Generator

All 24 arrangements of 4 objects, and the 9 that move every one

A generator in the probability library, called 82 times across 16 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

derange is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

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.

5 couples seated so that no one sits beside a partner

The ménage problem as a board of forbidden cells

The forbidden cells of a round table form a cycle

Touchard's formula for 6 couples, term by term

The chance of a good seating creeps up to e^(−2)

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

after 6 rolls the sum stopped after 1 terms is above the truth ×105
after 6 rolls the sum stopped after 2 terms is below the truth ×105
for 1 people the chance lies between the two stopped sums ×60
after 6 rolls the full sum agrees with the chain on faces seen ×35
on the staircase of size 2, 0 rooks fit in S(2, 2) ways ×27
the band of width 1 at 2: rook numbers and search agree ×17
starting from event 1, the formula and every pattern of successes agree ×14
with chances 1/k, starting at 1 is the classical rule passing over 0 ×14
at 5 couples the chance is e^−2·(1 − 1/n) to within 1/n² ×12
the ménage count at 3 by formula and by search ×10
the 1-th factorial moment is 1 ×9
the arrangements of 8 with exactly 0 in place, listed and counted ×9
the count for threshold 0 agrees with the formula ×8
the cycles of length 1, over all arrangements, number 40320/1 ×8
r0 is Kaplansky's 2n/(2n − k)·C(2n − k, k) ×6
Riordan's formula counts the 3 × 3 Latin rectangles with a fixed first row ×5
every one of the 5040 orders was tried ×4
the counted best for 5 matches the formula ×4
the share with 0 matches is within sampling noise of the Poisson ×4
the alternating sum lands on the 265 the search found ×3
width 1 approaches e^−1 ×3
with 2 choices among 8, every order counted agrees with the plan ×3
between 3 and 9 objects, few enough to list ×2
between three and twelve sizes, each between 2 and 20000 ×2
200 to 5000 trials ×1
9 of them leave nothing where it started ×1
a die of 3 to 12 faces ×1
a group of up to 20 to 120 people ×1
a run of rolls starting at the number of faces ×1
a single threshold keeps at least 1 − 1/e ×1
a worse first value makes the rule stricter at the second ×1
a year of 50 to 1000 days ×1
after any first night the pairs left contain no table of three ×1
all 24 arrangements are drawn ×1
an exhaustive point is at most 8 objects ×1
an odd number of guests from 5 to 13 ×1
and by a larger factor each time ×1
and comes within a few per cent of it ×1
and it does better than taking one at random ×1
and its height there is the same number ×1
and sends no two objects to the same place ×1
and settles above the 0.5802 the limit is, rather than falling to 1/e ×1
and so forbid the same number of permutations ×1
and so is the chance of success ×1
and so is the variance ×1
and stays below the family's limit of about 2.332 ×1
and stays below the limit it is climbing towards ×1
and the best single threshold secures at least half of it ×1
and the half is never breached ×1
and with three, 0.6842 ×1
another choice always helps ×1
arrangements of 20 to 5000 objects ×1
at least as many rolls as faces ×1
between 3 and 12 objects ×1
between 3 and 14 events, so every pattern can be enumerated ×1
between one and three rooks ×1
between three and eight couples ×1
between three and ten couples ×1
between three and ten sizes ×1
each correction crosses the answer rather than approaching it from one side ×1
each distribution is one the view knows ×1
each extra person brings the distribution closer to the Poisson ×1
each proportion is within one over the next factorial of 1/e ×1
each stop is on the side the rule says ×1
each stop lands on its own side of the truth, or on it ×1
equal rook numbers exactly when the multisets hᵢ − i agree ×1
every arrangement is counted once ×1
every arrangement is visited once ×1
every guest dines every night ×1
every pair is side by side on exactly one night ×1
from five couples on the chance rises towards its limit ×1
inclusion–exclusion over rook numbers equals the count by search ×1
more choices in hand never mean a later start ×1
N is from 50 to 100000 ×1
no man in the drawing sits beside his partner ×1
no online rule beats the oracle ×1
one probability per event, each strictly between nought and one ×1
one to five increasing numbers of choices, up to 6 ×1
six guests in three couples leave twelve allowed pairs ×1
sizes up to at most sixteen ×1
sizes up to at most twenty ×1
sizes up to between 6 and 16 ×1
skipping the certain one is worth exactly one, whatever the setting ×1
so does the threshold set at the median of the maximum ×1
some permutation avoids the board ×1
tables of three or more, eleven guests at most ×1
the alternating sum reaches the same number ×1
the arrangement is a permutation of its own places ×1
the arrangement names every object exactly once ×1
the best achievable rank rises with the size of the field ×1
the best rule does at least as well as one threshold ×1
the best rule for three values has expected rank about 1.3915 ×1
the best rule keeps at least 0.745 of the prophet's expected maximum ×1
the best rule looks at some of them and not all of them ×1
the best rule with one bar per position has expected rank about 1.4009 ×1
the best threshold is heading for one over e ×1
the best threshold rises with the field ×1
the board is one the family draws ×1
the case is secretary, constant or custom ×1
the case is uniform or tight ×1
the chance falls as the field grows ×1
the distribution is one the view knows ×1
the exhaustive check is over 4 to 8 candidates ×1
the exhaustive count is drawn for between 3 and 8 objects ×1
the expected rank rises with the number of values ×1
the field has between 4 and 400 candidates ×1
the first value is kept only below a third, so a later value is kept only when it leads ×1
the full alternating sum counts the numbers up to 1000 free of 2, 3, 5, 7, 11, 13 ×1
the full sum is the chance, found without it ×1
the grid of every arrangement is drawn for at most 5 objects ×1
the largest field drawn is already close to that limit ×1
the limit curve peaks at one over e ×1
the mean number of matches is 1 ×1
the number of objects is in the range this view can enumerate ×1
the oracle is never beaten ×1
the placements drawn are all of them ×1
the plans with no seating are exactly 3+3, 4+5 and 3+3+5 ×1
the probability is strictly between nought and one ×1
the product of the failures times the sum of the odds is the same chance ×1
the rank the rule will accept gets stricter as more remain ×1
the ratio is drawn up to between 2 and 10 objects ×1
the rolls that show every face are the onto maps, counted by the same sum ×1
the rook polynomial of disjoint blocks is the product of theirs ×1
the running total ends at the count by search ×1
the schedule seats every allowed pair side by side exactly once ×1
the settings are between nought and one ×1
the share stays above 0.745 however heavy the tail ×1
the shortfall approaches the half as the setting shrinks ×1
the sizes drawn are between 3 and 400 ×1
the standard demanded rises with the number still to come ×1
the standard for acceptance falls as the end approaches ×1
the start the odds rule picks is the best start ×1
the two boards drawn have the same rook numbers ×1
the value grid has between 200 and 2000 steps ×1
the value kept is the first below the line ×1
the view is one the family draws ×1
this plan has a seating ×1
Touchard's formula equals the count by search ×1
Touchard's sum equals the count by search ×1
two choices approach e⁻¹ + e^(−3/2) ×1
two forbidden cells attack exactly when they are neighbours on the cycle ×1
two to eight primes ×1
using the first value at the second step does better than a fixed bar ×1
whenever the odds reach one, the rule wins at least one time in e ×1
which is far above what the relative-ranking rule achieves ×1
with 1 choice among 8, every order counted agrees with the plan ×1
with one choice the plan is the classical rule ×1
with one object there is nothing to find, and the search finds nothing ×1
with three it is 3/2 ×1
with two candidates the best expected rank is 5/4 ×1
with two it wins three times in four ×1
with two values the best threshold rule has expected rank 5/4 ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Probability

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.

