The hat-check scramble

A derangement is a permutation with no element in its original position. They satisfy the recurrence !n = (n - 1) * (!(n - 1) + !(n - 2)) with !1 = 0 and !2 = 1, giving !4 = 3 * (2 + 1) = 9 and !5 = 4 * (9 + 2) = 44. Equivalently, for n >= 1, !n is the nearest integer to n! / e.

Words you need

Permutation: An ordering of items where order matters.
Derangement: A shuffle where nothing ends up in its original place.

Why it works

Inclusion-exclusion over the n fixed-point sets leaves n! times the truncated series of 1/e, which rounds to the exact integer.

!n = n! * sum_{i=0}^n ((-1)^i / i!) = nearest integer to n! / e for n >= 1 (separately, !0 = 1)

Spot it: No item may stay in its original position (secret santa, hat check, card mismatch).

Technique reference and sources

Guests check n hats and receive one back at random. A derangement means nobody gets their own hat. For large n the chance settles near 1/e (about 0.37), so roughly one shuffled deal in three is a clean miss.

When this method fits

No item may stay in its original position (secret santa, hat check, card mismatch).
You need permutations with forbidden positions symmetric across all items.
Small n (2 to 6) allows exact recurrence arithmetic by hand.
You want the probability that a random shuffle fixes nothing: !n / n!.

Anchor the recurrence. !1 = 0 (one item cannot move) and !2 = 1 (only the swap works).
Climb with the recurrence. !n = (n - 1) * (!(n - 1) + !(n - 2)). For n = 4: 3 * (2 + 1) = 9.
Cross-check with n! / e. For n >= 1, round n! / e to the nearest integer: 24 / e rounds to 9, 120 / e rounds to 44.
Convert to probability. Divide by n!: a random permutation of 4 deranges with probability 9 / 24 = 0.375.

Small subfactorials: !1 = 0, !2 = 1, !3 = 2, !4 = 9, !5 = 44, !6 = 265. Each step multiplies the sum of the previous two by n - 1.

!3 = 2 * (1 + 0) = 2
!4 = 3 * (2 + 1) = 9
!6 = 5 * (44 + 9) = 265

Derangement probability plateau: !n / n! converges to 1/e (about 0.37): 0.50, 0.33, 0.375 (rounds to 0.38), 0.37, 0.37 for n = 2 to 6.

n = 2: 1 / 2 = 0.5
n = 4: 9 / 24 = 0.375
n = 6: 265 / 720 = 0.37 to 2 places

One-predecessor recurrence: D_n = n * D_{n-1} + (-1)^n. Use it when only the immediately preceding value is remembered; it loses when parity mistakes are likely or the two-case derivation is the interview objective.

D_5 = 5 * 9 - 1 = 45 - 1 = 44
D_4 = 4 * 2 + 1 = 8 + 1 = 9

Common traps

Reporting n! / e without rounding (for example 8.83 for n = 4). Counts are integers. Round to the nearest whole number: 24 / e = 8.83 rounds to !4 = 9.

Starting the recurrence from !0 = 0. !0 = 1 (the empty permutation vacuously deranges). The hand recurrence only needs !1 = 0 and !2 = 1.

Confusing derangements with complementary counts like n! - 1. Only one permutation is the identity, but many have some fixed point. For n = 4, permutations with a fixed point number 24 - 9 = 15, not 23.

Another example: Probability a 4-shuffle fixes nothing

Favorable outcomes: !4 = 9
Total outcomes: 4! = 4 * 3 * 2 * 1 = 24
Probability: 9 / 24 = 0.375

Source notes

These explanations and questions are written for QuantArc. Links show the underlying mathematics and learning design.

Harvard Stat 110: Probability (Joe Blitzstein)
Free course site with videos and the open companion book Introduction to Probability; the topic spine for counting, Bayes, and linearity. Lesson examples and questions are original.

MIT OCW 6.042J: Mathematics for Computer Science
Course page checked: undergraduate discrete mathematics covering permutations and combinations plus counting principles. Topic spine for stars and bars, lattice paths, and derangements. Lesson examples and questions are original.

IES: Organizing Instruction and Study to Improve Student Learning
Supports worked examples, retrieval, explanations and spaced study. Does not establish QuantArc's exact lesson length, mastery threshold or review intervals.