# How do I determine the number of “second degree” derangements?

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...

• Does "not in the same place as $S$ and $D1$ at the same time" mean that $S,D2$ and $D1,D2$ are both derangements? In that case, the number of ways depends on the choice of $D1$. You are extending a $2\times n$ Latin rectangle to a $3\times n$ Latin rectangle. There are four ways to extend $1234,2143$ but only two ways to extend $1234,2341$. I think that Sam Hopkins wants two permutations $\pi,\sigma$ such that $i,\pi(i)$, and $\sigma(i)$ are distinct for all $i$. – Richard Stanley Sep 12 at 19:21
• Yes, sorry, what I wrote earlier was wrong. This problem can be rephrased as counting/understanding the structure of the set of pairs of permutations u and v such that u, v, and $u^{-1}v$ are all derangements. If the question is specifically about how to extend a fixed derangement u to such a pair, then as Richard said it depends on the specific u. – Sam Hopkins Sep 12 at 19:29
• This problem is discussed in John Riordan's Combinatorial Analysis but I don't have access to my copy right now. – Ira Gessel Sep 12 at 21:13
• The Riordan reference is Chapter 8, Section 3, page 201. Please excuse a bit of self-publicity: Riordan's method for solving this problem is the hardest part in Section 4.3 of my draft combinatorics textbook. In particular, Exercise 4.19 gives the formula $\sum_k \binom{n}{k} !k !(n-k) v_{n-2k}$ for the number of $3 \times n$ Latin rectangles, where $v_m$ is a Ménage number. See ma.rhul.ac.uk/~uvah099/Maths/CombinatoricsWeb.pdf. – Mark Wildon Sep 14 at 9:53
• I just discovered that this question is essentially a duplicate of mathoverflow.net/questions/144899/number-of-permutations. – Sam Hopkins Oct 1 at 23:19

(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.

• For Ira's paper: people.brandeis.edu/~gessel/homepage/papers/3latin.pdf – Sam Hopkins Sep 14 at 1:03
• For another approach to 3-row Latin rectangles, with generalizations and further references, see my paper Counting three-line Latin rectangles, Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985), 106–111, Lecture Notes in Math., 1234, Springer, Berlin, 1986. (I had a bad link in the original version of this comment; use the one in Sam's comment.) – Ira Gessel Sep 14 at 2:34

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$$.
• Can you say what you mean by "possible derangements $D_2$" in the case that $D_1$ is not a derangement of $S$ (e.g., if $D_1$ is the identity)? – Sam Hopkins Sep 14 at 0:29
• @SamHopkins: $D_2$ should be a derangement w.r.t. the identity permutation as well as a derangement with respect to $D_1$. I've clarified this in my answer. – Max Alekseyev Sep 14 at 0:48
• Thanks, makes sense! – Sam Hopkins Sep 14 at 0:56