I have a $N \times M $ grid and I am trying to calculate the number of ways I can color this grid in maximum $k$ colors (I can use only $2$ colors or all $k$ colors) with the exception that two adjacent cells can not be painted in the same color.
For example the following 3x3 grid can be colored in colors {0, 1, 2} in this way:
(2, 1, 2)
(1, 2, 1)
(2, 1, 0)
but not in this way:
(2, 1, 2)
(1, 2, 0)
(2, 1, 1)
because two colors 1 are adjacent (in the last row).
Currently I am out of ideas how to approach it.
I tried to use inclusion-exclusion principle where I counted all ways to count the colors, then removing all where 2 colors are adjacent and so on. Not only I was not able to calculate it properly I am also am not sure that this is correct.
I also tried to use the following approach. The (0, 0) cell can be colored in $k$ ways. The (0, 1) can be colored in $k-1$ way (the same way (0, 2) ... and all other in this row.
On the next row (1, 0) can be also colored in $k - 1$ way. But the (1, 1) element can be colored in $k-1$ way if cells (0, 1) and (1, 0) are colored in the same way and in $k-2$ ways otherwise. This looked like a valid approach, but I still can not figure out how to calculate it.
Am I on the right track with my second approach or there is a better way to calculate this?