Probability

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.

Probability

Add the odds from the end

Watch a sequence of independent events and try to stop exactly on the last one that happens. Add up the odds of the events from the end backwards until the total reaches one, and stop at the first success from there. That rule is the best possible for any probabilities whatever, and the secretary problem is the special case in which the chances are one over the position.

Probability

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.

Probability

Giving up on the best

The secretary rule treats landing the second-best exactly as badly as landing the worst, which is a strange thing to want. Ask instead for the smallest average rank and the answer is about the fourth-best candidate — whatever the size of the field, and whether it is ten or ten million.

Probability

Half of what an oracle takes

Compare an online rule not against the best it could have done but against a rule that has seen every value in advance. One fixed threshold secures half of what the oracle collects, whatever the distributions are — and there is an example on which half is all there is.

Probability

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.

Probability

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.

Probability

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.

Discrete

The colouring nobody has ever seen

Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.

Analysis

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.

Probability

The rank that remembers every value

Values arrive one at a time, each must be kept or discarded on the spot, and the aim is to keep one whose rank among all of them is low on average. Told only who is leading, the best rule gets 3.87. Shown the values, a rule gets below 2.33 — and how much lower the best possible rule goes is not known, because the rank of what is kept depends on every value seen, and the best rule may need to remember all of them.

Probability

The thresholds that nest

Allow a second acceptance in the secretary problem and the chance of holding the best rises from about 37 per cent to about 59. The best rule is still a threshold — but one threshold for each number of choices still in hand, the earlier ones starting sooner, and each additional choice buying less than the one before.

Probability

When every value comes from the same hat

A rule that sees values one at a time and must keep or discard each on the spot can guarantee half of what a prophet collects, and no more, when the values come from different distributions. When they all come from the same one, the guarantee rises to 0.745 — and a single fixed threshold, set so that each value crosses it with chance 1/n, already secures 1 − 1/e. For bounded values the best rule collects nearly everything; only a heavy tail, where one enormous value carries the prize, keeps the gap open.

Probability

When the numbers are shown

The secretary rule wins a third of the time and cannot do better, because it is told only who is ahead. Show the actual values and say where they came from, and the same problem is won three times in five — by a standard that falls as the end approaches.

Probability

When to stop looking

Candidates arrive one at a time in a random order. Each must be accepted or rejected on the spot, with no going back and no way to know what is still to come. The best possible rule is to look at about a third of them and then take the first one that beats everything seen — and it works about a third of the time, however many there are.

The whole library · What the figures prove