# counting problem

• Mar 30th 2009, 10: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, 05: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 $\displaystyle (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, $\displaystyle a_{ij}$ will represent the square at the $\displaystyle i$-th row and $\displaystyle j$-th coloumn. If we put a rook at $\displaystyle a_{11}$ then the remaining rooks can only be placed everywhere except the first row and first coloumn deleted. Thus, the remaining $\displaystyle n$ rooks go on the $\displaystyle n\times n$ subboard. There are $\displaystyle R_n$ ways of doing that. The same argument for $\displaystyle a_{12},a_{13},...,a_{1n}$ and so $\displaystyle R_{n+1} = R_n + R_n + ... + R_n = (n+1)R_n$ with $\displaystyle R_2= 2$. Therefore, $\displaystyle R_n = n!$.