= Solution
For finite sets $A_1,\ldots,A_n$, the <inclusion-exclusion principle> states
$$
\left|\bigcup_{i=1}^{n}A_i\right|
=\sum_{\varnothing\ne I\subseteq\{1,\ldots,n\}}
(-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right|.
$$
To prove it, fix an element belonging to exactly $k$ of the sets. If $k=0$, it contributes zero to both sides. If $k\geq1$, its total weight on the right is
$$
\sum_{r=1}^{k}(-1)^{r+1}\binom kr
=1-(1-1)^k=1
$$
by the <binomial theorem>. Summing these pointwise contributions proves the formula.
Let the universe be the $n!$ <permutations> of $\{1,\ldots,n\}$, and let $A_j$ be the set of <permutations> fixing $j$. A <derangement> belongs to none of the $A_j$. If $k$ specified points must be fixed, the remaining $n-k$ points can be permuted in $(n-k)!$ ways, so every such $k$-fold intersection has that size. There are $\binom nk$ choices of the specified fixed points. Applying <inclusion-exclusion> to the complement of their union gives the <derangement counting formula>
$$
\boxed{f(n)=\sum_{k=0}^{n}(-1)^k\binom nk(n-k)!
=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.}
$$
The $k=0$ term is the whole universe. Since the exponential <power series> converges absolutely at $-1$,
$$
\boxed{\lim_{n\to\infty}\frac{f(n)}{n!}
=\sum_{k=0}^{\infty}\frac{(-1)^k}{k!}=e^{-1}.}
$$
The alternating-series remainder additionally gives $\left|f(n)/n!-e^{-1}\right|\leq1/(n+1)!$. Thus the fraction is the probability of no fixed points in a uniformly chosen <permutation> and approaches $1/e$.
Back to article page
