Inclusion-Exclusion
Count a union by adding singles, subtracting pairs, adding triples…
What is it?
The size (or probability) of a union of overlapping sets equals the alternating sum of the sizes of all intersections.
Why is it useful?
It handles "at least one of several overlapping conditions" and upper bounds in counting, including derangements.
When should you think of it?
Use it when conditions overlap and intersections are easier to count than the union.
Think of this method when…
- "Divisible by 2, 3 or 5" style unions
- At least one condition among several overlapping ones
- Upper bounds in a stars-and-bars count
- Counting surjections or derangements
Core idea
Each element in the union is counted exactly once after the alternating corrections.
Step-by-step playbook
- 1Name the "bad" or target sets .
- 2Count each single set, each pair, each triple…
- 3Combine with alternating signs.
- 4Subtract from the total if you want "none".
Worked example
Worked example
How many integers in are divisible by 2, 3 or 5?
- 1
Singles: .
- 2
Pairs (6, 10, 15): . Triple (30): .
- 3
Combine.
- Answer:
Common mistakes
- Stopping after the pairwise term.
- Wrong signs on odd and even intersection levels.
- Using it when the sets are disjoint (just add).
Would you use this method?
How many ways can 4 letters go into 4 envelopes with none in its own envelope?
Practice this method
13 QuantSolve questions are tagged with this method.
Practice this method