Concept
Generalization of |A∪B| = |A|+|B|−|A∩B|. Counting unions by alternating sums of intersections — the workhorse of combinatorics.
Understand it in one breath
Subtract what you double-counted. When students join multiple clubs, this is how you count each person once. The fact that the probability of a derangement (everyone gets a gift that isn't theirs) is 1/e ≈ 36.8% comes directly from this principle.
At a glance
Random gift exchange among k people | Probability that nobody receives their own gift |
|---|---|
n = 2 | 1/2 = 0.5 |
n = 3 | 2/6 ≈ 0.333 |
n = 4 | 9/24 = 0.375 |
n = 5 | 44/120 ≈ 0.367 |
n = 10 | 1334961/10! ≈ 0.3679 |
n → ∞ | 1/e ≈ 0.36788 |
The inclusion–exclusion principle produces the alternating sum ∑(−1)ᵏ/k!. Because it is part of the Taylor expansion of e, it converges to 1/e. A simple counting principle summons e.
Key formula
|∪Aᵢ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − ⋯
Modern applications
Probability and expectation calculations, database UNION queries, and counting derangements and other overlapping cases.
Beyond MathVoyage
Loading…