1
$\begingroup$

I want to find the number of possible 8-rook setups such, that none of the rooks attacks one another. I can think of two ways to solve this problem:
One:
We place the rook on one of the $64$ fields. This rook will eliminate one row and one column and so we will be left with $7 \cdot 7$ fields. We repeat this process - another row and column are being cut off, leaving only $6 \cdot 6$ at our disposal. So, multiplying everything out, we get the desired number: $$(8!)^2$$
Two:
It is obvious that each of the rooks must be placed in a different column. Otherwise, they would be attacking each other. In the first column, we may place a rook on $8$ fields. In the second column, only on $7$ fields, because one is already being attacked. Proceed like this and we get this result:
$$8!$$ Why do these results differ so much? I reckon that one of them assumes that the rooks are indistinguishable from each other and the other one assumes that each rook is different. My question is - why. It seems to me that in both these attempts the order in which we place these rooks is taken into consideration.

$\endgroup$
1
$\begingroup$

In the first approach you have not consider the order that the rooks can be placed in, you need to divide by $8!$.

Edit: The first rook can be placed in $64$ different places, the second in $49$; at this stage the this configuration could have been attained by placing the first rook where the second rook is and then the second rook where the first rook is. In short you are multiply counting the configurations (in the first approach.)

$\endgroup$
  • $\begingroup$ Could you, please, elaborate a little bit more on "not having considered the order"? This is a little bit vague to me. $\endgroup$ – Aemilius Feb 20 '18 at 20:18
  • $\begingroup$ @Aemilius Please see the edit ... does this make it clearer ? $\endgroup$ – Donald Splutterwit Feb 20 '18 at 20:23
  • $\begingroup$ And this problem does not apply to the second approach because each column can only contain one rook and so no two identical situations on the board can arise? $\endgroup$ – Aemilius Feb 20 '18 at 21:01
  • $\begingroup$ @Aemilius That is right. $\endgroup$ – Donald Splutterwit Feb 20 '18 at 21:30

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.