Inclusion–Exclusion

|A ∪ B| = |A| + |B| - |A ∩ B| — alternate signs by intersection size.

The idea

Inclusion–exclusion counts the union of overlapping sets from the sizes of the sets and of their intersections.

Theorem (Inclusion–exclusion).

For any two finite sets, $|A \cup B| = |A| + |B| - |A \cap B|,$ and for any three, $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$

Adding the sizes of the sets counts a union correctly only when the sets are disjoint. When they overlap, an element lying in several of the sets is added once for each of them, so the sum overshoots, and the remaining terms correct it: subtract the pairwise intersections, whose elements were counted twice; the subtraction removes too much from an element lying in all three sets, so add the triple intersection back. With more sets the alternation continues, the $j$-fold intersections entering with sign $(-1)^{j+1}$, so the signs run $+, -, +, -$ as $j$ increases.

The formula applies whenever a condition is easier to count one piece at a time than all at once. Counting the integers up to $n$ divisible by at least one of several primes, for example, is a sum over the primes with the overlaps corrected.

Ways to work on it

• Walkthrough. Two-set inclusion-exclusion, plus the alternating-sign pattern.
• Proof. See why you subtract the overlap — count each region once.
• Practice. Two-set count: |A ∪ B| for friendly numbers.
• Hardest. Count the integers that escape several overlapping divisibility conditions.

Not sure where to start? Take the ten-question placement test.