8 rooks on a checkerboard that do not attack each other off the main diagonal

664 Views Asked by At

The number of arrangements of eight rooks on a chessboard such that no two attack each other is $8!$. A way to see this is to note that a placement of a rook is the same as a pair $(i,j)\in [8]\times[8]$. We want to place rooks at different places, and there are $(8!)^2$ ways to do this, and we must divide by $8!$ because rooks are indistinguishable.

Suppose I want to check the number of such arrangement which are all off the main diagonal. I read on this site that these are related to things called derangements, and that there's a magic formula for them involving $e$. I would like to understand what I'm missing in the following naive approach:

First, let's look at the problem in a different way. Instead of thinking about eight identical rooks on different rows of a chessboard, think of eight different objects - the row number of a rook corresponds to the identifier of the object. Then we just want to arrange eight different objects in a row (different columns), so $8!$ objects.

Now to have off-diagonal arrangements, I think we want fixed-point-free permutations (derangements). So object 1 (they have labels) can go to 7 places, object 2 can go to 6 places and so on. This yields $7!$ as an answer. What am I missing?

2

There are 2 best solutions below

4
On

The indices of the elements of any valid term of an 8-by-8 determinant would serve to locate your eight rooks. There are 8! such terms.

Additional info:
Where $n = {1 ... 9}\text{ }$, I did the enumeration $M_n$, the count of permutations completely outside the main diagonal of an n-by-n determinant, by brute force. See the table:

$\begin{array}{r|r|l} n&M_n&\frac{n!}{M_n}\\ \hline 1&0&\\ 2&1&2\\ 3&2&3\\ 4&9&\approx 2.666667\\ 5&44&\approx 2.727273\\ 6&265&\approx 2.716981\\ 7&1854&\approx 2.718447\\ 8&14833&\approx 2.718263\\ 9&133496&\approx 2.718284 \end{array}$

Apparently, as $n\text{ }$ increases, the quotient $\frac{n!}{M_n}$
approaches the base of natural logarithms $\mathrm{e}.$
$M_n=\left\lfloor{\frac{n!}{\mathrm{e}}}+.5\right\rfloor\text{ }$works nicely.

I SHOULDN'T HAVE WASTED MY TIME: I just found a nice discussion of the constant e in WikiPedia -- https://en.wikipedia.org/wiki/E_%28mathematical_constant%29?wprov=sfla1 -- , and within that discussion is a section devoted to derangements, which I think would serve as an answer to the OP''s query.

0
On

This would be a good use case for derangements! These are the permutations, except each item can't be placed in it's starting position. We can think of it as if we are placing all the rooks on the diagonal, where they can't be. Then, by deranging all 8, they will end up in new positions, none of which will be on the diagonal.

$Derangements(n) = \lfloor\frac{n!}{e}\rceil$