Numbers and Sets | Part IA, 2002

(a) Let SS be a finite set, and let P(S)\mathbb{P}(S) be the power set of SS, that is, the set of all subsets of SS. Let f:P(S)Rf: \mathbb{P}(S) \rightarrow \mathbb{R} be additive in the sense that f(AB)=f(A)+f(B)f(A \cup B)=f(A)+f(B) whenever AB=A \cap B=\varnothing. Show that, for A1,A2,,AnP(S)A_{1}, A_{2}, \ldots, A_{n} \in \mathbb{P}(S),

f(iAi)=if(Ai)i<jf(AiAj)+i<j<kf(AiAjAk)+(1)n+1f(iAi)\begin{aligned} f\left(\bigcup_{i} A_{i}\right)=\sum_{i} f\left(A_{i}\right)-\sum_{i<j} f\left(A_{i} \cap A_{j}\right) &+\sum_{i<j<k} f\left(A_{i} \cap A_{j} \cap A_{k}\right) \\ &-\cdots+(-1)^{n+1} f\left(\bigcap_{i} A_{i}\right) \end{aligned}

(b) Let A1,A2,,AnA_{1}, A_{2}, \ldots, A_{n} be finite sets. Deduce from part (a) the inclusion-exclusion formula for the size (or cardinality) of iAi\bigcup_{i} A_{i}.

(c) A derangement of the set S={1,2,,n}S=\{1,2, \ldots, n\} is a permutation π\pi (that is, a bijection from SS to itself) in which no member of the set is fixed (that is, π(i)i\pi(i) \neq i for all ii ). Using the inclusion-exclusion formula, show that the number dnd_{n} of derangements satisfies dn/n!e1d_{n} / n ! \rightarrow e^{-1} as nn \rightarrow \infty.

Typos? Please submit corrections to this page on GitHub.