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

$$\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 $A_{1}, A_{2}, \ldots, A_{n}$ be finite sets. Deduce from part (a) the inclusion-exclusion formula for the size (or cardinality) of $\bigcup_{i} A_{i}$.

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