Derangements

You will learn: Count permutations without fixed points and separate exact from limiting probabilities.

New to the notation? Start with the connected foundation for the underlying definitions and a worked example.

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!\sum_{k=0}^{n}\frac{(-1)^k}{k!}

Inspect every assignment

Items to enumerate 3.00

Positions are guests 1 through 3; each row lists the hats they receive. An asterisk marks a guest's own hat. All 6 assignments are equally likely; 2 have no fixed points (33.33%).

Show

Exact assignments, page 1 of 1
Hats received	Fixed points	Cycles
1* · 2* · 3*	3	3
1* · 3 · 2	1	2
2 · 1 · 3*	1	2
2 · 3 · 1	0	1
3 · 1 · 2	0	1
3 · 2* · 1	1	2

Follow a guest to the owner of their assigned hat, then repeat until returning: that is one cycle. A derangement can have several cycles. For four guests, 2 · 1 · 4 · 3 swaps two pairs.

Compare exact probabilities with simulation

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) approaches 1/e as n grows; n=1 and n=2 give exactly 0 and 1/2.

The remarkable limit

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

P(\text{derangement}) = \frac{D_n}{n!} = \sum_{k=0}^{n}\frac{(-1)^k}{k!} \to \frac{1}{e}

At n=3 the probability is 1/3, about 3.45 percentage points below 1/e. At n=6 it is 265/720 ≈ 0.368056, compared with 1/e ≈ 0.367879: a difference of about 0.018 percentage points.

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!}\sum_{j=0}^{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.

A derangement need not be one cycle

For n=3, enumerate the six equally likely rows. Only 2 · 3 · 1 and 3 · 1 · 2 avoid every original position: 2/6=1/3. At n=1 there are no derangements; at n=2 the swap is the single derangement out of two assignments.

For n=4, 2 · 1 · 4 · 3 also has no fixed points, but it consists of two separate swaps. A single cycle visits every item before returning to its start. Every single cycle on n>1 items is a derangement, but not every derangement is a single cycle. There are 9 derangements of four items and only 6 single cycles.

Make a prediction

Can a permutation of six items have exactly five fixed points?

Explore the answer

No. Once five items keep their positions, the only remaining item must occupy its own remaining position too. This explains the missing n−1 bar in the exact distribution.

Reference

Random Services: the matching problem gives the inclusion–exclusion count and fixed-point distribution. Use the enumeration above to check its first few cases before moving to the Poisson limit.

Explore 100 prisoners and boxes to constrain the lengths of every permutation cycle, rather than only excluding fixed points.

Reset all settings