Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 36 ยท Inclusion-Exclusion

Derangements and the Hat-Check Problem

Count permutations with no fixed points using inclusion-exclusion, the recurrence D(n) = (n-1)(D(n-1)+D(n-2)) and the 1/e limit, verified step by step in Python.

At a party, n guests hang their hats, and the attendant hands the hats back at random. What is the chance that nobody gets their own hat? The answer, surprisingly, is about 36.8% for any large party, and counting it is a showcase of inclusion-exclusion.

A derangement is a permutation in which no element stays in its original position (no fixed points). The number of derangements of n items is written D(n) or !n ("subfactorial n").

Small cases by hand

  • n = 1: the only permutation fixes its element, so D(1) = 0.
  • n = 2: swapping 1 and 2 works, so D(2) = 1.
  • n = 3: the permutations 231 and 312 work, so D(3) = 2.
  • n = 4: nine permutations, D(4) = 9.
Python Brute-force derangements

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see 1, 0, 1, 2, 9, 44, 265, 1854. Note D(0) = 1 by convention (the empty permutation has no fixed points).

Inclusion-exclusion formula

Let Ai be the set of permutations fixing position i. A derangement lies in none of A1, ..., An. The size of the intersection of j of these sets is (n-j)!: j positions are fixed, the others permute freely. There are C(n, j) ways to choose which j are fixed. So:

D(n) = ฮฃ (-1)^j C(n, j) (n-j)! = n! ฮฃ (-1)^j / j!

For n = 4: 24 - 24 + 12 - 4 + 1 = 9.

Python D(n) from inclusion-exclusion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A recurrence

A faster way to compute D(n) uses

D(n) = (n - 1) ยท (D(n-1) + D(n-2)).

Reason: consider where element n goes. It goes to some position i among the other n-1 (that is the factor n-1). Say n goes to i. Either element i goes to position n (a swap), leaving a derangement of the other n-2 elements: D(n-2); or i does not go to n, and then we can treat position n as "the forbidden spot" of i, giving a derangement-like problem on n-1 elements: D(n-1).

A simpler related recurrence is D(n) = n ยท D(n-1) + (-1)^n.

Python Two recurrences agree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The hat-check probability

The probability that a random permutation is a derangement is D(n) / n! = ฮฃ (-1)^j / j!. This is a partial sum of the series for e^(-1), so it converges fast to 1/e = 0.3678.... By n = 6 it is already correct to three decimals.

Python Probability tends to 1/e

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In fact D(n) is the integer nearest to n! / e, for n >= 1. Try it: 5!/e = 44.15, rounds to 44.

flowchart TD
    A["n hats returned at random"] --> B["D(n) outcomes with no match"]
    B --> C["Probability D(n)/n!"]
    C --> D["Tends to 1/e = 0.3679"]

Almost surprisingly, the answer barely depends on how many guests there are.

Variations

  • Exactly k fixed points: choose which k are fixed, derange the rest: C(n, k) ยท D(n-k).
  • Secret Santa: each of n people draws another's name. The number of valid draws is D(n).
  • Matching letters to envelopes is the same problem.
Python Exactly k fixed points

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Whenever a problem says "no item in its original place", "nobody gets their own" or "no one receives their own gift", think derangement.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is D(4), the number of derangements of 4 items?

    24 - 24 + 12 - 4 + 1 = 9.
  2. 2. Which recurrence is correct?

    Element n has n-1 places to go, then two sub-cases.
  3. 3. As n grows, the probability that a random permutation is a derangement approaches:

    D(n)/n! is a partial sum of the series for e^(-1).
  4. 4. How many permutations of 5 items have exactly 2 fixed points?

    C(5, 2) x D(3) = 10 x 2 = 20.

Summary

  • A derangement has no fixed points; D(n) = n! ฮฃ (-1)^j / j!.
  • Values: 1, 0, 1, 2, 9, 44, 265, 1854, ...
  • D(n) = (n-1)(D(n-1) + D(n-2)) and D(n) = n D(n-1) + (-1)^n.
  • The probability tends to 1/e; exactly k fixed points give C(n, k) D(n-k).

Next: Surjections and Euler's Totient