1

In this past thread linked here, we used combinations in the denominator: Chess Probability 8 rooks

I understand the past thread, but I am trying to understand another way to look at the problem that does not use directly combinations which is linked below. Let's limit this thread to the thinking used in the below pdf solutions:

Problem 2 here: http://web.mit.edu/6.041/www/6.041_Fall2010/Recitations/rec04.pdf

Solutions: http://web.mit.edu/6.041/www/6.041_Fall2010/Recitations/rec04_sol.pdf

When I started the problem, I thought "The sample space must be 64 choose 8 because those are the distinct ways to arrange the chessboard". I got the same numerator as their solutions. However, it seems based on the solution that if my numerator is 64*49*36*etc then my denominator should actually be 64!/56! in order to be consistent and I can't figure out why/verbalize what the problem is. There's a subtlety in this or misunderstanding I have that I was hoping we could talk about as the topic of this thread. My first guess is that somehow the numerator and denominator must either both be viewed as permutations or viewed as both be combinations, but I'm not sure if that idea right or what that means in terms of this problem's numbers. For example, is the numerator of 64*49*36*etc a permutation or a combination?

I'm not taking a class now, and these practice problems/solutions are publicly available

Community
  • 1
LongApple
  • 113

1 Answers1

2

Your first guess is correct. It is most convenient to count the ways to place the rooks one at a time so that they do not attack each other. For this count, order matters. The row/column position of the first rook to be placed can be chosen in $8^2$ ways. For each such way, the row/column position of the second rook to be placed can be chosen in $7^2$ ways, and so on, for a total of $(8^2)(7^2)\cdots (2^2)(1^2)$.

Since we have counted the number of ways to place the rooks, in order, for the denominator we must also find the number of ways of selecting, in order, $8$ different positions. The first position to be chosen can be selected in $64$ ways. For each of these ways, the next position to be chosen can be selected in $63$ ways, and so on, for a total of $(64)(63)(62)\cdots(57)$ ways. These ways are equally likely.

For the probability, divide.

Alternately and equivalently, imagine that the rooks have labels $1$ to $8$. For the denominator, there are $64$ ways to choose the position of Rook 1, and for each of these ways there are $63$ ways to choose the position of Rook 2, and so on up to $57$ ways for Rook 8.

We count the ways to place Rook 1,2, and so on up to Rook 8 in a non-attacking configuration in the same way. Rook 1 can be placed in $8^2$ ways. For each of these ways, Rook 2 can be placed in a "safe" position in $7^2$ ways, and so on.

Remark: One could, in principle, use $\binom{64}{8}$ as denominator, that is, use as sample space the total number of ways to choose $8$ positions, where order of selection does not matter. But then we would also have to count the number of ways to choose $8$ mutually safe positions, where again order does not matter. It is not hard to show that the number of such choices is $\frac{8^27^2\cdots 2^21^2}{8!}$. Then we can divide as usual.

André Nicolas
  • 507,029