## zepdrix one year ago (Combinatorics) In how many ways can five indistinguishable rooks be placed on an 8-by-8 chess board so that no rook can attack another and neither the first row nor the first column is empty?

1. zepdrix

The answer key says $$\rm =\left(\begin{matrix}7\\4\end{matrix}\right)^2 4!+7!\left(\begin{matrix}6\\3\end{matrix}\right)^2 3!$$

2. zepdrix

I'm seeing addition in the answer, so I assume I'm probably need to break this into cases.

3. zepdrix

It's just not quite working out for me though, hmm

4. zepdrix

Place one rook into the first row / first column. Then place the other 4 rooks into 7 rows $$\left(\begin{matrix}7\\4\end{matrix}\right)$$ Then these 4 rooks have 7 columns to choose from $$\large\rm P(7,4)$$ And I did some calculations and it turns out that:$\large\rm \left(\begin{matrix}7\\4\end{matrix}\right)^2 4!=\left(\begin{matrix}7\\4\end{matrix}\right)P(7,4)$Oo ok good! I'm on the right track here.

5. zepdrix

I similarly messed with the answer key to the second part and turned it into:$\large\rm 7!\left(\begin{matrix}6\\3\end{matrix}\right)P(6,3)$Hmm

6. zepdrix

Ooo Google to the rescue! yay, found something

7. zepdrix
8. zepdrix

Ok I guess I setup the first CASE correctly, placing the rook in the upper left corner. CASE 2 should be no rook in upper left? Hmm

9. zepdrix

Case 2: So when we look at the combinations of rows, we'll have to reserve one rook for the top row. So we only have 4 other rooks to work with. Hmm it looks like 3 in the answer though.. hmmm thinking

10. zepdrix

Oh oh so if a rook is not in the upper left corner, it means i need to reserve a rook for the first row, and another for the first column separately... ok ok ok

11. zepdrix

The rook in the first row has 7 options. The rook in the first column has 7 options. Leaving me with 3 rooks to place in 6 rows $$\left(\begin{matrix}6\\3\end{matrix}\right)$$ and permutate them in the columns $$\large\rm P(6,3)$$ Oooo yay I think I got it! $$\large\rm case2=7\cdot7\left(\begin{matrix}6\\3\end{matrix}\right)P(6,3)$$ Which matches the solution from that website, but not the book. I think it's more likely the book is wrong. Man I deserve a medal for that workout -_-

12. mathmate

I agree with your logic: Case 1: occupy square A1 (lower left corner): 4 rooks left, with 49 squares, 36 squares, 25 squares, 16 squares, etc. N1=49*36*25*16/4!=29400 ........=C(7,4)^2*P(7,4) Case 2: occupy one of A2-A8, AND B1-H1, 3 rooks left: N1=7*7*36*25*16/3!=117600............=7^2*C(6,3)^2*P(6,3) Total N1+N2=147000 ways This matches the given answer if the given answer were: $$\rm =\left(\begin{matrix}7\\4\end{matrix}\right)^2 4!+\color{red}{7^2 }\left(\begin{matrix}6\\3\end{matrix}\right)^2 3!$$

13. zepdrix

Doh!! It is a 7^2 in the book :P Man I'm a doofus!