Recall that a [derangement](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Lov%C3%A1sz_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. 



Non-enumerative proof that there are many derangements?
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](http://www.crafoordprize.se/prizesawarded.4.2f692b3510dbfce3396800010039.html).


