Past exam of the mathematics course of the University of Cambridge / 2002 / ia / Paper 4 / 6F (Numbers and Sets)

First, finite additivity of a set function gives $f(\varnothing )=0$, since $f(\varnothing )=2f(\varnothing )$. Put $w_s=f(\{s\})$. Decomposing any subset into its singleton elements and using induction gives $f(A)={\sum }_{s\in A}{w}_s$. Fix $s\in S$ and let $r$ be the number of sets $A_i$ containing it. Its total coefficient in the alternating intersection sum is zero if $r=0$, and otherwise isby the binomial theorem. These are exactly the coefficients in $f({\bigcup }_i{A}_i)$. Summing against $w_s$ proves the required inclusion-exclusion principle for the additive set function, including signed weights.

Take the finite ambient set $S={\bigcup }_i{A}_i$ and the additive set function $f(A)=|A|$. Disjoint subsets have additive cardinality, so (a) applies and givesThis is the finite inclusion-exclusion principle.

In the set of all $n!$ permutations, let $A_i$ consist of those fixing $i$. For a prescribed collection of $k$ fixed points, its intersection has $(n-k)!$ members. Applying the inclusion-exclusion principle to the complement of ${\bigcup }_i{A}_i$ gives the number of derangements:The convergent power series for the exponential function at $-1$ therefore gives $\boxed{d_n/n!⟶e^{-1}}$.