Thread: counting problem

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

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