1
$\begingroup$

$8$ rooks are randomly placed on different squares of a chessboard. A rook is said to attack all of the squares in its row and its column.

Compute the probability that every square is occupied or attacked by at least $1$ rook. You may leave unevaluated binomial coefficients in your answer.

I divided the question into cases, where Case $1$ is when there're only one rook in every row and column (which can be done in $8!$ ways).

But then, when I get to Case $2$ (which is when there're $2$ rooks in every row or column) I'm stuck. There're $\dbinom{8}{2}$ choices for choosing the squares in which the rooks will be, $8\cdot 7$ choices for those two rooks ... then 8C2 again for the next row, but then I overlap having more than one rook in a column ... and it's all confusing!

$\endgroup$
2
$\begingroup$

You should be using in inclusion-exclusion. Count the ways they fill all the rows, add the ways they fill all the columns, and subtract the ways they fill both because you counted them twice.

$\endgroup$
  • $\begingroup$ Yes. I agree with this. Though, to be pedantic, it would be a good idea to show that the only way to fulfil the condition in the question is if either all $8$ rows or all $8$ columns (or both) each contain a rook. $\endgroup$ – N. Shales May 8 '18 at 16:26

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.