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 P1,…,PnP_1, \ldots, P_n:

N(none)=N−∑iN(Pi)+∑i<jN(PiPj)−∑i<j<kN(PiPjPk)+⋯N(\text{none}) = N - \sum_i N(P_i) + \sum_{i<j} N(P_iP_j) - \sum_{i<j<k} N(P_iP_jP_k) + \cdots

where N(PiPj)N(P_iP_j) counts the objects with both PiP_i and PjP_j. 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 m≥1m \ge 1 of the properties. It is counted once in NN, (m1)\binom{m}{1} times in the singles, (m2)\binom{m}{2} times in the pairs, and so on. Its net count is

1−(m1)+(m2)−⋯±(mm)=(1−1)m=01 - \binom{m}{1} + \binom{m}{2} - \cdots \pm \binom{m}{m} = (1 - 1)^m = 0

by the binomial theorem. Every object with at least one property cancels to 00, 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

  1. Find D5D_5.

    Answer

    4444

    Full solution

    120−120+60−20+5−1=44120 - 120 + 60 - 20 + 5 - 1 = 44.

  2. Five letters go into five addressed envelopes at random. Find the chance no letter is in its right envelope.

    Answer

    44120≈0.367\tfrac{44}{120} \approx 0.367

    Full solution

    D55!\tfrac{D_5}{5!}, already close to 1e≈0.368\tfrac{1}{e} \approx 0.368.

  3. Check the recurrence Dn=(n−1)(Dn−1+Dn−2)D_n = (n - 1)(D_{n-1} + D_{n-2}) for n=5n = 5.

    Answer

    4(9+2)=444(9 + 2) = 44

    Full solution

    D4=9D_4 = 9 and D3=2D_3 = 2.

  4. How many onto functions are there from a 44-element set to a 22-element set?

    Answer

    1414

    Full solution

    24−2⋅14=142^4 - 2 \cdot 1^4 = 14: every function except the two constant ones.

  5. How many integers from 11 to 6060 are divisible by 22, 33 or 55?

    Answer

    4444

    Full solution

    30+20+12−10−6−4+2=4430 + 20 + 12 - 10 - 6 - 4 + 2 = 44. The other 1616 share no factor with 3030.

  6. Count the permutations of 1,2,3,41, 2, 3, 4 in which 11 is not first and 22 is not second.

    Answer

    1414

    Full solution

    24−6−6+2=1424 - 6 - 6 + 2 = 14.

  7. Explain why an object with exactly 22 of the properties is counted 00 times net.

    Answer

    1−2+1=01 - 2 + 1 = 0

    Full solution

    It is counted once in the total, twice among the singles and once among the pairs.

  8. A student computes D4=24−4⋅6=0D_4 = 24 - 4 \cdot 6 = 0. What is missing?

    Answer

    The pair, triple and quadruple terms: +12−4+1+12 - 4 + 1.

    Full solution

    Subtracting all single counts removes permutations with two fixed points twice, so they must be added back, and so on, giving 99.

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.