Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 12 / Solution

For finite sets $A_1,\dots ,A_n$, the inclusion-exclusion principle statesTo prove it, fix an element in exactly $r$ of the sets. If $r=0$, it contributes to neither side. If $r\ge 1$, its contribution to the right side isusing the binomial theorem. This is exactly its contribution to the union. Summing over the finite ambient union proves the formula. Equivalently, the proof is an identity of elementwise membership indicators, so no unproved rule for overlapping sets is being assumed.

Now let the ambient set be all $n!$ permutations, and let $E_i$ be those fixing element $i$. A set intersection of $k$ specified events $E_i$ has $(n-k)!$ elements: the specified elements are fixed and the others may be permuted freely. Apply inclusion-exclusion to the complement of the union of these events. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ possible choices of the fixed positions, hence the derangement count isThe $k=0$ term counts the whole ambient set before subtraction; it is not an omitted empty intersection. The formula also gives $f(0)=1$ and $f(1)=0$.

Dividing by the factorial and using the convergent power series for the exponential function at $-1$ givesThe alternating-series estimate supplies the explicit error bound $|f(n)/n!-e^{-1}|\le 1/(n+1)!$. Thus the limiting proportion is established, not merely identified from the first few values.