47
$\begingroup$

Recall that a derangement is a permutation $\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}$ with no fixed points: $\pi(j) \neq j$ for all $j$. A classical application of the inclusion-exclusion principle tells us that out of all the $n!$ permutations, a proportion $1/e + o(1)$ of them will be derangements. Indeed, by computing moments (or factorial moments) or using generating function methods, one can establish the stronger result that the number of fixed points in a random permutation is asymptotically distributed according to a Poisson process of intensity 1.

In particular, we have:

Corollary: the proportion of permutations that are derangements is bounded away from zero in the limit $n \to \infty$.

My (somewhat vague) question is whether there is a "non-enumerative" proof of this corollary that does not rely so much on exact combinatorial formulae. For instance, a proof using the Lovasz Local Lemma would qualify, although after playing with that lemma for a while I concluded that there was not quite enough independence in the problem to make that lemma useful for this problem.

Ideally, the non-enumerative proof should have a robust, "analytic" nature to it, so that it would be applicable to other situations in which one wants to lower bound the probability that a large number of weakly correlated, individually unlikely events do not happen (much in the spirit of the local lemma). My original motivation, actually, was to find a non-enumerative proof of a strengthening of the above corollary, namely that given $l$ permutations $\pi_1,\ldots,\pi_l: \{1,\ldots,n\} \to \{1,\ldots,n\}$ chosen uniformly and independently at random, where $l$ is fixed and $n$ is large, the probability that these $l$ permutations form a $2l$-regular graph is bounded away from zero in the limit $n \to \infty$. There is a standard argument (which I found in Bollobas's book) that establishes this fact by the moment method (basically, showing that the number of repeated edges or loops is distributed according to a Poisson process), but I consider this an enumerative proof as it requires a precise computation of the main term in the moment expansion.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Do you think the following elementary argument helps: The difference between the num of odd and even derangements is $(-1)^{n-1}(n-1)$, and this can be shown by evaluating a nice determinant, as shown in math.hmc.edu/~benjamin/papers/derangement.pdf $\endgroup$
    – Suvrit
    Commented Jan 19, 2012 at 18:21
  • 1
    $\begingroup$ It feels like there should be some sort of proof by showing that conditioning a random permutation on $\pi(i) \neq i$ for $1 \leq i \leq j-1$ makes it more likely that $\pi(j) \neq j$. This seems intuitive enough (assuming that $\pi(i) \neq i$ makes it more likely that some $i$ has $\pi(i)=j$), but I don't see an obvious proof that doesn't use the same counting techniques that would already get you the full formula. $\endgroup$
    – Kevin P. Costello
    Commented Jan 19, 2012 at 19:30
  • $\begingroup$ Perhaps this is just deferring the enumeration part of the proof, but what about considering the proportion of cycle structures which have no fixed points? Perhaps that is bounded away from zero, and can be used in an inductive proof that the proportion of derangements is also bounded away from zero. Gerhard "Ask Me About System Design" Paseman, 2012.01.19 $\endgroup$
    – Gerhard Paseman
    Commented Jan 20, 2012 at 0:05
  • $\begingroup$ So would you like some cobinatorial way to collect permutations to groups of at most 10 permutations where each group has at least one derangement? I wonder if there's a proof like that. $\endgroup$
    – Zsbán Ambrus
    Commented Jan 20, 2012 at 9:18
  • $\begingroup$ A variation on Suvrit's argument above shows that there are at least roughly $(n−1)^{n/2}$ permutations without fixed points: Choose a Hadamard matrix of size $n$ (supposed to be divisible by 4) which is of the form $A+Id$ with $A$ antisymmetric (such matrices exist for example if $n=p+1$ where $p$ is a prime of the form $4k+3$). The number of derangement is of course at least equal to the absolute value of the determinant $\pm (n−1)^{n/2}$ of the matrix $A$. $\endgroup$
    – Roland Bacher
    Commented Jan 24, 2012 at 11:41

6 Answers 6

Reset to default
64
$\begingroup$

  1. The mean number of fixed points is 1. This is very elementary.

  2. Consider the operation of rotating three values around: $p(i)\to p(j)\to p(k)\to p(i)$. Given a permutation with no fixed points, there are $n^2-O(n)$ rotations that create from it a permutation with exactly one fixed point. Given a permutation with exactly one fixed point, there are $n^2-O(n)$ rotations that create from it a permutation with no fixed points.

  3. From (2), the numbers of permutations with 0 and 1 fixed points are the same to $O(1/n)$ relative error. Combining this with (1) shows that the fraction of permutations with no fixed points is at least $\frac13-O(1/n)$.

This is the switching method and it can be used in extremely many circumstances. By continuing to increase the number of fixed points by further switchings, step 1 could be avoided.

Incidentally, congratulations to Terry and Jean Bourgain.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I guess you rotate three elements (instead of just 2) so that the claim in (2) will hold for all permutations, not just almost all? But this is not necessary in order to reach the conclusion in (3). I was thinking about swapping the first element with the unique fixed point, and inversely swapping the first element to its proper place. This provides an almost-bijection between derangements and permutations with exactly one fixed point. $\endgroup$
    – Johan Wästlund
    Commented Jan 20, 2012 at 16:13
  • $\begingroup$ @Johan, I think what you're saying is along the lines of what I added to my answer after seeing Brendan's solution. $\endgroup$
    – Barry Cipra
    Commented Jan 20, 2012 at 16:33
  • $\begingroup$ Thanks, this is exactly the sort of thing I was looking for - among all the methods proposed, this seems to be the most robust (in particular, it seems to easily give the second claim in the question, namely that l random permutations generate a 2l-regular graph with probability bounded away from zero, by switching away the problematic edges). $\endgroup$
    – Terry Tao
    Commented Jan 20, 2012 at 17:14
  • $\begingroup$ @Johan, Yes, to get a lower bound switching just two elements will suffice. Switching three gives easier counting if bounds in both directions are required. $\endgroup$
    – Brendan McKay
    Commented Jan 21, 2012 at 0:09
  • 1
    $\begingroup$ In case anyone trips over the same mental block I had: I found Step 2 easier to follow when I replaced the last few words by, "...that create it from a permutation with no fixed points." $\endgroup$
    – Timothy Chow
    Commented Jan 23, 2012 at 19:24
21
$\begingroup$

I'm not sure this qualifies, but here goes.

It doesn't take any fancy enumerations to show that the average number of fixed points is 1: Among the $n!$ permutations of $n$ objects, each object is fixed by $(n-1)!$ permutations, for a total of $n!$ fixed points. So if the probability of having no fixed points tends to 0 (for some subsequence of $n$'s), then the probability of having more than one fixed point must also tend to 0. This seems like it should be easily disprovable nonsense.

