TheoremProved

Inclusion–exclusion principle

Statement

For finite sets $A_1,\dots,A_n$ , $\Big|\bigcup_{i=1}^n A_i\Big| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n|$ .

Why is it true?

Simply adding the sizes of overlapping sets double-counts elements that lie in more than one set. Subtracting the pairwise overlaps corrects the double-counting, but now triple overlaps have been removed too many times, so they must be added back, and so on, alternating sign until every element of the union is counted exactly once.

Proof sketch

Fix an element $x$ in the union that belongs to exactly $m \ge 1$ of the sets. Show that its net contribution to the alternating sum is $\sum_{j=1}^{m} (-1)^{j-1}\binom{m}{j}$ , which by the binomial theorem applied to $(1-1)^m = 0$ equals $1$ . Since every element of the union contributes exactly $1$ and elements outside the union contribute $0$ , the alternating sum equals $|\bigcup A_i|$ .

Topics that use this theorem

Inclusion–exclusion principle

Related theorems

Pigeonhole principle Binomial theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

J. H. van Lint, R. M. Wilson (2001). A Course in Combinatorics