Counting some special derangements
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.
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$.