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.
Best Answer
The mean number of fixed points is 1. This is very elementary.
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.
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.