This problem is about colorings of non-attacking rooks.
On a $n\times n$ board we place $n$ rooks such that they don't attack each other, that is, there is exactly one rook in each row/column.
We say two rooks are adjacent if they share a vertex. In the figure above, Rook A and Rook B are adjacent.
We use $k$ colors to color rooks such that no adjacent rooks have the same color.
Suppose $a_n^k$ is the number of $k$-colored non-attacking rooks on a $n\times n$ board such that no adjacent rooks have the same color.
For example, $\{a_n^1\}$ is given by
A002464, $a_1^2 = 2$, $a_2^2 =4$.
Find $a_n^k$.