Derangements Intro: Concepts, Formulas and Examples

A derangement is a permutation in which no object stays in its original position. If 4 letters are placed randomly into 4 addressed envelopes, a derangement is an outcome where every letter lands in the wrong envelope. The count is written !n, read as "subfactorial n".

This matters because "nothing in its right place" problems appear in probability puzzles, secret-Santa draws, and quality checks. Derangements also lead to one of the most surprising constants in probability: about 37% of random shuffles derange.

Key Concepts

• Derangement: a permutation of n objects with no fixed points — nothing in its original position.
• Subfactorial !n: the number of derangements of n distinct objects.
• Fixed point: an object that stays where it started; derangements have zero of them.
• 1/e connection: for large n, the fraction of permutations that are derangements approaches 1/e ≈ 0.368.

Formulas

• Inclusion–exclusion formula: !n = n! × (1 − 1/1! + 1/2! − 1/3! + … + (−1)^n/n!).
• Recurrence: !n = (n − 1) × (!(n − 1) + !(n − 2)), for n ≥ 3.
• Small values: !1 = 0, !2 = 1, !3 = 2, !4 = 9.
• Probability: for large n, P(derangement) ≈ 1/e ≈ 0.368.

Worked Example

Four letters are randomly put into four addressed envelopes. How many outcomes put every letter in the wrong envelope? Using the formula: !4 = 4! × (1 − 1/1! + 1/2! − 1/3! + 1/4!) = 24 × (1 − 1 + 0.5 − 0.1667 + 0.0417) = 24 × 0.375 = 9. So 9 of the 24 possible placements are derangements. Check with the recurrence: !4 = 3 × (!3 + !2) = 3 × (2 + 1) = 9. Both routes agree.

Common Misconceptions

• "!1 = 1." Wrong — a single object cannot avoid its own position, so !1 = 0.
• "Derangements become rarer as n grows." Wrong — the probability settles near 1/e ≈ 36.8% and stays there; it does not tend to zero.
• "A derangement means everything is shuffled." Not quite — it means nothing is in its original place; some pairs may still be internally consistent, just misplaced.

Real-World Applications

• Secret Santa: draws where nobody picks their own name.
• Hat-check problem: coats returned so that nobody gets their own.
• Mail rooms: estimating how often a random sort misplaces every item.
• Card shuffling: the classic "rencontres" probability puzzle.

Derangements count the "all wrong" outcomes through !n, computable by formula or recurrence. Remember !4 = 9 as a landmark, and the 1/e rule of thumb: in a large random shuffle, there is about a 37% chance nothing is where it started.