Placing 8 rooks to a chessboard

Question

In MIT Opencourware Probabilistic Systems Analysis and Applied Probability course, there's a recitation problem for Lecture 4:

Quotestion: Imagine that 8 rooks are randomly placed on a chessboard. Find the probability that all the rooks will be safe from one another, i.e. that there is no row or column with more than one rook.

And the solution is like that:

Solution: We will count the number of favorable positions in which we can safely place 8 rooks, and then divide this by the total number of positions for 8 rooks on a 8 × 8 chessboard. First we count the number of favorable positions for the rooks. We will place the rooks one by one. For the first rook, there are no constraints, so we have 64 choices. Placing this rook, however, eliminates one row and one column. Thus for our second rook, we can imagine that the illegal column and row have been removed, thus leaving us with a 7 × 7 chessboard, and thus with 49 choices. Similarly, for the third rook we have 36 choices, for the fourth 25, etc... There are 64 · 63 · · · 57 total ways we can place 8 rooks without any restrictions, and therefore the probability we are after is: 64 · 49 · 36 · 25 · 16 · 9 · 4 / (64!/56!)

I understand the part that placing the rooks that all will be safe but I could not understand the part that we find the sample space(total number of positions for 8 rooks on an 8 × 8 chessboard).
Why don't we just say that there are C(64,8) ways to choose the cells that we will place the 8 rooks? For example, placing a1 first and e7 second does not matter for us, it could be e7 first and a1 second. It means the ordering is not important for us. So why does the solution counts step by step?

Answer 1

Because it is not mentioned in the problem that rooks are the same. Also if rooks are exactly the same the first step will be different, because we will need to divide our total number by $8!$ to avoid a similar situation with permutations of rooks.

Answer 2

We will count the number of favorable positions in which we can safely place $8$ rooks, and then divide this by the total number of positions for $8$ rooks on a 8 × 8 chessboard.

In fact that is not what the rest of the solution does. What the solution does is to count the number of ways we can safely place eight rooks in sequence, and divide by the total number of ways to place eight rooks on an $8\times 8$ chessboard in sequence.

If the solution were written the way the first sentence says it is, both the numerator and denominator of the answer would be divided by a factor of $8!$ in order to factor out the sequence in which the rooks are placed.

If we look only at the final result of positioning the rooks, as promised in the first sentence of the solution, you are correct, there are just $\binom{64}{8}$ distinct positions not counting the different sequences in which the placements can be made. On the other hand there are just $8!$ safe positions for all eight rooks, the number of permutations of the numbers $\{1,2,\cdots, 8\},$ which is the number of one-to-one functions from $\{1,2,\cdots, 8\}$ to $\{1,2,\cdots, 8\},$ in which each such function tells us the rank (or row number) of the single rook in each file (or column). The final answer then is $$ \frac{8!}{\binom{64}{8}} = \frac{8!}{\frac{64!}{56!\cdot8!}} = \frac{(8!)^2 56!}{64!}. $$

Notice that the way the printed solution counts the "positions," the answer comes out to $$ \frac{64 \cdot 49 \cdot 36 \cdot 25 \cdot 16 \cdot 9 \cdot 4}{64!/56!} = \frac{8^2\cdot 7^2\cdot 6^2\cdot 5^2\cdot 4^2\cdot 3^2\cdot 2^2\cdot 1^2}{64!/56!} = \frac{(8!)^2 56!}{64!}. $$

That is, it's the same answer either way.

We should not be surprised that the answer is the same. What this tells us is that the practical constraints of having to place the rooks one by one (we cannot just dump a bag of rooks on the board and expect them each to take a different square) does not affect the probabilities of the final outcome. This problem is one of a large class of problems in criteria for "success" do not care about the sequence of a group of objects in a configuration, but in which there is an obvious way to sequence the objects when counting configurations and in which we get the same probabilities whether we do or do not use the sequence of the objects to distinguish one "configuration" from another.

Answer 3

A natural interpretation of the above Q. leads to probability

$$ \frac {8!}{\binom{64}8} $$

which is the same as

$$ \frac{7!\cdot 7!\cdot56!}{63!} $$

Answer 4

If the rocks are safe from one another then on every row there must stand exactly one rook. For the first row there are $8$ choices for the rook. Then for the second row there are $7$ choices left, et cetera. So there are $8!$ configurations such that the rocks are safe for each other.

There are $\binom{64}8$ configurations in total, so by equiprobability we find probability: $$\frac{8!}{\binom{64}8}$$