Counting overlapping sets
When sets overlap, simply adding their sizes overcounts the shared elements. The inclusion exclusion principle fixes this with an alternating pattern of additions and subtractions.
The pattern
For the union of several sets:
- Add the size of each individual set.
- Subtract the size of every pairwise intersection, since each was counted twice.
- Add back every triple intersection, which the subtractions removed too often.
- Continue alternating signs through all higher intersections.
Each element ends up counted exactly once, no matter how many sets it belongs to, because the alternating contributions cancel to a single net count.
Where it appears
- Counting integers below n divisible by at least one of several primes.
- Counting derangements, permutations where nothing sits in its original place.
- Solving constraint problems by counting the complement, the arrangements that violate at least one rule, then subtracting.
The price is that with many sets the number of intersection terms grows quickly, so it suits problems with few constraints or where most intersections are empty.
Key idea
Inclusion exclusion counts a union by adding sets, subtracting pairwise overlaps, re adding triples, and alternating onward, so every element is tallied exactly once despite overlaps.