## Problem 29

Posted 08/01/2016
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

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$.