3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Richard Stanley Sep 12 at 19:21
  • $\begingroup$ 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. $\endgroup$ – Sam Hopkins Sep 12 at 19:29
  • 2
    $\begingroup$ This problem is discussed in John Riordan's Combinatorial Analysis but I don't have access to my copy right now. $\endgroup$ – Ira Gessel Sep 12 at 21:13
  • $\begingroup$ 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. $\endgroup$ – Mark Wildon Sep 14 at 9:53
  • $\begingroup$ I just discovered that this question is essentially a duplicate of mathoverflow.net/questions/144899/number-of-permutations. $\endgroup$ – Sam Hopkins Oct 1 at 23:19
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ For Ira's paper: people.brandeis.edu/~gessel/homepage/papers/3latin.pdf $\endgroup$ – Sam Hopkins Sep 14 at 1:03
  • $\begingroup$ 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.) $\endgroup$ – Ira Gessel Sep 14 at 2:34
1
$\begingroup$

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$.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Sam Hopkins Sep 14 at 0:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Max Alekseyev Sep 14 at 0:48
  • $\begingroup$ Thanks, makes sense! $\endgroup$ – Sam Hopkins Sep 14 at 0:56

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.