Four rooks are randomly placed on a $4 \times 4$ chessboard. Suppose no rook can attack another. Under this condition, what is the probability that the leading diagonal of the chessboard has no rooks at all?
Since no rook can attack another, we know that each row and each column contains exactly one rook each. Let $A_i$ be the event that row $i$ has its rook on the diagonal. Then $P\{A_i\} = \frac{1}{4}$ for each $i = 1,\dots,4$.
We want to find the probability that the diagonal of the chessboard has no rooks at all, or equivalently that none of the rows have their rook on the diagonal. Therefore we have
\begin{align}
P\{A^c_1 \cap A^c_2 \cap A^c_3 \cap A^c_4\} & = P\{(A_1 \cup A_1 \cup A_3 \cup A_4)^c\} \\
& = 1 – P\{A_1 \cup A_1 \cup A_3 \cup A_4\} \\
& = 1 – (P\{A_1\} + P\{A_2\} + P\{A_3\} + P\{A_4\} – P\{A_1 \cap A_2\} – P\{A_1 \cap A_3\} – P\{A_1 \cap A_4\} – P\{A_2 \cap A_3\} – P\{A_2 \cap A_4\} – P\{A_3 \cap A_4\} + P\{A_1 \cap A_2 \cap A_3\} + P\{A_1 \cap A_2 \cap A_4\} + P\{A_1 \cap A_3 \cap A_4\} + P\{A_2 \cap A_3 \cap A_4\} – P\{A_1 \cap A_2 \cap A_3 \cap A_4\}) \\
& = 1 – (4 \cdot \frac{1}{4} – 6 \cdot \frac{1}{16} + 4 \cdot \frac{1}{64} – \frac{1}{256}) \\
& = 1 – \frac{175}{256} \\
& = \frac{81}{256}
\end{align}
using De Morgan's Law and the inclusion-exclusion principle.
However, it seems that this is incorrect since if we consider the number of ways that we can place the rooks such that no rook can attack each other we have $\frac{(4!)^2}{4!} = 4! = 24$ [as per this answer for a similar problem] and so the answer should have denominator of 24. Having said that I don't see where my answer is wrong, so would someone be able to show me the correct solution?
Best Answer
Each non-attacking placement of the rooks defines a permutation $c_1c_2c_3c_4$ of $\{1,2,3,4\}$: $c_k$ is the number of the column containing the rook in row $k$. There are $4!=24$ such permutations, all equally likely. Those that have no rook on the main diagonal are derangements, and there are $9$ of them, so the desired probability is $\frac9{24}$.
If you know the formula for the number of derangements of a set of $n$ objects, you can use it, but $4$ is small enough that it’s almost as easy just to list them:
$$\begin{align*} &2143,2341,2413\\ &3142,3412,3421\\ &4123,4312,4321 \end{align*}$$