A derangement is a permutation $\sigma$ of $\{1,2,3,\dots,n\}$ such that $\sigma(i) \neq i$ for every $i$. A common application of inclusion/exclusion in undergraduate combinatorics and probability classes is to compute the number of derangements, and in the process show that the probability a random permutation is a derangement approaches $\frac{1}{e}$ for large $n$.
There's also a "standard" intuition for this probability, which goes roughly as follows: Let $E_i$ be the event that $\sigma(i)=i$.
1) For a given $i$, the probability of $E_i$ is exactly $\frac{1}{n}$.
2) If $n$ is large, than these events should be "nearly" independent ($E_i$ occurring means that $\sigma(i) \neq j$, making it a tiny bit more likely that $\sigma(j)=j$, but this shouldn't have much of an effect for large $n$), so we'd expect the probability none of the $E_i$ occur to be roughly $\left(1-\frac{1}{n}\right)^n$.
3) For large $n$, $\left(1-\frac{1}{n} \right)^n \approx \frac{1}{e}$.
Now the last approximation alone already has an error proportional to $\frac{1}{n}$. What's suprising then is that, after working through the inclusion/exclusion, you find that the probability is not just approximately $\frac{1}{e}$, but incredibly close — the error is less than $\frac{1}{(n+1)!}$.
Is there some alternative intuitive explanation for the $\frac{1}{e}$ asymptotic probability that gives a sense of why the convergence is so fast?
Best Answer
In fact a much stronger $e$-related statement is true: let $X_i$ denote the number of $i$-cycles in a random permutation on $n$ elements. Then for fixed $k$, as $n \to \infty$ the random variables $X_1, X_2, ... X_k$ are asymptotically independently Poisson with rates $1, \frac{1}{2}, ... \frac{1}{k}$. This observation about derangements is a special case applied to $X_1$. See this blog post for details, which proves this fact as a corollary of the exponential formula. The convergence rate is presumably also controlled by the exponential formula but I haven't worked out the details.