Counting / Inclusion Exclusion
Least You Need to Know: Inclusion-Exclusion
When two counted groups overlap, add the group sizes and then subtract the overlap once.
The least you need to know
- The sum rule works directly only for disjoint cases.
- If two sets overlap, the overlap gets counted twice when you add the set sizes.
- For two sets, |A ∪ B| = |A| + |B| - |A ∩ B|.
- Exactly one means left-only plus right-only.
- Neither means total minus the union.
Key notation
A ∪ B
in A or B or both
A ∩ B
in both A and B
|S|
size of set S
Tiny worked example
- Suppose 12 students take Python, 9 take Java, and 5 take both.\n- Adding 12 + 9 counts the 5 students in both classes twice.\n- So |Python ∪ Java| = 12 + 9 - 5 = 16.
Common mistakes
- Students often forget to subtract the overlap.
- Students often subtract the overlap twice.
- Students often confuse at least one with exactly one.
How to recognize this kind of problem
- If the problem mentions both groups and overlap, inclusion-exclusion is likely needed.
- At least one usually means union.
- Exactly one usually means exclude the overlap.
Next recommended lesson
Continue through this topic with Least You Need to Know: Permutations and Combinations.
Least You Need to Know: Permutations and CombinationsRelated lessons
Keep going with nearby lessons in the same topic.