Counting Colorings of a Grid Given a $n \times m$ grid, define a valid coloring as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent if they share a side. How many valid colorings are there? Let $f(n, m, k)$ be the answer.

I search for a way to compute $f(n, m, k)$ fast, primarily in terms of time complexity. However, a polynomial-time solution is not required.

This problem was proposed in Codesprint 5 at HackerRank with constraints $1 \le n,m \le 8$ and $k \le 10^9$. However, I am not asking for this particular case, so it does not matter so much. It is worth mentioning there is a discussion on TopCoder, but I do not get it after several readings.

Approaches. I present my thoughts as following. First, we may explicitly enumerate all colorings. This works only on very small instances, because the number of colorings is growing exponentially. In order to see this, consider an $1 \times m$ grid and $k = 3$ colors. The first cell may be colored in $3$ ways and each following cell in $2$ ways, which yields $f(1, m, 3) = 3 \cdot 2^{m - 1}$.

Let's consider $n = 2$. If $m = 1$, we simply get $f(2, 1, 3) = 6$. Assume, we know $f(2, m, 3)$ for some $m \in \mathbb{N}$. Let $X$ and $Y$ be the colors in the rightmost / last column for an abritrary valid coloring of $2 \times m$ grid. In $(m + 1)^{th}$ column, there are $2$ colors for the top cell $(Y$ and the third color, say $Z$). Distinguish between two cases.

Case #1: Top cell has color $Y$. Then, our bottom cell can get color $X$ or color $Z$. There are two possible choices.

Case #2: Top cell has color $Z$. Then, our bottom cell must have color $X$.

Altogether, there are $3$ possibilities for the next step, i.e. $f(2, m + 1, 3) = 3 \cdot f(2, m, 3)$. Using our base case and solving the recurrence, the result comes out to be $f(2, m, 3) = 2 \cdot 3^m$.

These counting arguments get more complicated for larger values of $n$, even for $n = 3$ I do not find an explicit formula. In the original problem, there are significantly more colors than cells. It should be sufficient to consider colorings with exactly $1, 2, \dots, mn$ colors (let $a_{i}$ be the respective answers) and compute $\displaystyle \sum_{i = 1}^{mn} \binom{k}{i} a_{i}$. Therefore, don't worry too much about this step.

Hints and approaches are appreciated as well as solutions and references.
For every graph $G$ on $n$ vertices there is a degree $n$ polynomial $\chi_G$ such that $\chi_G(k)$ is the number of valid $k$-colorings of the graph. This polynomial is known as the chromatic polynomial, and can be found in exponential time. The easiest solution to the programming challenge is to precompute the chromatic polynomials. For example, denoting the $n \times m$ grid by $G(n,m)$, we have
$$
\begin{align*}
\chi_{G(1,1)} &amp;= x \\
\chi_{G(1,2)} &amp;= x^2 - x \\
\chi_{G(2,2)} &amp;= x^4 - 4x^3 + 6x^2 - 3x \\
\chi_{G(1,3)} &amp;= x^3 - 2x^2 + x \\
\chi_{G(2,3)} &amp;= x^6 - 7x^5 + 21x^4 - 33x^3 + 27x^2 - 9x \\
\chi_{G(3,3)} &amp;= x^9 - 12x^8 + 66x^7 - 216x^6 + 459x^5 - 648x^4 + 594x^3 - 323x^2 + 79x
\end{align*}
$$