derangements
/ dee-RAYNJ-ment /
Suppose n people each wrote a letter and addressed an envelope, but the letters got stuffed into envelopes completely at random. What is the chance that NOT A SINGLE letter lands in its correct envelope? A permutation in which no item ends up in its own original position is called a derangement, and counting them is a beautiful application of inclusion-exclusion.
Let D(n) (also written !n) be the number of derangements of n items. Direct counting is hard because 'nobody in their right place' forbids many positions at once, so we use complementary counting via inclusion-exclusion. Start with all n! permutations, subtract those fixing at least one item, add back those fixing at least two (subtracted twice), and so on. The result is the clean formula D(n) = n! times (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!). For small n: D(1) = 0, D(2) = 1, D(3) = 2, D(4) = 9, D(5) = 44. There is also a tidy recurrence, D(n) = (n-1) times (D(n-1) + D(n-2)).
The startling part is the probability of a total mismatch: D(n)/n! equals that alternating sum, which is the first several terms of the series for e^(-1). So as n grows, the chance that a random shuffle leaves EVERYTHING out of place settles near 1/e, about 0.3679 — and it gets there fast, already very close by n = 6. The lesson worth carrying away: this probability barely depends on n, contradicting the common guess that with more people a total mismatch becomes far rarer.
Three friends randomly grab one of three hats. There are 3! = 6 ways; the derangements (nobody gets their own hat) number D(3) = 2, so the chance everyone is wrong is 2/6 = 1/3 about 0.333 — already close to 1/e about 0.368.
D(n) counts permutations with NO fixed point; D(n)/n! tends to 1/e.
The probability of a complete mismatch converges to 1/e and changes very little as n grows — it is NOT true that more items make a full derangement dramatically rarer.