= Solution
For <finite sets> $A_1,\ldots,A_r$, the <inclusion-exclusion principle> states
$$
\boxed{\left|\bigcup_{i=1}^rA_i\right|=\sum_{\varnothing\ne J\subseteq\{1,\ldots,r\}}(-1)^{|J|+1}\left|\bigcap_{j\in J}A_j\right|.}
$$
To prove it, count the contribution of one element. If it belongs to exactly $q\geq1$ of the <sets>, it is counted by $\binom qk$ intersections of size $k$. Its total weight is
$$
\sum_{k=1}^q(-1)^{k+1}\binom qk=1-(1-1)^q=1,
$$
using the <binomial theorem>. An element belonging to none contributes zero. Summing these weights gives the <cardinality> of the union and proves the <inclusion-exclusion principle>. Equivalently, within a finite ambient <set> $U$, the number avoiding every $A_i$ is the sum over all $J$, with sign $(-1)^{|J|}$ and the empty intersection interpreted as $U$.
Back to article page
