A derangement of a list of $n$ distinct entries is a permutation of that list such that no corresponding entries match. It is well-known that the number of such derangements is the nearest integer to $n!/e$ where $e$ is the base of natural logarithms.

Let's say that a permutation of a list is a $\mu$-derangement if both it and its reverse ordering are derangements. Equivalently, iff the permutation is a derangement both of the original list and of the reverse of the original list.

How many $\mu$-derangements of the list $[1,2,..,n]$ are there? Is there an exact formula? A good approximation or bound?

There are no $\mu$-derangements for $n \lt 4$, except in the trivial case of an empty list. I got counts for $n \le 10$ below by enumerating possibilities with a bit of Prolog code:

 n | # of µ-derangements 
 4 |           4
 5 |          16
 6 |          80
 7 |         672
 8 |        4752
 9 |       48768
10 |      440192

The OEIS has this sequence as A003471, with a recurrence relation that suggests some separation into even and odd terms might simplify things.

  • $\begingroup$ I think you mean $n!/e$- is it really the nearest integer to that? I know that the probability that a permutation is a derangement is close to $1/e.$ $\endgroup$ – Geoff Robinson Dec 27 '11 at 11:21
  • $\begingroup$ @GeoffRobinson: Just so, Geoff. Fixed! $\endgroup$ – hardmath Dec 27 '11 at 11:26
  • 3
    $\begingroup$ Empirically, both sets of values seem to be asymptotic to $n!/e^2$. The dominant error term appears to be $1/n$ for even values of $n$ and $1/(2n^2)$ for odd values. Probably an asymptotic expansion is possible based on the recurrence relation? $\endgroup$ – mjqxxxx Dec 27 '11 at 13:02
  • 1
    $\begingroup$ Note that the very rough approximation $(1- \frac{2}{n})^n$ gives the right answer asymptotically for the probability that a permutation is this kind of derangement, even though it (unjustifiably) treats the choices as independent. The heuristic argument is that for a given permutation $\sigma,$ there are two values of $\sigma(i)$ which are not permissible. $\endgroup$ – Geoff Robinson Dec 27 '11 at 14:58
  • 1
    $\begingroup$ I proposed an edit to the OEIS sequence adding the integral formula. $\endgroup$ – joriki Dec 27 '11 at 15:19

For $n=2k$, this is equivalent to What's the General Expression For Probability of a Failed Gift Exchange Draw, with a slot and its reverse partner forming a couple – the answer for this case is

$$\int_0^\infty\left(x^2-4x+2\right)^k\mathrm e^{-x}\mathrm dx\;,$$

and I derived in the answer to the other question that this goes as $n!/\mathrm e^2$ for large $n$.

For $n=2k+1$, there's a single slot without a partner which leads to a factor $-L_1(x)=x-1$, so the answer for this case is

$$\int_0^\infty\left(x^2-4x+2\right)^k(x-1)\mathrm e^{-x}\mathrm dx\;.$$

The asymptotic analysis remains essentially unchanged, so this also goes as $n!/\mathrm e^2$ for large $n$.

  • $\begingroup$ Danke shön, joriki! The application that motivated me here was for an $n = 2k$ even term case, trying to optimize the search strategy there. Your answer nicely sheds light on why the even and odd term cases differ by a little. Since $\int_0^\infty x^k e^{-x} dx = k!$, one can in principle expand your integral formula into a summation involving factorials. $\endgroup$ – hardmath Dec 27 '11 at 19:26
  • $\begingroup$ @hardmath: It does seem so; expand the polynomial power with the multinomial formula, and then replace the integrals with factorials... if there was a recurrence relation for these, I wouldn't be surprised. $\endgroup$ – J. M. is a poor mathematician Dec 28 '11 at 2:45

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.