Inclusion exclusion
Named by 10 essays across 6 fields — each of them below, with the objects they name alongside it.
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.
The sieve that cannot finish
Sifting out the composites is the oldest method in the subject and it has a ceiling nobody has raised. The reciprocals of the twin primes add to a finite number, so no argument that measures thickness can reach them — and the inclusion–exclusion every sieve truncates goes wildly wrong before it goes right.
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 one that hardly ever comes up
Make the kinds unequally likely and the tidy decomposition into stages fails, because a stage's rate now depends on which kinds turned up rather than on how many. What replaces it is an alternating sum over every subset — and the rarest kind turns out to be nearly the whole answer.
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.
Counting targets by their holes
The Euler characteristic adds up like an area: glue two shapes together and it is the sum of theirs minus that of their overlap. So it can be used to measure, and measuring with it does something no area can. A field of sensors that each report only how many targets they detect — not which, not where — can have its readings added up, weighted by the Euler characteristics of the regions where the count is high, and the answer is exactly the number of targets.
Nineteen copies and no more
Two of the icosahedron's rotations, chosen at random, generate all sixty of them nineteen times in thirty. Philip Hall found the number in 1936 by inclusion and exclusion over every subgroup at once, weighted by the Möbius function of the subgroups' order — and the same count says that nineteen copies of the group, side by side, can still be generated by two elements, while twenty cannot.
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.
A card game almost nobody wins
Shuffle a deck and deal it face up, calling ace, two, three, up to king and round again, four times through. If a card ever matches the rank being called, the game is lost, and it is won about one time in sixty-two. The chance is 0.016232727…, exact, because the forbidden pairings form thirteen separate four-by-four squares and inclusion–exclusion turns their rook numbers into a sum — a sum whose terms climb past ten before they cancel to a sixtieth, and which is also the integral of a power of a Laguerre polynomial. The obvious guess, e to the minus four, is eleven per cent too high, and two hundred thousand deals can tell.
Named alongside it
The objects these essays reach for when they reach for this one.
Derangemente, the numberLimitPermutationRook polynomialApproximationCounting argumentCounting two waysGenerating functionPoisson approximationProbabilityAlternating group