Number of ways to place $k$ non-attacking rooks on a $100\times 100$ chess board

Question

I need to show that the number of ways to place $k$ non-attacking rooks (no two share the same column or row) on a $100\times 100$ chessboard is $k!{100 \choose k}^2$.

When I try to formulate this equation I end up getting ${100 \choose k}^2$ because you need to choose $k$ columns from $100$ columns and $k$ rows from $100$ rows. I know this isn't correct because if you have $k=100$, there is more than just $1$ solution. However I don't know how to come up with the $k!$ part of the equation.

Answer 1

First of all, congrats on realizing that the answer you got can't possibly be correct. It's always a good idea to test formulas against special cases, to see if they stand up.

One way to arrive at the correct answer is to view the placement of the rooks in two steps: First choose the $k$ rows that the rooks will go in, and then, going row by row, decide which column to place that row's rook in. The first rook has $100$ columns to choose from, the second will have $99$, the third $98$, and so on. The total is thus

$${100\choose k}100\cdot99\cdot98\cdots(100-(k-1))={100\choose k}{100!\over(100-k)!}={100\choose k}{100!\over(100-k)!k!}k!={100\choose k}^2k!$$

Answer 2

First, choose your $k$ rows and columns, as you said. Start by considering the configuration in which the rooks are successively placed in the legal square furthest to the top and to the left (so that the rooks go "diagonally down to the right").

From there, it suffices to note that any rearrangement of the rook-columns results in a new and valid configuration. Since there are $k!$ such rearrangements, there are $k!$ configurations for any particular choice of $k$ rows and $k$ columns.

Answer 3

Your problem is that $\binom{100}{k}^2$ only gives you the ways to choose the columns and the rows separately, without specifiying which row goes with which column. This is why you need to add the factor $k!$, which corresponds to the number of bijections between your $k$ rows and your $k$ columns, i.e. the number of ways to associate them together.

An alternative way of obtaining this is to consider that you first choose $\binom{100}{k}$ column where you will place your rooks, then choose for each column the row where you place a rook; this second step amonts to choosing $k$ rows with order, which you can do in $\frac{100!}{(100-k)!}=\binom{100}{k}k!$ ways. Multiplying the two numbers together gives you the result.

Answer 4

Regards User. If i may contribute, here is my view :

A 100 $\times $ 100 chess board can be viewed as a matrix of size 100 $\times $ 100. For example : let $$(i, j), \:\: \text{ with } \:\:\: i,j=1,2,... ,100$$ denotes the $i$th row and $j$th column of the board.

To solve your problem, the key is : the $k$ non-attacking roots is as same as no two $(i_{1}, j_{1})$ and $(i_{2}, j_{2})$ with $i_{1}=i_{2}$ or $j_{1}=j_{2}$. Two rooks with position $(1, 100)$ and $(91, 100)$, for example, does not satisfy the non-attacking roots condition.

To illustrate how to solve this, first, you could start with $k=1$.

• For k=1. Let the position of this particular rook is $(x_{1},y_{1})$. Then there are 100 possibilities for $x_{1}$, and 100 possibilities for $x_{2}$. So the number of possibilities is (100)(100) = $ 1! \binom{100}{1}^{2} $

• For k=2. For each of the two rooks, their positions are denoted with $(x_{1},y_{1})$ and $(x_{2}, y_{2})$. For the first one, There are 100 possibilities for each $x_{1}$ and $y_{1}$. For the 2nd rook, $x_{2}$ and $y_{2}$ each has 99 possibilities (since they can't be equal to the 'coordinates' of the 1st rook). So the number of possibilities to put 2 non-attacking distinguished rooks is $$ (100^{2})(99^{2}) $$ For your problem, they are not distinguished, so we have to divide this by 2 (exactly $2!$), because we can choose either rook to be the 1st or the 2nd. So, output : $$ \frac{(100^{2})(99^{2})}{2!} = \frac{(100 \cdot 99)(100 \cdot 99)}{2!} = \frac{(100 \cdot 99)(100 \cdot 99)}{2!} \left(\frac{98! \cdot 2!}{98! \cdot 2!} \right)^{2} = 2! \binom{100}{2}^{2} $$

• For k=3 and above, you would be confident to try and continue this method.

Hope this will helps. Regards, Arief.