How do I determine the number of "second degree" derangements?

Question

The number of derangements for a given set is saying, the number of total possible ways of shuffling the members such that no member sits in its original place. This is given by the closed form:

$$!n = n! \cdot \sum_{k=0}^{n}\frac{(-1)^k}{k!}$$

Now, given a set S and one of its derangements D1, how many ways are there to find a new (let's say second degree) derangement D2 with members that are not in the same place as S and D1 at the same time...

Answer 1

(Corrected and expanded, again!)

As mentioned in the comments, the number of third permutations depends on the relationship between the first two. Asymptotically, the number of third permutations is $\sim e^{-2} n!\, (1-1/n - 1/(2n^2)+O(n^{-3}))$ regardless of the first two permutations. For the exact number, follow Ira's hint: Riordan, Introduction to Combinatorial Analysis, chapter 8, part 3.

I can give a hint of how much the number of third permutations varies according to the first two. Let $s$ be the number of intercalates in the first two permutations. (An intercalate is two positions where the two permutations have the same two entries in opposite order: where one has $ab$ the other has $ba$.) Since intercalates cannot overlap, the number of them can't exceed $n/2$. Asymptotically, the number of third permutations which are a derangement of the first two is $$ e^{-2} n!\, \Bigl( 1 - \frac 1n - \frac 1{2n^2} + \frac 1{3n^3} + \frac {s}{n^4} + O(n^{-4})\Bigr).$$

This is from C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, J. Combinatorial Theory, Ser. B, 48 (1990) 19-44. Corrected version.

A triple of permutations, each two of which are derangements of each other, is a 3-row Latin rectangle. There is a simple summation for the number of them due to Yamamoto, see page 18 in Stone's survey.

Answer 2

The answer depends on the cycle structure of $D_1$. Let $n:=|S|$ and $c_i$ be the number of cycles of length $i$ in $D_1$ (with $\sum_i ic_i=n$). Since $D_1$ is a derangement, we have $c_1=0$, but what follows well applies to any permutation (not necessarily derangement) $D_1$ of $S$.

The number of permutations $D_2$ that are derangement w.r.t. the identity permutation as well as w.r.t. $D_1$ equals $$\sum_{j=0}^n (-1)^j\cdot (n-j)!\cdot [z^j]\ F(z),$$ where $[z^j]\ F(z)$ is the coefficient of $z^j$ in $$F(z) := (1+z)^{c_1}\cdot \prod_{i=2}^n \left( \left(\frac{1+\sqrt{1+4z}}2\right)^{2i} + \left(\frac{1-\sqrt{1+4z}}2\right)^{2i} \right)^{c_i}.$$

This can be obtained with the method described in my paper (in particular, see formula (4) and Lemma 1).

Particular cases:

• when $c_1=n$ (i.e., $D_1$ is the identity permutation), we get just the number of derangements;
• when $c_n=1$ (i.e., $D_1$ is a cyclic permutation), we get the menage number A000179(n);
• when $n=2m$ and $c_2=m$ (i.e., $D_1$ is a derangement and an involution), we get A000316(m) = A000459(m)$\cdot 2^m$.