The sum rule only works for disjoint cases. When sets overlap, adding their sizes counts the shared elements more than once. The inclusion-exclusion principle corrects this systematically: add the sizes, subtract the pairwise overlaps, add back the three-way overlaps, and so on. It is a simple tool that solves counting problems that would otherwise be awkward.
Two sets
|A ∪ B| = |A| + |B| − |A ∩ B|
Elements in both A and B are counted twice by |A| + |B|; subtracting |A ∩ B| counts them only once.
Example: in a company 40 employees use a company laptop, 25 use a company phone and 10 use both. How many use at least one of the two devices? 40 + 25 − 10 = 55.
Three sets
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Why add back the triple intersection? Follow an element that lies in all three sets: it is counted 3 times in the first group of terms, subtracted 3 times in the pairwise intersections, and would therefore end up counted 0 times. The last term brings it back to 1.
Example: numbers divisible by 2, 3 or 5
How many numbers between 1 and 1000 are divisible by at least one of 2, 3 and 5?
The number of multiples of d between 1 and 1000 is ⌊1000/d⌋, and a number is divisible by two distinct primes if and only if it is divisible by their product.
| Term | Calculation | Value |
|---|---|---|
| |A₂| + |A₃| + |A₅| | 500 + 333 + 200 | 1033 |
| − pairs | − (166 + 100 + 66) | − 332 |
| + triple | + ⌊1000/30⌋ | + 33 |
| Total | 734 |
Consequently the numbers between 1 and 1000 divisible by none of 2, 3 and 5 number 1000 − 734 = 266.
The general formula
For n sets A₁, …, Aₙ:
|A₁ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| − … + (−1)ⁿ⁺¹ |A₁ ∩ … ∩ Aₙ|
The sums range over every choice of 1, 2, 3, … distinct sets. The signs alternate. Correctness is proved by observing that an element belonging to exactly m sets is counted C(m, 1) − C(m, 2) + C(m, 3) − … times, and this alternating sum equals exactly 1.
Often what you want is the complement, the elements that lie in none of the sets:
|none| = |U| − |A₁ ∪ … ∪ Aₙ|
Application: derangements
A derangement is a permutation in which no element stays in its place. The classic problem: n people leave their hats at the door and pick them up at random; in how many ways does nobody get their own hat back?
Let Aᵢ be the set of permutations in which person i gets their own hat. Fixing k people in place leaves (n − k)! permutations of the rest, and there are C(n, k) ways to choose the k people. By inclusion-exclusion, the number of permutations with no fixed points is:
Dₙ = n! − C(n,1)(n − 1)! + C(n,2)(n − 2)! − … = n! · (1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!)
The first values are D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9, D₅ = 44. The sum in parentheses converges quickly to 1/e ≈ 0.3679, so the fraction of permutations with no fixed points is about 36.8% even for small n, and stays practically constant as n grows.
A concrete application: in a draw for a gift exchange, the probability that nobody picks their own name is about 0.37 regardless of the number of participants. That is why systems that organise exchanges of this kind do not simply shuffle once, but reshuffle until they obtain a derangement, or build a cycle directly.
Application: Euler's totient function
Euler's totient function φ counts the integers between 1 and n that share no factors with n. If the distinct prime factors of n are p₁, …, pᵣ, inclusion-exclusion over the multiples of each prime gives:
φ(n) = n · (1 − 1/p₁) · (1 − 1/p₂) · … · (1 − 1/pᵣ)
Example: 1000 = 2³ · 5³, so φ(1000) = 1000 · 1/2 · 4/5 = 400. The function φ is central to modular arithmetic, because it counts the elements that have an inverse modulo n.
A check in Python
For small values it is always worth checking by brute force:
n = 1000
direct = sum(1 for x in range(1, n + 1)
if x % 2 == 0 or x % 3 == 0 or x % 5 == 0)
assert direct == 734
In short
- For two sets: |A ∪ B| = |A| + |B| − |A ∩ B|.
- With more sets, add and subtract alternately the intersections of 1, 2, 3, … sets.
- Often the complement is what matters: the elements in none of the sets.
- About 37% of permutations have no fixed points, whatever n is.
- Euler's totient function is a case of inclusion-exclusion over prime factors.