Added 1/20/12 Brendan McKay's "switching method" answer nails the nonsense. Here's a slight variation on his argument.

Assume you're at a large $n$ where, say 99 percent (or more) of the permutations have exactly one fixed point. (That was the thrust of my intial posting: If the fraction of permutations with no fixed points is close to 0, then the fraction with exactly one fixed point must be close to 1.) Then there's at least one object that's fixed by at least $.99(n-1)!$ permutations having no other fixed points. If you take each of these permutations and switch the fixed object with each of the other $n-1$ objects, you've created $.99(n-1)!(n-1) = .99n!(1-1/n)$ distinct permutations with no fixed points. Since $n$ is large, this is almost $.99n!$ itself, so certainly greater than $.5n!$. But $.99+.5 > 1$, which gives us more than $n!$ permutations on $n$ objects.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ The first three moments for the number of fixed points suffice. (The three first terms from inclusion-exclusion give a lower bound of $1/3$ for the fraction of derangements. $\endgroup$
    – Omer
    Commented Jan 19, 2012 at 21:05
  • 1
    $\begingroup$ Actually the average number of fixed points requires non computation at all: for any finite group acting on a set, the average number of fixed points is equal to the number of orbits (Burnside's lemma). $\endgroup$
    – Marc van Leeuwen
    Commented Jan 21, 2012 at 11:42
  • 7
    $\begingroup$ It doesn't even have anything to do with group theory per se. The probability that a random permutation fixes any particular element is $1/n$. So the expected number of fixed points is 1, by linearity of expectation. $\endgroup$
    – Timothy Chow
    Commented Jan 23, 2012 at 18:32
17
$\begingroup$

L. Lu and L. A. Szekely have successfully applied the Lopsided (i.e. Negative Dependency Graph) Lovasz Local Lemma to this problem.

A negative dependency graph is as a dependency graph except that independence is replaced with the inequality $$ \Pr\left(A_k \middle\vert \bigwedge_{i \in S} A_i\right) \leq \Pr(A_k) $$ for any fixed event $A_k$ and collection $S$ of non-neighbors of $A_k$. Erdos and Spencer showed the Lovasz Local Lemma holds with negative dependency graphs in place of dependency graphs.

Let $\Omega$ be the probability space of all perfect matchings of $K_{n,n}$ equipped with the uniform distribution. For a partial matching $M$ of $K_{n,n}$, define the event $$ A_M = \{M^\prime \in \Omega \mid M \subseteq M^\prime\} $$ (all perfect matching that contain the partial matching $M$).

Given a collection $\mathcal{M}$ of partial matchings of $K_{n,n}$, construct a graph with vertex set $\{A_M \mid M \in \mathcal{M}\}$ and set two matchings adjacent if their union is not again a matching. L. Lu and L. A. Szekely showed this graph is a negative dependency graph.

Finally we can address the problem at hand. Let the partite sets of $K_{n,n}$ be $\{1, \dots, n\}$ and $\{1^\prime, \dots, n^\prime\}$. For $1 \leq i \leq n$, let $M_i$ be the one-edge matching $ii^\prime$. Viewing perfect matchings of $K_{n,n}$ as permutations of an $n$-element set, the event $\bigwedge_{i=1}^n \overline{A_{M_i}}$ contains precisely those permutations not having a fixed point. Choosing $x_i = \frac{1}{n}$ for the purposes of the Lopsided Lovasz Local Lemma, we get $$ \Pr\left( \bigwedge_{i=1}^n \overline{A_{M_i}} \right) \geq \left(1 - \frac{1}{n}\right)^n, $$ which converges to $\frac{1}{e}$ as $n \rightarrow \infty$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Great! I'm happy to see that my initial puzzlement that the local lemma seemed to "want" to help with this problem, but was unable to due to the independence requirements in the hypothesis of the standard formulation of this lemma, was resolved satisfactorily. $\endgroup$
    – Terry Tao
    Commented Oct 12, 2012 at 20:27
12
$\begingroup$

The fraction $f(n)$ of permutations of $n$ letters that are derangements satisfies the recurrence $f(n) - f(n-1) = \frac{-1}{n} (f(n-1) - f(n-2))$ with $f(0)=1$ and $f(1)=0$. It is easy to see from this that $f(2k) > f(2k+1)>f(2k-1)$, and in particular $f(n) \ge f(3) > 0$ for $n \ge 2$.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Why is the first sentence true? $\endgroup$
    – Igor Rivin
    Commented Jan 19, 2012 at 19:43
  • 1
    $\begingroup$ To produce a derangement $X$ of $\{1 \ldots n\}$, first select $X(1)$ from $\{2 \ldots n\}$ ($n−1$ ways to do this), then either have $X(X(1))=1$ and make a derangement of the remaining $n−2$ items, or take a derangement $Y$ of $\{2 \ldots n\}$, and if $Y(k)=X(1)$ let $X(k)=1$ and $X(i)=Y(i)$ for $i \in \{2 \ldots n\} \backslash \{k\}$. Thus the number $D(n)$ of derangements of $n$ letters satisfies $D(n)=(n−1)(D(n−2)+D(n−1))$. The number $P(n) = n!$ of permutations of $n$ letters also satisfies $P(n)=(n−1)(P(n−2)+P(n−1))$... $\endgroup$
    – Robert Israel
    Commented Jan 20, 2012 at 8:26
  • $\begingroup$ Now $$ \frac{f(n) - f(n-1)}{f(n-1) - f(n-2)} = \frac{\frac{D(n-2)+D(n-1)}{P(n-2)+P(n-1)} - \frac{D(n-1)}{P(n-1)}}{\frac{D(n-1)}{P(n-1)} - \frac{D(n-2)}{P(n-2)}} = - \frac{P(n-2)}{P(n-1)+P(n-2)} = -\frac{1}{n}$$ $\endgroup$
    – Robert Israel
    Commented Jan 20, 2012 at 8:31
  • $\begingroup$ Actually this last bit of magic is not needed. From the fact that $\frac{D(n)}{P(n)} = \frac{D(n-2)+D(n-1)}{P(n-2)+P(n-1)}$ with the $D$'s and $P$'s positive we get that $f(n)$ is between $f(n-1)$ and $f(n-2)$, and then $f(2k) \ge f(2k+1) \ge f(2k-1)$. $\endgroup$
    – Robert Israel
    Commented Jan 20, 2012 at 16:06
12
$\begingroup$

The number of derangements of an $n$-set is the number of perfect matchings in the bipartite complement of $n$ disjoint copies of $K_2$. The rook polynomial of $nK_2$ is $(x-1)^2$ and so the number of matchings in the complement is equal to $$ \int_0^\infty (x-1)^n e^{-x}\ dx. $$ (I am not sure if this is along the lines you want, but it is a nice formula for asymptotic purposes.) This approach is used in anger in C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, J. Combinatorial Theory, Ser. B, 48 (1990) 19-44. (Also on Brendan's web page.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ It is used in anger? $\endgroup$
    – Steven Gubkin
    Commented Aug 30, 2012 at 14:21
  • 1
    $\begingroup$ It's a figure of speech. $\endgroup$
    – Chris Godsil
    Commented Aug 30, 2012 at 18:31
  • $\begingroup$ Apparently it is a Britishism meaning "used in earnest". See english.stackexchange.com/questions/30939/…. $\endgroup$
    – I. J. Kennedy
    Commented Nov 5, 2012 at 2:18
  • 3
    $\begingroup$ not just British. $\endgroup$
    – Chris Godsil
    Commented Nov 5, 2012 at 13:26
5
$\begingroup$

There is a very elegant approach to derangements

D.M. Jackson, Laguerre polynomials and derangements, Math. Proc. Camb. Phil. Soc., 80 (1976), 213–214.

I am not sure it fits precisely your criteria, but I found Jackson's approach very useful for various asymptotic estimates.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .