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

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?

• What if (say) the first rook in the first row is in the second column? Then the second rook still has 7 possibilities. – Parcly Taxel Sep 12 '16 at 9:39
• Try it with something smaller, like a 4-by-4 chessboard, where it's not hard to write down all the derangements, and see what your procedure misses. – Gerry Myerson Sep 12 '16 at 10:19
• Are you happy with the comment from @Parcly? – Gerry Myerson Sep 14 '16 at 5:29
• Wikipedia has a nice discussion deriving the number of derangements. – Ross Millikan Sep 16 '16 at 14:59

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.

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.

• This does not answer the question. – user133281 Sep 12 '16 at 10:50
• @user133281 Sorry. I was still working on it. – Senex Ægypti Parvi Sep 12 '16 at 17:12
• Link to the "nice discussion of $e$"? – Gerry Myerson Sep 16 '16 at 10:31
• @Gerry Myerson \ Done! Sorry for the omission, sir. – Senex Ægypti Parvi Sep 16 '16 at 14:35