I am having some troubles with understanding some aspect of the problem below: Placing 3 INDISTINGUISHABLE rooks on a 6x6 board such that no two rooks attack each other (rooks can attack others if they are in the same row or column). I got to the point knowing that it is 36*25*16, but for the answer I don't get why you have to divide by 6, and also, what what the answer look like if the 3 rooks were changed to DISTINGUISHABLE?
Any advice and hint would be much appreciated.
$\endgroup$ 12 Answers
$\begingroup$Your two questions answer each other.
If the three rooks were distinguishable, then the answer would be $36\times25\times16$ as you originally worked out. If the wooks are indistinguishable, then that is no longer the right answer. For example, the following two positions:
are different positions if we take the rooks to be distinguishable, but are the same position if the rooks are indistinguishable.
For each possible position with three indistinguishable rooks, there are $6$ ways of colouring the three rooks to end up with a position with distinguishable rooks. That is why you need to divide by $6$.
$\endgroup$ $\begingroup$Your 36*25*16 is obviously obtained by placing one rook A anywhere on the board, the second rook B in any of the 25 squares that are not attacked by the first, and the last rook C in any of the 16 that are not attacked by any of the first two.
Now, suppose the rooks are distinguishable. Then if you switch the locations of A and B you get a different solution. For example, suppose you put rook A in the top right corner, and rook B in the bottom left. Then, later on, when you considered any of the other 35 positions for rook A, you put rook A in the botttom left corner, and rook B in the top right. So, both of those solutions are included as different solutiona in your 36*25*16, meaning that you have all solutions here ... if these two solutions are indeed different ... Which is true only if the rooks are distinguishable.
But what if the rooks are indistinguishable? Then swapping any two rooks means you get the same solution (the board will end up exactly the same). So, what you counted earlier as two different solutions, is really just one solution! In fact, since you have 3 rooks, and since there are 6 ways to distribute the 3 rooks between any 3 positions, this means that you counted the same solution as 6 different solutions in your 36*25*16 formula. Hence, you need to divide the 36*25*16 by 6 in order to get the number of solutions if the rooks are indistinguishable.
$\endgroup$
