Discrete Math › Section D · Counting › Topic D.3
Overlaps and inclusion-exclusion
The sum principle only works when cases do not overlap. Real questions overlap all the time, and the principle of inclusion-exclusion is the bookkeeping that counts every outcome exactly once.
In this topic
- When cases overlap
- Pictures first: Venn diagrams
- Inclusion-exclusion for two sets
- Worked example: bit strings with two conditions
- Inclusion-exclusion for three sets
- Worked example: multiples of 3, 5 or 7
- Worked example: filling a three-circle diagram
- The general pattern
- Overlaps hidden inside a product
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…