0
$\begingroup$

I am trying to show that the number of ways to place $k$ non attacking rooks (no two share the same row or column) on a $100 \mathsf x 100$ chessboard where each rook may only be placed on a white tile.

I need to come up with the solution formula to be $\sum_{i=0}^k i!$$50\choose i$$^2$$(k-i)!$$50 \choose k-i$$^2$

I am pretty confused how to even start this. Does the two "choose" parts of the formula have something to do with once you choose one row you have one less column to choose from?

$\endgroup$
1
$\begingroup$

Think of the white tiles in odd rows and columns: any rook on these tiles is non-attacking to rooks on white tiles of even rows and columns. So, it is like having two separate chessboards, each of size $50\times 50$. You need to first partition your $k$ rooks into two subsets, and then put each subset on one of the $50\times 50 $ chessboards in a non-attacking manner. Let's suppose you put $i$ rooks on the first chessboard, the number of ways to do that is (https://en.wikipedia.org/wiki/Rook_polynomial) \begin{equation} i!\binom{50}{i}^2 \end{equation} and the remaining $k-i$ rooks should be placed on the second chessboard. The number of ways you can do this is \begin{equation} (k-i)!\binom{50}{k-i}^2. \end{equation} Now multiply these together and sum over $i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.