Nobody gets their own hat

A cloakroom loses its tickets and hands the coats back in a random order. What is the chance that nobody gets their own?

The question has a shape that ought to make it easy: the number of arrangements is a factorial, the number of bad ones ought to be countable, and the answer ought to depend on the size of the crowd in some obvious way. Two of those three are true. The third is spectacularly false, and the failure is the interesting part.

Nine out of twenty-four is three eighths, or 0.375. The answer for a crowd of five is 44 out of 120, which is 0.3667. For six, 265 out of 720, or 0.3681. The proportion is not settling towards a nice fraction and it is not drifting towards zero or one. It is sitting on a number.

Counting by looking #

The grid is the definition made visible. An arrangement of n objects is a permutation — a rule sending each object to a place, no two objects to the same place — and it can be drawn as a grid with one mark in every row and one in every column. The diagonal cells are the ones where an object goes to its own place, so an arrangement in which nobody gets their own is one whose marks avoid the diagonal entirely.

Such an arrangement is called a derangement, and the figure finds them by listing all twenty-four permutations and checking each for a mark on the diagonal. Nine survive.

Listing works up to about ten objects, at which point there are three and a half million arrangements, and stops working entirely by fifteen. Something better is needed, and the better thing is a method that never lists.

Subtracting the bad ones, and the trouble with that #

The natural move is to count the bad arrangements — the ones where somebody does get their own — and subtract. There are twenty-four arrangements in all; how many have at least one person holding their own coat?

The first attempt is to count the arrangements in which person A gets their own coat, which is the number of ways to arrange the other three, or six. The same for B, C and D. Four people, six each, twenty-four bad arrangements — and twenty-four minus twenty-four is zero, which is wrong by nine.

It is wrong because arrangements have been counted more than once. An arrangement in which both A and B hold their own coats was counted in A’s six and again in B’s. The overcount is not a small correction; it swallowed the entire answer.

Putting the double-counting back #

The repair is to add back what was subtracted twice. The arrangements fixing a chosen pair number two — the ways of arranging the remaining two objects — and there are six pairs, so twelve get added. But now the arrangements fixing three people have been subtracted three times and added back three times, so they need subtracting once more; and so on, alternately, to the end.

The result is the sequence in the figure: 24, then 0, then 12, then 8, then 9. Every partial sum lands on the wrong side of the answer, and the figure asserts that it does — each correction crosses the target rather than approaching it from one direction. That alternation is the signature of the method, and it is the reason none of the terms can be dropped as small: the term that would be dropped is the one that pulls the total back across the line.

The general term is easy to name once the pattern is seen. Choosing k people to fix can be done in as many ways as there are k-subsets, and the rest can be arranged in (n − k)! ways, and the sign alternates. That is the whole of the inclusion–exclusion principle, arrived at by fixing a broken count rather than by being stated.

What the sieve is really doing #

The alternating sum has a form that is worth reading rather than following, because the same form appears in every application of the method.

Each term counts arrangements satisfying at least a chosen set of conditions — here, “these particular people got their own hats”, with everybody else free. The count for a set of size k does not depend on which set, only on its size, which is what collapses a sum over all subsets into a sum over sizes with a binomial coefficient in front. That collapse is not automatic; it is a symmetry of this particular problem, and problems without it produce sums with exponentially many distinct terms and no closed form.

The signs come from a small identity about how many subsets of each size a set has, with alternating signs: for any non-empty set, the alternating count of its subsets is exactly zero. Applied to the set of conditions an arrangement happens to satisfy, that identity says every arrangement satisfying at least one condition contributes zero to the total, and every arrangement satisfying none contributes one. So the sum counts exactly what is wanted, and it does so by an enormous amount of cancellation — twenty-four terms of arithmetic to produce a nine.

The cancellation is why the method feels like sleight of hand and why it is completely reliable. Nothing is being estimated. Every arrangement is counted a whole number of times, and the whole number is 1 for the good ones and 0 for all the rest.

The number it settles on #

Divide the alternating sum by n! and something remarkable happens to it: the terms become 1, then −1, then a half, then a sixth, then a twenty-fourth — the reciprocals of the factorials, with alternating signs. That series is the one that defines the exponential at −1, so the proportion of derangements converges to 1/e.

The convergence is not leisurely. At four objects the proportion is 0.375 against 0.3679; at seven it agrees to four decimal places; at ten the difference is smaller than one part in thirty million. The answer for a crowd of ten and the answer for a crowd of ten million are the same number to any precision anyone will ever want.

That is the fact this essay exists for. The chance that a cloakroom disaster spares everybody does not depend on the size of the cloakroom. It is, and stays, a bit more than a third.

The appearance of e here is worth flagging as strange. Nothing in the setup involves growth, or compound interest, or a curve that is its own slope. It is a counting problem about hats. The constant arrives through a series that happened to be the exponential’s, and the connection is real rather than decorative — but it is the kind of arrival this site has a theme for, and the same one that brings pi into a problem about needles.

