= Solution
For finitely many finite sets $A_1,\ldots,A_k$, the <inclusion-exclusion principle> states
$$
\boxed{\left|\bigcup_{i=1}^kA_i\right|
=\sum_{\varnothing\ne J\subseteq\{1,\ldots,k\}}
(-1)^{|J|+1}\left|\bigcap_{j\in J}A_j\right|.}
$$
To see why, an element belonging to exactly $t\geq1$ of the sets contributes
$$
\sum_{j=1}^t(-1)^{j+1}\binom tj=1
$$
by the <binomial theorem>. Elements outside the union contribute zero. Equivalently, if these sets lie in a finite universe $U$, the number avoiding all of them is
$$
|U|+\sum_{\varnothing\ne J}(-1)^{|J|}
\left|\bigcap_{j\in J}A_j\right|.
$$
Back to article page
