The Inclusion-Exclusion Principle
When counting elements in the union of sets, simply adding sizes overcounts elements in the intersection. Inclusion-exclusion corrects for this.
Two Sets:
|A ∪ B| = |A| + |B| - |A ∩ B|
Three Sets:
|A ∪ B ∪ C| = |A| + |B| + |C|
- |A ∩ B| - |A ∩ C| - |B ∩ C|
+ |A ∩ B ∩ C|Example: Survey Problem
In a survey of 100 students: 60 like Math, 50 like Science, 40 like English, 20 like Math and Science, 15 like Math and English, 10 like Science and English, and 5 like all three. How many like at least one subject?
|M ∪ S ∪ E| = 60 + 50 + 40 - 20 - 15 - 10 + 5 = 110... wait
Let me recalculate:
|A ∪ B ∪ C| = 60 + 50 + 40 - 20 - 15 - 10 + 5 = 110
But there are only 100 students! This means some students
like none of the three subjects... or the data is inconsistent.
Correct: 110 means 110 is the count, so 100 - 110 = -10
meaning 10 students like none (if we had 100 total).
Actually: Like at least one = 110, so 0 like none.
But we only have 100 students. The problem data must ensure consistency.General Formula
For n sets A₁, A₂, ..., Aₙ:
|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ|
+ Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| - ...
+ (-1)ⁿ⁺¹|A₁ ∩ A₂ ∩ ... ∩ Aₙ|
Application: Counting integers divisible by 2, 3, or 5 up to N
Use inclusion-exclusion with multiples of each number.