Series

Inclusion exclusion — the series

10 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. All 24 arrangements of 4 objects, and the 9 that move every one. Every permutation of 4 objects drawn as a grid of cells, with the diagonal — where an object stays where it began — shaded, and the arrangements that avoid it entirely marked.

    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.

    part 1 · probability
  2. A 6-sided die rolled 6 to 40 times: some face missing, and the sum stopped early. Curves of the chance that some face of a die has not yet appeared against the number of rolls, with the inclusion–exclusion sum stopped after one, two and three terms drawn around the exact curve.

    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.

    part 2 · probability
  3. How many of 8 people get their own hat, against the Poisson with mean 1. Paired bars for each number of people getting their own hat: the exact share of arrangements and the Poisson probability with mean one, nearly equal at every count.

    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.

    part 3 · probability
  4. Permutations that avoid 8 forbidden cells. A 5 by 5 grid with 8 forbidden cells shaded and one permutation that avoids them marked, beside the numbers of ways to place non-attacking rooks on the forbidden cells and the count of avoiding permutations they give.

    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.

    part 4 · probability
  5. 5 couples seated so that no one sits beside a partner. A round table with 10 seats alternating women and men, labelled by couple, arranged so that no man sits next to his partner, with the number of such arrangements.

    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.

    part 5 · probability
  6. A single table for 9 guests over 4 nights. Small circles of 9 guests, one per night, each showing the night's seating as a closed zigzag path; every pair of guests is adjacent in exactly one of them.

    Every pair side by side, once

    Seat an odd number of guests at round tables for as many nights as it takes, the same table sizes every night, so that every two guests sit side by side on exactly one night. For a single table a zigzag turned a notch each night does it for any number of guests. For other table plans the answer is almost always yes — and for six guests at two tables of three, nine at tables of four and five, and eleven at three, three and five, an exhaustive search proves it is no.

    part 6 · probability
  7. How many matches a frustrating deal has. 0:0.016233/0.018316, 1:0.068899/0.073263, 2:0.144164/0.146525, 3:0.198194/0.195367, 4:0.201325/0.195367, 5:0.161112/0.156293, 6:0.105762/0.104196, 7:0.058554/0.059540, 8:0.027898/0.029770, 9:0.011615/0.013231, 10:0.004276/0.005292, 11:0.001406/0.001925, 12:0.000416/0.000642

    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.

    part 7 · probability
  8. Arcs that overlap and still leave gaps. n=14, a=0.2: starts 0.014,0.017,0.118,0.192,0.232,0.237,0.251,0.428,0.458,0.500,0.510,0.579,0.930,0.931; gaps 1; P(cover) exact 0.34675223.

    Arcs that cover a circle

    Throw fourteen arcs, each a fifth of a circle, onto the circle at random: together they are nearly three times as long as it, and still a third of the time some stretch is left bare. The chance of covering is an alternating sum over which gaps are too long, found by W. L. Stevens in 1939. Its terms run into the thousands and cancel to almost nothing, and they say that random covering costs a logarithm.

    part 8 · probability
  9. Boxes as a permutation. A random permutation of 24 with cycle lengths 11, 7, 5, 1; longest 11.

    A hundred prisoners and one shuffle

    A hundred prisoners each search fifty of a hundred boxes for their own number, one at a time, with no communication once it starts. If any fails, all are executed. Choosing at random gives them a chance of 8 × 10⁻³¹. There is a rule that gives them 31%, and no rule can do better. Every prisoner's individual chance is still one half: what the rule changes is not how often each succeeds but how those successes line up.

    part 9 · probability
  10. One swap splits the long cycle. A shuffle of 100 boxes whose longest cycle has 61 boxes, drawn as a ring; swapping the contents of two boxes 30 steps apart splits it into cycles of 30 and 31, so every cycle has at most 50 and all prisoners succeed.

    One swap saves every prisoner

    A hundred prisoners following the cycles of a shuffle all survive about 31% of the time. Let a helper look into the room first and swap the contents of two boxes, and they survive every time. With fewer boxes each, more swaps are needed — exactly one per cut a long cycle needs — and the number of swaps a random room demands has an exact distribution.

    part 10 · probability

All series