Discrete Math · Undergraduate
Inclusion–Exclusion in General: Derangements and Onto Functions
Quick answer
The general inclusion–exclusion principle counts how many objects have none of the properties P₁, …, Pₙ: start with everything, subtract those with each property, add back those with each pair, subtract each triple, and so on. Applied to permutations where no item stays in its place, it gives the derangement count Dₙ = n!(1 − 1/1! + 1/2! − ⋯ ± 1/n!): about 1/e of all shuffles fix nothing. The same pattern counts onto functions and the numbers up to N sharing no factor with given primes.
What you'll learn
- State inclusion–exclusion for any number of properties
- Count derangements and the probability of a derangement
- Count onto functions from one finite set to another
- Count integers avoiding several divisors
Counting what has none of the properties
For two or three sets, inclusion–exclusion corrects for overlaps. The same idea works for any number of properties. To count objects with none of the properties :
where counts the objects with both and . The signs alternate, and when the counts depend only on how many properties are involved, each sum is a binomial coefficient times one count.
Why each object is counted exactly once
Take an object with exactly of the properties. It is counted once in , times in the singles, times in the pairs, and so on. Its net count is
by the binomial theorem. Every object with at least one property cancels to , and every object with none is counted exactly once. The alternating signs are precisely what makes the overcounting cancel.
Worked examples
Common mistakes
Practice problems
-
Find .
Answer
Full solution
.
-
Five letters go into five addressed envelopes at random. Find the chance no letter is in its right envelope.
Answer
Full solution
, already close to .
-
Check the recurrence for .
Answer
Full solution
and .
-
How many onto functions are there from a -element set to a -element set?
Answer
Full solution
: every function except the two constant ones.
-
How many integers from to are divisible by , or ?
Answer
Full solution
. The other share no factor with .
-
Count the permutations of in which is not first and is not second.
Answer
Full solution
.
-
Explain why an object with exactly of the properties is counted times net.
Answer
Full solution
It is counted once in the total, twice among the singles and once among the pairs.
-
A student computes . What is missing?
Answer
The pair, triple and quadruple terms: .
Full solution
Subtracting all single counts removes permutations with two fixed points twice, so they must be added back, and so on, giving .
Frequently asked questions
What is the general inclusion–exclusion principle?
The number of objects with none of the properties equals the total, minus the sum over single properties, plus the sum over pairs, minus the sum over triples, and so on, alternating signs.
What is a derangement?
A permutation in which no element stays in its original position, like returning hats so that nobody gets their own.
How many derangements of n objects are there?
Dₙ = n!(1 − 1/1! + 1/2! − 1/3! + ⋯ + (−1)ⁿ/n!). The first values are 0, 1, 2, 9, 44, 265.
Why is the chance of a derangement close to 1/e?
Dₙ/n! is a partial sum of the series for e⁻¹ = Σ (−1)ᵏ/k!, which converges very fast.
How many onto functions are there from a 5-element set to a 3-element set?
3⁵ − 3·2⁵ + 3·1⁵ = 150, by subtracting the functions that miss some output.