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.

3more comments