Question

(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?

Answer 1

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!\)

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

Ooo Google to the rescue! yay, found something

Answer 7

http://jeremycue.com/wp-content/uploads/2013/06/10-More-Counting-Problems.pdf
Problem 7

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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 -_-

Answer 12

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!\)

Answer 13

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