Skip to content

Derangements: The Hat-Check Problem and Its Formula

A derangement is a permutation that leaves nothing in place. Count them with inclusion–exclusion, see why the odds approach 1/e, and use the recurrence.

By Published 4 min read

Reign Creative LLC makes Discrete Math: Study & Quiz, which this article links to, so we have a commercial interest in it. How we write and check articles.

AI-assisted article. Drafted with AI tools from the sources cited below and checked by automated tests and an AI editorial review. No person has reviewed it yet. How we write and check articles.

Key takeaways

  • A derangement is a permutation in which no item ends up in its original position.
  • The number of derangements of n items is Dₙ = n!(1 − 1/1! + 1/2! − 1/3! + ⋯ ± 1/n!), found by inclusion–exclusion.
  • The first values are 1, 0, 1, 2, 9, 44, 265, 1854 for n = 0 to 7.
  • The chance that a random permutation is a derangement approaches 1/e ≈ 0.368, and is already close for n = 4.
  • Derangements satisfy the recurrence Dₙ = (n − 1)(Dₙ₋₁ + Dₙ₋₂).

A cloakroom attendant loses the tickets and hands the hats back at random. What is the chance that nobody gets their own hat? Or: a group draws names for a gift exchange from a hat; how often does nobody draw themselves? Both are questions about derangements, permutations in which nothing stays where it started. MathWorld records that P. R. de Montmort formulated the problem in 1708 and solved it in 1713, and that Nicholas Bernoulli also solved it with inclusion–exclusion.

Small cases

Number the items 1 to n and look for orderings in which item i is never in position i.

  • n = 1: the only ordering, 1, leaves 1 in place. D₁ = 0.
  • n = 2: 21 works. D₂ = 1.
  • n = 3: of 123, 132, 213, 231, 312 and 321, only 231 and 312 move everything. D₃ = 2. This is the example Levin's Discrete Mathematics: An Open Introduction uses.
  • n = 4: 9 of the 24 orderings.

Listing gets out of hand quickly, which is why a formula is worth having. The OEIS entry for the sequence (A000166) gives

n 0 1 2 3 4 5 6 7 8
Dₙ 1 0 1 2 9 44 265 1,854 14,833
n! 1 1 2 6 24 120 720 5,040 40,320

(D₀ = 1 by convention: the empty arrangement moves nothing, but it also leaves nothing in place.)

The formula, by inclusion–exclusion

Count the permutations that fix at least one item, then subtract from n!. Let Aᵢ be the set of permutations that leave item i in place.

  • |Aᵢ| = (n − 1)!, since the other n − 1 items are arranged freely. There are C(n, 1) such sets.
  • |Aᵢ ∩ Aⱼ| = (n − 2)!, with C(n, 2) pairs.
  • In general, fixing k chosen items leaves (n − k)! arrangements, and there are C(n, k) ways to choose them.

By inclusion–exclusion, the number fixing at least one item is

C(n, 1)(n − 1)! − C(n, 2)(n − 2)! + C(n, 3)(n − 3)! − ⋯

Since C(n, k)(n − k)! = n!/k!, subtracting from n! gives

Dₙ = n! (1 − 1/1! + 1/2! − 1/3! + ⋯ + (−1)ⁿ/n!).

Check with n = 5: 120 · (1 − 1 + 1/2 − 1/6 + 1/24 − 1/120) = 60 − 20 + 5 − 1 = 44.

Levin's book introduces the topic with a prank: swapping the nameplates on five professors' doors so that every one is wrong. The answer is D₅ = 44 ways.

Why 1/e appears

The probability that a random permutation is a derangement is

Dₙ/n! = 1 − 1/1! + 1/2! − 1/3! + ⋯ + (−1)ⁿ/n!.

That is the start of the series for e⁻¹ = Σ (−1)ᵏ/k!, so as n grows the probability approaches 1/e ≈ 0.3679. MathWorld remarks that the probability is very close to 1/e for as few as four items, and the numbers bear that out:

n Probability of a derangement
2 0.5
3 0.3333
4 0.375
5 0.3667
6 0.3681
10 0.3679

So in a gift exchange with names drawn at random, someone draws their own name about 63% of the time, almost regardless of group size. The terms of the series shrink so fast that the error after n terms is less than 1/(n + 1)!, which is why Dₙ equals n!/e rounded to the nearest whole number for every n ≥ 1. (For n = 6: 720/e ≈ 264.87, which rounds to 265.)

A related fact with a one-line proof: the expected number of people who get their own hat is exactly 1, for every n. Each person has a 1/n chance, and by linearity of expectation the n chances add to 1. The expected value guide explains why expectations add even when events depend on each other.

A recurrence

Derangements also satisfy

Dₙ = (n − 1)(Dₙ₋₁ + Dₙ₋₂), for n ≥ 2.

Why. Item 1 goes to some position k ≠ 1: n − 1 choices. Now look at item k.

  • If item k goes to position 1, items 1 and k have swapped, and the other n − 2 items must form a derangement: Dₙ₋₂ ways.
  • If item k does not go to position 1, treat position 1 as k's "forbidden" spot. The remaining n − 1 items, including k, must each avoid one forbidden position: Dₙ₋₁ ways.

Check: D₅ = 4 · (D₄ + D₃) = 4 · (9 + 2) = 44, and D₆ = 5 · (44 + 9) = 265. Recurrences like this are solved and analysed in recurrence relations.

Variations

  • Exactly k items in place. Choose which k stay, C(n, k) ways, and derange the rest: C(n, k) · Dₙ₋ₖ. For n = 5 and k = 2: 10 · 2 = 20.
  • At least one item in place. n! − Dₙ; for 5 items, 120 − 44 = 76.

Where derangements show up

  • Gift exchanges and draws. Rejecting a draw where someone picks themselves and redrawing until none do produces a derangement.
  • A card game's name. MathWorld notes that derangements are also called rencontres numbers, after the solitaire game rencontres, or complete permutations.
  • Checking shuffles. In a fair shuffle of n cards, the chance that no card stays in its original position is close to 1/e.

Counting problems built on permutations and inclusion–exclusion belong to the combinatorics unit of Discrete Math: Study & Quiz. See our education apps, or work through the discrete math hub for the surrounding counting guides, starting with permutations versus combinations.

Good to know

Frequently asked questions

What is a derangement?
A rearrangement of a list in which no item stays in its original position. Of the 6 orderings of 1, 2, 3, only 231 and 312 move every number, so there are 2 derangements of three items.
How many derangements of 5 items are there?
44. By the formula, D₅ = 5!(1/2! − 1/3! + 1/4! − 1/5!) = 60 − 20 + 5 − 1 = 44, out of 120 permutations in all.
What is the probability that nobody gets their own hat back?
For n people it is Dₙ/n!, which is 1 − 1/1! + 1/2! − ⋯ ± 1/n!. As n grows it approaches 1/e, about 36.8%. With 4 people it is 9/24 = 37.5%, and for 10 or more it agrees with 1/e to several decimal places.
What is a subfactorial?
Another name for the number of derangements, written !n. So !4 = 9 and !5 = 44. It can be computed as n!/e rounded to the nearest integer for n ≥ 1.

Sources

  1. Advanced Counting Using PIE: Counting Derangements (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
  2. Derangement (opens in a new tab)Wolfram MathWorld — accessed
  3. A000166: Subfactorial or rencontres numbers, or derangements (opens in a new tab)The On-Line Encyclopedia of Integer Sequences (OEIS) — accessed

About the author

— The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.

We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.

No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.

Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.

Keep reading