2
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ What if (say) the first rook in the first row is in the second column? Then the second rook still has 7 possibilities. $\endgroup$ – Parcly Taxel Sep 12 '16 at 9:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Sep 12 '16 at 10:19
  • $\begingroup$ Are you happy with the comment from @Parcly? $\endgroup$ – Gerry Myerson Sep 14 '16 at 5:29
  • $\begingroup$ Wikipedia has a nice discussion deriving the number of derangements. $\endgroup$ – Ross Millikan Sep 16 '16 at 14:59
1
$\begingroup$

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.

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

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.