Inclusion-Exclusion Principle
What You'll Learn
You'll learn how to count elements in the union of multiple sets without counting the same element more than once.
The Core Problem
Imagine you're counting students who take either Math or CS. If you simply add "students in Math" plus "students in CS," you've double-counted everyone taking both classes!
The Inclusion-Exclusion Principle fixes this by systematically correcting for overlaps.
The Formula
For two sets A and B:
|A ∪ B| = |A| + |B| - |A ∩ B|
We include the individual sets, then exclude the intersection to remove the double-count.
For three sets A, B, and C:
|A ∪ B ∪ C| = |A| + |B| + |C|
- |A ∩ B| - |A ∩ C| - |B ∩ C|
+ |A ∩ B ∩ C|
Notice the pattern: add singles, subtract pairs, add triples.
Why It Works
When you add |A| + |B| + |C|, elements in two sets get counted twice, and elements in all three get counted three times. Subtracting the pairwise intersections fixes the doubles, but now elements in all three have been removed too many times (once for each pair), so we add back |A ∩ B ∩ C|.
Example
How many integers from 1 to 100 are divisible by 2 or 3?
- Divisible by 2: 50 numbers
- Divisible by 3: 33 numbers
- Divisible by both (6): 16 numbers
Answer: 50 + 33 - 16 = 67 numbers
Key Takeaway: The Inclusion-Exclusion Principle counts union sizes by alternating addition and subtraction of intersections—ensuring every element is counted exactly once.