A second route, which agrees #

There is another way to the same numbers, and it takes no sums at all.

Consider a derangement of n objects, and look at where the first object goes — say to place j, of which there are n − 1 choices. Now ask where object j goes. Either it goes to place 1, in which case the two have swapped and the remaining n − 2 objects must be deranged among themselves; or it does not, in which case object j is forbidden from place 1 in exactly the way an object is normally forbidden from its own place, and what remains is a derangement of n − 1 objects in disguise.

So the count for n is (n − 1) times the sum of the counts for n − 1 and n − 2. Starting from 1 and 0, that gives 1, 2, 9, 44, 265 — the same numbers the sieve produced, with no factorials and no alternating signs anywhere. The figures check the two against each other at every size they draw.

Two derivations agreeing is worth more than either alone, and it is worth more here than usual, because the alternating sum is exactly the sort of computation in which a sign error produces a plausible wrong answer. A recurrence built from a case split has different failure modes, and the intersection of two sets of failure modes is usually empty.

The control at the small end #

The search reports zero for a single object, and the zero is not a special case wheeled in to be tidy. There is exactly one way to hand one hat back, it hands the hat to its owner, and the search finds no derangement — which is what it should find, and what a search that could not report nothing would be unable to tell.

Two objects give one derangement: the swap. Three give two: the two cyclic shifts. These are small enough to enumerate by hand and they are also the sizes at which the proportion is furthest from its limit — nothing, a half, a third. The small cases lie theme normally names patterns that hold for a while and then break; this is the opposite failure, a pattern that has not started yet at the sizes a reader can check.

Two coincidence problems that behave in opposite ways #

Both questions ask about an unlikely-sounding coincidence in a random arrangement, and the two behave in opposite ways.

The birthday problem has an answer that races from nothing to near-certainty over a range of about forty people. It does that because the number of pairs grows as the square of the group, so the opportunities for a collision multiply far faster than the group does.

The hat problem has an answer that does not move at all. The reason is the same reason turned around: the number of opportunities for a match grows exactly as fast as the number of people, and the chance of each is exactly as small, so the two effects cancel. One person, one chance in one. Ten people, ten chances in ten. The product of the near-misses stays put.

Which of the two shapes a coincidence question has is not something intuition reads off the statement, and getting it wrong in either direction is easy. A useful test is to ask what is being counted — individuals or pairs — and how many of each there are. That is also the whole content of the pigeonhole style of argument, where the answer turns entirely on which of two collections is larger.

What the picture cannot show #

The grid draws twenty-four arrangements and the interesting sizes are beyond drawing. Five objects is a hundred and twenty grids, which is a wall rather than a figure; eight is forty thousand. Every figure past the first works from counts rather than from pictures of arrangements, and the honest description of the later ones is that they report a computation instead of showing it.

The independence is not visible either. The intuition that makes the answer feel right is that each person has about a 1/n chance of getting their own hat, and n nearly-independent near-misses of probability 1/n give about 1/e. That reasoning gets the right answer and is not correct as stated — the events are not independent, since one person having their own hat changes everybody else’s chances — and no picture on this page indicates how much the dependence matters. It happens to matter very little, and the sieve is what establishes that.

And the question of which arrangements is untouched. Nine is a count. Asking for a derangement of a large collection, or for a random one, or for the derangement that is in some sense the first, are all different problems, and none of them is answered by knowing there are 14,833 of them at eight objects.

Where the ladder goes next #

Inclusion–exclusion is not really about hats; it is about counting the things that avoid a list of conditions, when the conditions overlap. It answers how many numbers below a bound are divisible by none of a set of primes, which is what makes the sieve of Eratosthenes countable rather than merely runnable. It answers how many ways there are to colour a graph, and how many surjections there are between two finite sets.

The rung above this one is the version where the corrections do not stop being useful: for many problems the alternating sum is truncated deliberately, giving bounds that alternate above and below the truth, which is a genuinely useful thing to have when the exact count is out of reach. The bounds are called Bonferroni’s, they are the reason the method survives at scale, and their picture is the staircase of running totals in the sieve figure read as a bracket rather than as a route to an answer.

There is a third direction, towards the constant rather than the counting. The series 1 − 1 + 1/2 − 1/6 + 1/24 − … is the exponential’s, evaluated at −1, and this essay met it as the answer to a question about hats rather than as anything to do with growth. That the same series is what one point’s worth of information produces when a function is expanded, and what a sum that never stops growing fails to be, is the kind of coincidence that stops being one on closer inspection: factorials in denominators are what counting problems and derivatives both produce, for related reasons.

The other direction is the one this essay has already touched. A count that settles on a constant as the collection grows is the shape of an awful lot of probability, and the reason the constant is often e or π has to do with what the underlying series is. The birthday problem settles on a different constant by a similar route, and the two together make a decent case that the interesting question about a counting problem is not the count but the limit it approaches.