3.4Inclusion–exclusion and derangements
The idea
Inclusion–exclusion counts objects that avoid every bad property: start with the total, subtract each bad set, add back the overlaps. A derangement is a permutation with no element in its original place.
Think of it like this: Everyone throws a hat in a pile and grabs one at random; a derangement is the case where nobody gets their own hat.
Why it exists
Counting numbers coprime to something (Euler φ), counting derangements and counting onto functions all use the same alternating sum.
How it works
- Numbers ≤ N divisible by none of a₁..a_k: N − Σ⌊N/aᵢ⌋ + Σ⌊N/lcm(aᵢ,aⱼ)⌋ − … .
- Euler totient φ(n) = n Π (1 − 1/p) over the primes p dividing n.
- Dₙ = n! Σ (−1)ᵏ/k!, and Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂). Values: D₁..D₅ = 0, 1, 2, 9, 44.
- Permutations with exactly k fixed points: C(n, k)·D_{n−k}.
Worked example: Numbers ≤ 100 not divisible by 2, 3 or 5
100 − (50+33+20) + (16+10+6) − 3 = 100 − 103 + 32 − 3 = 26.
Now play with it
- →Use the lab with N = 100 and divisors 2 3 5 to see the 26.
- →Open the derangements tab and watch Dₙ/n! settle at 0.368.
| Divisible by all of | ⌊N / lcm⌋ | sign |
|---|---|---|
| 2 | 50 | + |
| 3 | 33 | + |
| 2, 3 | 16 | − |
| 5 | 20 | + |
| 2, 5 | 10 | − |
| 3, 5 | 6 | − |
| 2, 3, 5 | 3 | + |
Add singles, subtract pairs, add triples, … Euler's φ(n) is this count with the primes of n.
Check yourself
How many permutations of 4 objects leave no object in its original position?
Exam notes (the dense version)
Numbers ≤ N divisible by none of a set: N − Σ⌊N/aᵢ⌋ + Σ⌊N/lcm(aᵢ,aⱼ)⌋ − … . Euler φ(n) = n Π(1 − 1/p). Derangements (no element fixed): Dₙ = n! Σₖ (−1)ᵏ/k! = (n−1)(Dₙ₋₁ + Dₙ₋₂). D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9, D₅ = 44. Dₙ/n! → 1/e. Permutations with exactly k fixed points: C(n,k)·D_{n−k}.
Previous year questions: Combinatorics & Recurrences (17)
PYQs are grouped by topic, so this is the full set for Combinatorics & Recurrences; try the ones that match this subtopic. Open all 17 on the topic page.