= Inclusion-exclusion principle
{wiki}
= Inclusion-exclusion
{synonym}
For <finite sets> $A_1,\ldots,A_n$, the cardinality of their <union> is
$$
\left|\bigcup_{i=1}^n A_i\right|=\sum_{\varnothing\neq J\subseteq\{1,\ldots,n\}}(-1)^{|J|+1}\left|\bigcap_{j\in J}A_j\right|.
$$
Add the individual <cardinalities>, subtract pairwise <intersection> counts, add triple <intersection> counts, and continue alternating. This is useful whenever one object can satisfy several conditions: a search result can match several filters, or a <permutation> can have several forbidden <fixed points>.
Among the <integers> from 1 to 30, let $A$ contain the multiples of 2 and $B$ the multiples of 3. Then $|A|=15$, $|B|=10$, and $|A\cap B|=5$, because their common multiples are the multiples of 6. The naive sum $25$ counts those five twice; the correct <union> size is \b[$15+10-5=20$]. The regions contain ten in $A$ alone, five in both, five in $B$ alone, and ten in neither.
\Image[/inclusion-exclusion-counting.png]
{title=Subtracting overlap counts each selected <integer> once; a third <divisibility> condition requires adding the triple overlap back}
Add a third <set> $C$ containing the multiples of 5. Its size is 6; the three pairwise <intersections> have sizes $5,3,2$; and the triple <intersection> contains only 30. The <inclusion-exclusion principle> gives \b[$15+10+6-5-3-2+1=22$] integers divisible by at least one of 2, 3, and 5.
The alternating corrections have a local explanation. An object belonging to exactly $r\geq1$ of the <sets> is counted $\binom r1-\binom r2+\cdots+(-1)^{r+1}\binom rr=1$ times, by the <binomial theorem> applied to $(1-1)^r$. An object in none contributes zero. Thus overlapping descriptions are repaired without requiring the <sets> themselves to be disjoint. For <probability>, the same calculation applies to event probabilities in place of <cardinalities>, giving the <inclusion-exclusion principle for probabilities>.
Back to article page
