recurrence relation for putting n nonattacking rooks in $n^2$ board

Question

what is recurrence relation for putting n non attacking rooks in $n^2$ board?

can it be $a_n = n^2 \times a_{n-1}$ ?

or

$a_n = a_{n-1} + (n-1) a_{n-2} ?? $

I need proof thanks!

Answer 1

Pick a square in the first row to put a rook. There are $n$ to choose from. It eliminates the first row and one column which means you effectively have an $(n-1)\times(n-1)$ board left in which to place the remaining $n-1$ rooks.

Answer 2

It is neither of these two. The proper recurrence relation is $$ a_n = n \cdot a_{n-1}, $$ as each row must contain exactly one rook, and there are $n$ ways of placing a rook into the first row. Once you have done that, cross out the column where you have placed it and the first row to get $(n-1)\times(n-1)$ board where you need to place $n-1$ non-attacking rooks.

By the way, the number of possibilities of placing theses rooks is $n!.$

Answer 3

It's the same as for permutations.

Each piece must be placed in its own column and in its own row.
So you can put them all on the diagonal, then permute columns (or rows).
Each resulting setup is valid, and each valid setup can be reached this way, hence the number of valid setups equals the number of permutations of $n$ distinct elements.