# counting problem

• Mar 30th 2009, 11:24 AM
smellatron
counting problem
Let
Rn be the number of ways to place n non-attacking rooks on an nxn chess-board.
(a) Prove that |
Rn|= n!.
(b) Define
f : Rn =>Z by

f
(r) = number of rooks in r on the diagonal squares

(for r is an element of
Rn). Is f injective? Is it surjective? Is there a partition of Rn described by f?

The first part i get that |Rn| is n^2!/n! because there are n^2 places to go and n rooks, not sure if right.

part b has me confused. It should be injective and surjective since there is only one choice for the rook to go to at one time. Any help would be great.
• Mar 30th 2009, 06:06 PM
ThePerfectHacker
Quote:

Originally Posted by smellatron
[LEFT]Let Rn be the number of ways to place n non-attacking rooks on an nxn chess-board.
(a) Prove that |
Rn|= n[FONT=CMR10][SIZE=3]!.

Consider a $(n+1)\times (n+1)$ board. By pigeonhole principle each rook must be located at its own row alone. Let us give each square a name, $a_{ij}$ will represent the square at the $i$-th row and $j$-th coloumn. If we put a rook at $a_{11}$ then the remaining rooks can only be placed everywhere except the first row and first coloumn deleted. Thus, the remaining $n$ rooks go on the $n\times n$ subboard. There are $R_n$ ways of doing that. The same argument for $a_{12},a_{13},...,a_{1n}$ and so $R_{n+1} = R_n + R_n + ... + R_n = (n+1)R_n$ with $R_2= 2$. Therefore, $R_n = n!$.