Derangements

n guests check their hats at a restaurant. The hats are returned in a uniformly random order. What is the probability that no guest receives their own hat?

A permutation where no element appears in its original position is called a derangement. The count of derangements of n items is:

D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}

P(derangement) theory

36.79%

→ 1/e ≈ 36.79% as n → ∞

Simulated

38.75%

n (items) 8 simulations 2000

Dark bars: analytical PMF P(X=k) = (1/k!) · D(n−k)/(n−k)!. Light bars: empirical from 2000 random permutations. The k=0 bar (a derangement — no hat goes to its owner) converges to 1/e for any n ≥ 3.

The remarkable limit

The probability that a random permutation is a derangement converges rapidly:

P (derangement) = \frac{D _{n}}{n !} = k = 0 \sum n \frac{( - 1 ) ^{k}}{k !} \to \frac{1}{e}

Already at n=3 this is within 2% of 1/e. The formula is a truncated alternating series — the pattern converges so fast that the n=6 value is indistinguishable from 1/e to 6 decimal places.

Distribution of fixed points

More generally, let X be the number of items that land in their original position. The full PMF is:

P (X = k) = \frac{1}{k !} j = 0 \sum n - k \frac{( - 1 ) ^{j}}{j !}

This looks like a Poisson(1) distribution — and indeed as n → ∞, X converges in distribution to Poisson(1). The probability of exactly k fixed points approaches 1/(e · k!), which is exactly the Poisson(1) PMF.

Inclusion-exclusion

The derivation uses inclusion-exclusion. Let Aᵢ be the event that item i is fixed. We want P(none fixed) = 1 − P(A₁ ∪ … ∪ Aₙ). By inclusion-exclusion:

P(at least one fixed) = Σ P(Aᵢ) − Σᵢ<ⱼ P(Aᵢ ∩ Aⱼ) + …

Each P(Aᵢ₁ ∩ … ∩ Aᵢₖ) = (n−k)!/n! regardless of which k items are chosen. There are C(n,k) such terms, giving the alternating series above after cancellation.