= Solution
For finite <sets> $C_1,\ldots,C_k$, the <inclusion-exclusion principle> states
$$
\boxed{\left|\bigcup_{j=1}^kC_j\right|
=\sum_{\varnothing\ne J\subseteq[k]}(-1)^{|J|+1}
\left|\bigcap_{j\in J}C_j\right|.}
$$
In a finite ambient <set> $\Omega$, its equivalent complement form is
$$
\left|\Omega\setminus\bigcup_{j=1}^kC_j\right|
=\sum_{J\subseteq[k]}(-1)^{|J|}
\left|\bigcap_{j\in J}C_j\right|,
$$
where the intersection for $J=\varnothing$ means $\Omega$. To see the counting mechanism, an element in exactly $r\ge1$ of the <sets> has coefficient $\sum_{i=1}^r(-1)^{i+1}\binom ri=1$, by the <binomial theorem>; an element in none has coefficient zero in the union formula.
Back to article page
