November 4th
Today I learned the asymptotic formula for derangements. Fix a nonnegative integer $n.$ We are interested in counting the number permutations on $n$ letters which fix no elements. One way symbolically heavy but conceptually easy way to do this is with the principle of inclusion-exclusion on the complement.
Explicitly, we'll count the number of permutations which fix at least one element. For this, we define $S_\bullet$ to be the set of permutations which fix the element $\bullet,$ implying we are interested in\[\left|\bigcup_{k=1}^nS_k\right|.\]Using the principle of inclusion-exclusion, this is\[\left|\bigcup_{k=1}^nS_k\right|=\sum_{m=1}^n(-1)^{m+1}\sum_{\substack{T\subseteq[1,n]\\|T|=m}}\left|\bigcap_{t\in T}S_t\right|.\]Now, these intersections are actually quite nice because the number of permutations fixing some given $m$ elements is the number of permutations of the remaining elements, which is $(n-m)!.$ Then the number of possible subsets comes out to $\binom nm,$ so this collapses into\[\left|\bigcup_{k=1}^nS_k\right|=\sum_{m=1}^n(-1)^{m+1}\cdot\binom nm(n-m)!=n!\sum_{m=1}^n\frac{(-1)^{m+1}}{m!}.\]
To finish, we return the question of derangements. The above is the number of permutations which aren't derangements, so subtracting from $n!$ tells us we want\[n!-n!\sum_{m=1}^n\frac{(-1)^{m+1}}{m!}=\boxed{n!\sum_{m=0}^n\frac{(-1)^m}{m!}}.\]Of particular interest is that we see that the fraction of permutations which are derangements is\[\frac{n!}{n!}\sum_{m=0}^n\frac{(-1)^m}{m!}=\sum_{m=0}^n\frac{(-1)^m}{m!}.\]As $n\to\infty,$ this rapidly converges to $e^{-1}\approx0.368.$ So a positive and reasonably sized proportion of all permutations are derangements, which is nice.