0
$\begingroup$

In how many ways can five indistinguishable rooks be placed on an 8-by-8 chessboard so that no rook can attack another and neither the first row nor the first column is empty?

I started out by calculating the total number of ways of placing $5$ rooks on $8\times8$ board so that no rook can attack another which is $\binom{8}{5}5!$. Then I calculated the number of ways in which 5 rooks can be placed by leaving both first row and first column empty, which then corresponds to placing 5 rooks on $7\times7$ board (because first row and column are out of picture), this can be done in $\binom{7}{5}5!$ ways. Then I subtracted this from total, giving me $4200$ ways. But I think this method is not correct as I am just subtracting the case of leaving both first row and first column empty, which should not lead to just getting both first row and first column non-empty.

My another approach is this - Calculate the ways where there is a combination where one rook gets placed in intersection of first row and first column or, where one rook gets placed in first row and another rook gets placed in first column.

For the first part, there is only one way to place a rook in the intersection of first row and first column, and rest 4 rooks are now to be placed on $7\times7$ board which can be done in $\binom{7}{4}4!$ ways. For the second part, take anyone of the squares in the first row (not intersecting with first column) and place a rook on that. This can be done in $7$ ways. Then we have remaining 7 rows and 7 columns (including first column). Again take one rook and place it in first column, which can be done in $7$ ways. Now 6 rows and 6 columns are remaining along with 3 rooks, which can be placed in $\binom{6}{3}3!$ ways. So total ways I get is $\binom{7}{4}4! + 7\times7\times\binom{6}{3}3! = 6720$.

Please tell me which of my approach is correct and if correct, then have I done the correct calculation or missed something.

$\endgroup$
2
$\begingroup$

The critical error in your working is to say that there are ${n\choose k}k!$ ways of placing $k$ non-attacking rooks on an $n\times n$ board (where $k<n$).

Yes, there are ${n\choose k}$ ways of choosing a subset of $k$ rows. Yes, there are $k!$ ways of ordering the subset. But you also have to choose a subset of $k$ columns. So there are in fact $${n\choose k}^2k!\text{ ways }$$

You have correctly identified the other problem with your first approach: you are not subtracting off cases where there is a rook in the first row, but not in the first column (and vice versa).

Your second approach is correct in principle, but you need to take account of the point above.

$\endgroup$
  • $\begingroup$ Thanks, that really is a critical error. Is there any other way (a general way) to do this type of problem? Here there were only 5 rooks and 8x8 board and restriction on only one row and one column, in general, there could be like 20x20 board with 12 rooks and restriction on multiple rows and columns. $\endgroup$ – Ankit Seth Jan 7 at 18:00
  • $\begingroup$ Combinatorics is a notoriously tricky area. It is easy to use the wrong formula or otherwise get things wrong. I can only recommend plenty of practice! Plus it is usually worth checking a result for small values of $n$. It is also easy to get intractable problems which can only be solved by software for modest values of $n$. $\endgroup$ – almagest Jan 7 at 18:04

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.