Derangement
Named by 8 essays across 4 fields — each of them below, with the objects they name alongside it.
Nobody gets their own hat
Hand back a pile of hats at random and ask for the chance that not one person gets their own. The answer barely moves as the crowd grows — it is a third and a bit at four people, and a third and a bit at four thousand.
The constant that counts what does not happen
Nothing grows in a shuffled pack of cards, and nothing grows in a factorial. Yet e sits in the middle of both — as the chance that a shuffle leaves nothing in place, and as the base that makes n! nearly a power.
A sum stopped early still says something
Inclusion–exclusion corrects an overcount, then the correction's overcount, and so on to the end. Stop after any number of terms and the result is not merely an approximation: after an odd number it is too high and after an even number too low, always. So two or three terms bracket an answer whose full sum is out of reach — as long as the events being counted are rare.
How many get their own hat
The chance that nobody gets their own hat settles on 1/e. The chance that exactly one person does settles on 1/e too, exactly two on 1/(2e), exactly three on 1/(6e) — the Poisson distribution with mean 1. The reason is a set of averages that come out exactly 1 at every size, and the counts reach the limit so fast that eight hats are within six ten-thousandths of it.
The product that deals the labels
Multiplying two counting series pairs one choice with another. When the things being counted carry labels, the labels have to be dealt out as well, and the only series that survive the extra bookkeeping are the ones divided by n factorial.
The cells a permutation must miss
A derangement is a permutation that misses the diagonal of a square grid. Forbid any other set of cells instead and inclusion–exclusion still counts what is left — driven entirely by one list of numbers, the ways to place non-attacking rooks on the forbidden cells. Boards that look nothing alike can share that list, and rooks on a staircase turn out to count the ways to split a set.
A round table with no couple together
Seat n couples round a table, men and women alternating, so that nobody sits beside their partner. Once the women are placed the men face a board of forbidden cells that bends round a corner — and that corner is the whole difficulty. The forbidden cells form a cycle, a count of non-adjacent points on a cycle finishes the problem, and the chance of a good seating creeps towards e^(−2) far more slowly than the hat problem reaches 1/e.
A third of random games have no pure equilibrium
Fill a game's payoff table with random numbers and ask whether some cell is each player's best reply to the other. Exactly one cell is expected to be, at every size, and the chance that none is climbs from one in eight to 1/e — the same constant that counts the shuffles in which nobody gets their own hat back, and for the same reason.
Named alongside it
The objects these essays reach for when they reach for this one.
e, the numberInclusion exclusionPermutationCounting two waysApproximationCounting argumentLimitAlternating seriesComplementary countingGenerating functionRook polynomialBijection