Concept

Permutation

A rearrangement of a collection that sends each member to one place and leaves nothing doubled up. The parity of one is invariant under the way it is written as swaps, which is why some puzzle positions are unreachable.

Named by 61 essays across 11 fields — each of them below, with the objects they name alongside it.

Every relabelling of a 4-gon's corners, and the 8 that are motions. All 24 permutations of the corners drawn one by one, with the 8 that preserve every distance marked; the rest deform the polygon and are not symmetries.

Eight ways to leave a square alone

A square can be picked up and put back so that nothing looks different. There are exactly eight ways to do it, and the number is not taken on trust here — it is what a search through all twenty-four relabellings of the corners comes back with.

algebra · Symmetry groups
16 colourings in 6 classes. Every way of colouring the corners, with the ones a motion carries to each other placed on the same row; the number of rows is the number of genuinely different colourings.

Colourings nobody can tell apart

Sixteen ways to colour four corners in two colours, and only six of them are genuinely different. The count can be got by pooling the sixteen — or by never forming a single class and instead averaging how many colourings each motion leaves untouched.

algebra · Symmetry groups
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.

probability · Inclusion exclusion
5,040 orders, 7 thresholds, one best rule. For each number of candidates passed over, the share of the 5,040 possible arrival orders in which the rule ends up with the best of the 7. The count is exhaustive.

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.

probability · Optimal stopping
A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

applied · Assignment
The permutation (1 3 4 2) drawn as 4 strings, crossing 3 times. A permutation drawn as strings running from a row of numbered pegs to another, with every place two strings cross marked, and the crossing count checked against the number of pairs that are out of order.

The crossings that will not come out even

Draw a rearrangement as strings from one row of pegs to another and count where they cross. The count depends on how the strings are drawn; whether it is odd or even does not, and that single bit is what makes determinants exist and a sliding puzzle unsolvable.

algebra · Permutation parity
Every order of arrival for three partners, and what each player adds. A table with one row per order in which the players could arrive, giving what each adds to the group already present, and the average of each column as that player's share.

The order everybody arrives in

Three people jointly earn nine, and the question is what each is owed. Ask instead what each adds on walking into a room the others are already in, average that over every order they could have arrived in, and four modest conditions leave no other answer.

applied · Shapley value
Every turn that leaves a cube where it was. A cube in wireframe beside a table of its rotation axes: 3 of order 4, 4 of order 3, 6 of order 2, totalling 24 turns including the one that does nothing.

The five solids as three groups

There are five regular solids and only three groups of rotations between them, because a solid and its dual share their symmetries exactly. The largest of the three is the smallest group with no way of coming apart, which is why the general equation of the fifth degree has no formula.

geometry · Regular polyhedra
A sequence of 3² with no climb and no fall longer than 3. 10 terms plotted in order, each labelled with the longest climb and the longest fall ending at it; the first 9 keep both counters at 3 or below and the last one cannot.

The sequence that cannot avoid a staircase

Any ten numbers in a row contain four that climb or four that fall. The proof gives every term a pair of counters, notices that no two terms can share a pair, and is finished — with a bound that is exactly right.

discrete · Ramsey theory
Sampling the orders, and how fast the answer arrives. The largest error in the estimated shares against the number of orderings sampled, both on logarithmic axes, with the square-root rate drawn through the first point.

Too many orders to list

The rule is an average over every order the players could have arrived in. At seven players that is five thousand orders and at twenty it is more than there are seconds in the age of the universe — so the average is sampled, and the error falls at a rate that can be measured.

applied · Shapley value
A parallelepiped of volume 2.94. The image of the unit cube under a three-by-three matrix, beside the six signed products whose sum is its volume.

The only function that behaves like a volume

Ask for a function of the columns of a matrix that scales when a column scales, vanishes when two columns agree, and gives one on the identity. Three conditions, and there is exactly one such function in every dimension.

algebra · Determinant
A determinant of −5 and a permanent of 23 from the same six products. The six products of a three-by-three matrix listed once, added with signs to give the determinant and without signs to give the permanent, with a row operation applied to both.

The same sum without its minus signs

Delete the signs from the determinant's sum over permutations and what is left counts things directly rather than by cancellation. It is a better count and a far worse object — because the cancellation was what made the determinant computable.

algebra · Determinant
A cycle showing every pair from 5 things exactly once. The complete graph on 5 points with an Eulerian circuit drawn, and the cyclic sequence of symbols it spells; every window of two consecutive symbols is a different pair.

A cycle for every pair

A cyclic sequence in which every window of two consecutive symbols is a different pair of things. For five things it exists and for four it does not, and in both cases there are exactly as many pairs as there are places to put them.

computation · De bruijn
16 ways to sort it. A small order with its 16 linear extensions counted, and for each incomparable pair the fraction of extensions putting one before the other.

How many ways to sort it

An order says some things come before others and leaves the rest open. Counting the orderings consistent with it measures how much is still unknown — and the counting is as hard as any counting problem gets.

discrete · Posets
The 6 corners, and nothing in between. The 6 permutation matrices of size 3, drawn as grids. A search over every table of shares on a fine grid finds these and only these as corners of the set.

The corners are whole assignments

A table of shares can be written as a lottery over whole assignments, which one worked example shows. The general statement is that the corners of the set of such tables are exactly the whole assignments, and that single fact is why the whole subject is easy.

applied · Assignment
One table of shares, two different lotteries. A doubly stochastic table decomposed into whole assignments twice, by two different orders, giving two mixtures that reconstruct the same shares.

One table, two lotteries

A table of shares says what fraction of each task each person does. It does not say how — the same table is a mixture of whole assignments in many different ways, and the differences are exactly what the people being assigned would care about.

applied · Assignment
The half of 24 permutations that commutators reach. A block of 24 squares, one per permutation, with the 12 generated by commutators shaded, beside bars counting the homomorphisms to each cyclic group.

The only bit that survives

A shuffle can be called even or odd, and the label behaves under composition. Ask whether some cleverer label — a number out of three, or out of four — could behave the same way, and the answer is that nothing else can — one bit is exactly what a permutation gives up.

algebra · Permutation parity
A 2×3 sliding puzzle: 360 arrangements of 720 can be reached. Two arrangements of a small sliding puzzle side by side, the solved one and the one with two tiles exchanged, with the count of positions reachable by sliding found by walking every move.

The puzzle that is exactly half solvable

A sliding puzzle sold with two tiles swapped is not a hard puzzle; it is an impossible one, and the proof is a quantity that no slide can change. The same argument, run three times at once, says that one arrangement of a scrambled cube in twelve is reachable.

algebra · Permutation parity
The character table of the permutations of 4 places, computed from traces. A table with one row per irreducible representation and one column per conjugacy class, giving the trace of the matrix each representation assigns, with the dimension column marked.

When the label may be a matrix

A permutation carries exactly one bit into any commutative target, and commutativity is the restriction doing all the work. Drop it — let the label be a matrix — and what survives is a short finite table, computed here from traces and checked for orthogonality over every pair of rows.

algebra · Permutation parity
Up to 4 choices among 60, and the thresholds that nest. For 60 candidates in random order and 1, 2, 3, 4 acceptances, the chance of ending with the best among those accepted — 37.3%, 60.0%, 74.3%, 83.5% — and where along the sequence the rule starts accepting for each number of choices in hand.

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 · Optimal stopping
2 sheets branched over 4 points of a sphere: a surface of genus 1. A 2-sheeted branched covering of the sphere with 4 branch points, drawn as 2 rows of sheets over a centre and the branch points, with the sheets joined where each point's permutation cycles them. Counting cells gives Euler characteristic 0, matching the Riemann–Hurwitz formula, and genus 1.

What a branch point subtracts

Let the sheets of a covering meet at a few points and the count stops multiplying — but it fails by an amount that can be read off each point's permutation. Cut the sphere into a star, lift the cells, and the Riemann–Hurwitz formula falls out of a subtraction. The same count then turns out to be necessary and not sufficient.

topology · Covering spaces
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.

probability · Inclusion exclusion
The 6 ways to deal 4 labels between pieces of size 2 and 2. Every way of splitting 4 labels between a piece of size 2 and a piece of size 2, listed as two rows of boxes each. The count is the binomial coefficient that distinguishes a labelled product from an ordinary one.

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.

discrete · Generating functions
Permutations of n things, by how many pairs they put in the wrong order. A table whose row n and column k hold the number of permutations of size n whose inversions is k, with each row's total beside it — the plain count the one-variable series gives.

The coefficient that is a polynomial

Add a second variable to track a statistic and each coefficient stops being a number. Set the new variable to one and the old count comes back untouched; leave it in and the mean of the statistic is a derivative rather than an average.

discrete · Generating functions
Six lists of cycle shapes, and how many coverings each has. A table of lists of cycle shapes over a sphere, each with the Euler characteristic the Riemann–Hurwitz count gives, the number of lists of permutations with that product, and the number of those that connect all the sheets.

A count that can say zero

The branched count ends on a list of cycle shapes that passes every test and describes no covering. There is an exact formula for how many coverings a list has — a sum over the character table of a symmetric group — and it returns nought without giving any reason why.

topology · Covering spaces
The odd ring that forbids a stable pairing. The ranked lists of 6 people and a stable partition of them drawn on a circle: pairs as plain chords, a ring of three or more as arrows from each person to the one they hold. An odd ring is present, as it is in every stable partition of this instance.

A ring that no pairing can break

Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.

applied · Stable matching
Every way to pair the edges of a hexagon. Chord diagrams of all 15 pairings of a 6-gon's edges, shaded by the surface each gluing makes: 5 spheres, 10 tori.

Every way to pair a polygon's edges

A hexagon's six edges can be paired in fifteen ways. Glue each pair head to tail and five of the fifteen give a sphere and ten give a torus; an octagon's 105 pairings give 14 spheres, 70 tori and 21 surfaces with two handles. The spheres are exactly the pairings whose chords never cross, and the whole table obeys one recurrence found in 1986.

topology · Surface classification
A random pairing of 24 edges. Chord diagram of one uniformly random pairing of a 24-gon's edges, corners coloured by the vertex they become. a 24-gon with its edges paired at random and glued head to tail: the 24 corners fall into 3 vertices, so the surface has genus 5, against a most possible of 6.

The surface a random gluing makes

Pair the edges of a large polygon at random and glue each pair head to tail. The surface almost always has nearly as many handles as the polygon allows: a thousand edges leave about seven and a half vertices, and the genus is within four of its ceiling of 250. The vertices behave like the cycles of a random permutation, and their average is a harmonic number.

topology · Surface classification
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.

probability · Inclusion exclusion
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.

probability · Inclusion exclusion
The three pairings of the roots of x⁴ + x + 1. Three panels each showing the same four roots of a quartic in the complex plane, joined in a different way into two pairs, with the value of the sum of the pair products beneath.

Three ways to pair four roots

Four roots can be split into two pairs in exactly three ways, and the three numbers r·r′ + r″·r‴ those pairings give are the roots of a cubic whose coefficients can be read straight off the quartic. That cubic is where Ferrari's formula gets its cube roots, and it is also a verdict: whether its roots are rational decides which of the twenty-four symmetries the quartic's roots actually have.

algebra · Galois correspondence
Pollak's circle: one rotation in every n + 1 parks on the line. Several circles of numbered spots, each showing where cars park when every preference in a list is rotated by a fixed amount, with the one rotation that leaves the last spot empty highlighted.

Cars that park, and trees that grow

Three cars arrive at a one-way street with three spaces; each has a favourite space, drives to it, and takes the first free one from there on. Of the 27 lists of favourites, exactly 16 let every car park — the same 16 as the labelled trees on four points. The reason is a circular street with one extra space, on which every list parks and exactly one rotation of it leaves the extra space empty.

discrete · Labelled trees
Every residue joined to 2 times itself, on a dial of 199. A circle with 199 equally spaced points and a chord from each point k to the point 2k mod 199, with the 1-cusped curve the chords envelope drawn dashed.

Multiplying every number on the dial at once

Join every residue on a dial to twice itself and the chords draw a heart-shaped curve with one cusp; join each to three times itself and the curve has two. The picture is the whole multiplication map at once, and it holds three facts: the map splits the dial into cycles whose lengths are orders, those cycles on a dial of 2ⁿ − 1 are the binary necklaces of length n, and the curve is the caustic light draws inside a cup.

discrete · Modular arithmetic
Every reachable arrangement of the 3×3 sliding puzzle, by moves from solved. A bar chart of the 181440 reachable arrangements of the 3×3 sliding puzzle by the fewest moves that solve them, rising to a peak at 24 and falling to 2 at the maximum distance 31.

Thirty-one moves from solved

Parity settles which half of a sliding puzzle's arrangements can be reached and is silent about how far away any of them is. Searching every reachable arrangement of the three-by-three tray answers the second question exactly — two arrangements sit thirty-one moves out — and parity turns up again, this time as a law about distance.

algebra · Permutation parity
Which arrangements sliding tokens reach, on nine graphs, against Wilson's theorem. A table of 9 small graphs drawn as icons, each with the searched count of reachable token arrangements and the fraction of all arrangements it is: a six-cycle 5/120; K₂,₃ 12/24; the 2×3 tray 60/120; a house 24/24; a six-cycle with one chord 120/120; a wheel of six 120/120; θ, inner paths 2, 2, 2 2520/5040; θ₀, inner paths 1, 2, 2 120/720; θ, inner paths 1, 3, 3 20160/40320.

Which graphs let the tokens go anywhere

A sliding puzzle is a graph with a token on every vertex but one. Richard Wilson found in 1974 what every such puzzle can reach, and the answer has a surprise in it — the half the tray is stuck with is not a fact about permutations at all, but about the board being two-coloured — and one exception, a graph of seven vertices that reaches exactly 120 of 720.

algebra · Permutation parity
PRIMEGAME: fourteen fractions whose powers of two are the primes. The size in binary digits of the numbers produced by Conway's PRIMEGAME from 2 over 40000 steps, with the pure powers of two marked; their exponents are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Fourteen fractions that list the primes

Change the Collatz rule so that the multiplier depends on the remainder modulo some other number than two, and the resulting maps can compute anything a computer can. John Conway proved it in 1972, which means no method can decide, for every such map, whether its orbits come down — and fourteen fractions, applied in order, turn out to be enough to print every prime.

dynamics · Collatz
How far a deck of 52 is from random after each riffle shuffle. A bar chart over one to 12 riffle shuffles of the exact total variation distance from a uniformly random deck. The bars stay near one for the first few shuffles and drop sharply around 8.

The forgetting that happens all at once

A single small chain forgets its start gradually, a little more with every step. A family of large ones can do something different — stay almost perfectly informed about where it began, and then lose all of it inside a window far shorter than the wait. That cliff is the cutoff phenomenon, and it is why "seven shuffles" is an answer rather than a convention.

probability · Markov chains
Six permutations as six arrows between three symbols. A directed graph with 3 vertices and 6 arrows, one per permutation of 3 symbols in shorthand, every vertex with two arrows in and two out, numbered in the order of an Euler circuit spelling 213231.

Every ordering once, around a cycle

No cycle can show every ordering of three symbols as a window of three: a window holding each symbol once forces the next symbol to repeat the one just dropped, so the sequence has period three and shows three orderings of six. Two repairs work. Write each ordering by its first two entries and the transitions form a balanced graph, so Euler's theorem hands over the cycle at once. Or add a fourth symbol and ask only that each window keep a different relative order — which works too, but no graph explains why.

computation · De bruijn
Descents of 10 as a sum of 9 hidden coins. Bars of 9 coin probabilities beside a bar chart of the descents distribution for n = 10, with dots giving the coin-sum distribution landing on every bar.

Coins hidden in the roots

The polynomial that counts permutations by their descents has no product formula, and nothing in the definition of a descent is a coin toss. But every root of the polynomial is real and negative, and a polynomial like that is a product of coins in disguise: each root r is a coin landing heads with chance 1/(1 − r). The descent count of a random permutation is exactly a sum of independent coins nobody can point to — which is why it is bell-shaped, and why its coefficients obey inequalities the inversion count breaks.

discrete · Generating functions
No pair of weights modulo ten catches everything. Two 10 × 10 grids over pairs of alternating weights modulo ten, shaded by the share of single errors and of swaps each catches. No pair is full in both; weights 3 and 1, ringed, catch every single error and 88.9% of swaps.

Ten digits need a symmetry that does not commute

A check digit should catch one wrong digit and two neighbours swapped. Over eleven symbols a weighted sum does both; over the ten decimal digits no weighted sum can, no scheme of any shape built on adding modulo ten can, and the reason is the same as the reason Euler's thirty-six officers cannot be paraded. What works is the ten symmetries of a pentagon, which do not commute.

computation · Error-correcting codes
A function on nine points, and the tree with two marks it becomes. Left: a function on 9 points as arrows, with cycles through 2, 5, 7 and trees hanging into them. Right: the tree Joyal's rule makes from it, a path from head 7 to tail 2 with the same trees hanging below.

Every function is a tree with two marks

There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.

discrete · Labelled trees
The twenty maps x ↦ ax + b modulo 5, as permutations of five roots. A four-by-five grid of pentagons; in each, arrows show where the map ax + b modulo 5 sends each of the five corners. Rows are the slopes 1, 4, 2, 3; columns the shifts 0 to 4.

The quintics that have a formula

No formula solves every equation of degree five, and yet x⁵ − 2 is solved by a fifth root and x⁵ − 5x + 12 by a longer expression of the same kind. A quintic can be solved by radicals exactly when the symmetries of its roots fit inside one group of twenty — the maps x ↦ ax + b on the numbers modulo 5 — and two exact tests on its coefficients say whether they do.

algebra · Galois correspondence
Every pair of rearrangements of four letters, and what the two generate. A 24 by 24 grid of ordered pairs of permutations of four letters: 216 generate S4, 96 generate A4, 264 generate a smaller subgroup.

Two random shuffles reach every shuffle

Pick two ways of rearranging n letters at random and allow them to be repeated in any order. Almost always the two together reach every rearrangement there is, or every even one — and when they fail, the usual reason is a coincidence about a single letter that both happen to leave alone. Eugen Netto guessed it in 1882 and John Dixon proved it in 1969.

algebra · Symmetry groups
The 16 zigzag arrangements of 5 numbers. All alternating permutations of 1..5: 13254, 14253, 14352, 15243, 15342, 23154, 24153, 24351, 25143, 25341, 34152, 34251, 35142, 35241, 45132, 45231.

The tangent counts zigzags

Arrange the numbers 1 to n so that they go up, down, up, down. There are 1, 1, 2, 5, 16, 61, 272 such arrangements, and those are, multiplied by factorials, the Taylor coefficients of tan x and sec x — the odd lengths from the tangent, the even from the secant. Désiré André proved it in 1879 by splitting a zigzag at its largest number, and the split turns out to be the derivative of the tangent written out term by term.

analysis · Circular functions
Every swap-proof scrambling, graded on twins and jump swaps. 34040 permutations; twin errors caught range 50–86 of 90, jump transpositions 600–848 of 900; Verhoeff's at (848, 86).

The best of thirty-four thousand scramblings

Verhoeff's check digit multiplies digits in the symmetry group of a pentagon after scrambling each one a different number of times, and 34,040 scramblings make it catch every swap of neighbours. Graded on the rarer errors, none of them catches everything, the best catch 86 of 90 doubled-digit slips and 848 of 900 swaps across a digit — and the scrambling Verhoeff published in 1969 is one of the forty that are best at both.

computation · Error-correcting codes
Ten dots that never repeat a step. Welch array p=11, g=2: 0,1,3,7,4,9,8,6,2,5; difference triangle rows: 1 2 4 -3 5 -1 -2 -4 3 / 3 6 1 2 4 -3 -6 -1 / 7 3 6 1 2 -7 -3 / 4 8 5 -1 -2 -4 / 9 7 3 -5 1 / 8 5 -1 -2 / 6 1 2 / 2 4 / 5.

Dots that never repeat a step

Place n dots on an n-by-n grid, one in each row and column, so that no two pairs of dots are joined by the same step. These Costas arrays were invented for sonar, and finite fields build them: a primitive root modulo a prime gives one family, a pair of primitive elements in any finite field another. Yet the constructions account for almost none of the arrays that exist — 92 of the 2,160 of order ten — and for orders 32 and 33 nobody has found a single one.

computation · Finite fields
Fifty-two cards, swapped the naive way. Naive shuffle, n=52: max ratio 1.3522 at card 2 → place 1; min ratio 0.7429.

A perfect coin and a biased shuffle

Give a program a perfect source of random numbers and ask it to shuffle a deck by swapping each card with a card chosen from anywhere in the deck. The result is biased, provably and for every deck of three or more cards: there are nⁿ equally likely runs and n! orders, and the first number is never a multiple of the second. In a deck of 52 some card-and-place pairs come up a third more often than they should. Swapping only with cards not yet placed fixes it; swapping only with later cards makes nothing but single cycles.

computation · Pseudorandomness
Scrambled in three steps, restored in thirty. Cat map on 61×61: period 30; frames at steps 0, 1, 2, 3, 7, 22, 30; lit pixels 693.

A chaotic map that always comes back

Arnold's cat map stretches a square by the golden ratio squared and wraps it round, and any two nearby points fly apart: a difference of a million-millionth fills the square in twenty-seven steps. Apply the same map to a picture made of pixels and it dissolves into noise within a few steps — and then, after exactly thirty steps on a 61 × 61 grid, every pixel is back where it started. Chaos and exact return are both true, and the Fibonacci numbers decide how long the return takes.

dynamics · Sensitive dependence
The largest prime factor, as a power of the number. Share of n with log P(n)/log n ≤ s: at s=0.5, n≤10⁴ 0.268, n≤10⁷ 0.272, Dickman 0.307; median e^(−1/2) = 0.6065; largest gap at 10⁷ 0.061.

The largest prime in a typical number

Count a number's prime factors and the answer is about log log n. Ask instead how big the largest one is, and the answer is a power of n with a law of its own: half of all large numbers have a prime factor above n^0.6065, and the share whose primes all stay below n^(1/u) is Dickman's ρ(u), a function defined by its own past. The same law governs the longest cycle of a random shuffle, and there it arrives at once; for the numbers themselves, at ten million, it is still visibly on its way.

number · Unique factorisation
Every ordering of four in thirty-three symbols. 123412314231243121342132413214321: windows 1234 2341 3412 4123 (1231) 2314 3142 1423 4231 (2312) 3124 1243 2431 4312 (3121) (1213) 2134 1342 3421 4213 (2132) 1324 3241 2413 4132 (1321) 3214 2143 1432 4321.

The shortest string holding every ordering

Thirty-three symbols hold all twenty-four orderings of 1, 2, 3, 4 as blocks of four in a row, and no shorter string does. The formula 1! + 2! + … + n! gives the shortest length for up to five symbols and was believed for all of them — until a string of 872 for six beat its 873, and a lower bound posted anonymously on a forum left everything between 867 and 872 open.

computation · De bruijn
Fourteen truth functions of three letters. table 00000000: 2; table 01101001: 2; table 00001111: 6; table 00111100: 6; table 00010111: 8; table 00011000: 8; table 00000001: 16; table 00010110: 16; table 00000011: 24; table 00000110: 24; table 00011011: 24; table 00011110: 24; table 00000111: 48; table 00011001: 48.

Truth tables up to renaming

There are 256 truth functions of three letters, but many differ only in which letter is called what, or whether a letter or the answer is negated. Counted up to such renamings there are fourteen. For four letters there are 222, for five 616,126 — and almost every function of many letters is changed by every renaming, so the count settles into a simple division.

logic · Truth functions
Every failed branch datum up to eight sheets. Exceptions with three branch points: 4: 31|22|22; 6: 51|222|222; 6: 42|411|222; 6: 42|222|222; 6: 33|33|3111; 6: 33|321|222; 8: 71|2222|2222; 8: 62|5111|2222; 8: 62|2222|2222; 8: 611|422|2222; 8: 53|3311|2222; 8: 53|2222|2222; 8: 521|422|2222; 8: 5111|44|2222; 8: 5111|422|422; 8: 44|44|311111; 8: 44|3221|2222; 8: 431|332|2222; 8: 422|332|2222.

The lists no covering can have

A covering of the sphere by itself with three branch points is three permutations of the sheets whose product is the identity. The Riemann–Hurwitz count says which lists of cycle shapes might work, and a search through every permutation says which do. Up to thirteen sheets, 150 lists pass the count and fail the search — and not one of them has a prime number of sheets.

topology · Covering spaces
Every order of nine cards, and the ones a seed can reach. 16-bit LCG, 65,536 seeds, Fisher–Yates on 9 cards (high bits): 62616 of 362880 orders reached.

A seed is a deck

A shuffle that is perfectly correct, driven by a generator that passes every statistical test, can still deal almost none of the possible decks. A shuffle program is a function from the generator's starting state to an ordering of the cards, so it can never produce more orderings than the generator has states: a 32-bit seed reaches one deck in about 10⁵⁸. On nine cards and a 16-bit generator every case can be checked — 62,616 of the 362,880 orders are ever dealt — and on a full deck, six cards on the table are enough to name the seed and every card still to come.

computation · Pseudorandomness
Thirteen subgroups of index three. a=012 b=120; a=021 b=102; a=021 b=120; a=102 b=021; a=102 b=120; a=102 b=210; a=102 b=201; a=120 b=012; a=120 b=021; a=120 b=102; a=120 b=120; a=120 b=210; a=120 b=201

Counting the subgroups of a free group

The free group on two letters has one subgroup of index 1, three of index 2, thirteen of index 3, then 71, 461, 3,447 and nearly thirty-two million of index 10. Each is a covering of a figure-eight with a marked sheet, so counting them is counting pairs of permutations that join every sheet to every other. Marshall Hall did it in 1949 by sorting every pair by how far one sheet can travel, and the recursion that comes out says the count is almost exactly n times n factorial.

topology · Covering spaces
How many subgroups of each index a surface group has. genus 1: 1,3,4,7,6,12,8,15; genus 2: 1,15,220,5275,151086,6605004,362069912,26370058035; genus 3: 1,63,7924,2757307,2081946006,3233368740252,9037199115520808,42295362888015649395; free F2: 1,3,13,71,461,3447,29093,273343.

The subgroups of a surface group

A covering of a surface with n sheets is a choice of permutations for its handles whose commutators multiply to the identity, and counting those choices is a question about the characters of the symmetric group. Only their dimensions are needed — the numbers of ways to fill a Young diagram — and they give the torus σ(n) subgroups of index n, the genus-two surface 15, 220, 5,275, 151,086, and every surface a count that soon becomes 2n times a power of n factorial.

topology · Covering spaces
The far end of a sliding tray falls as holes are added. Exhaustive search of the 2×3, 2×4 and 3×3 sliding trays with one to all-but-one holes. Far ends for the 3×3 tray: 31, 24, 21, 17, 13, 10, 7, 4; averages 21.97, 16.04, 12.70, 9.99, 7.88, 5.92, 3.75, 2.00.

A second empty square

With one empty square a sliding tray can reach exactly half its arrangements, and the half it misses is guarded by a sign. Leave a second square empty and the guard disappears — every arrangement is reachable, two tiles can be exchanged in four moves, and the far end of the three-by-three tray comes in from thirty-one moves to twenty-four. Searching every tray with every number of holes shows what each extra square of room is worth.

algebra · Permutation parity
A sorting network on 8 wires. Batcher's odd-even merge network with 8 wires, 19 comparators and depth 6; it sorts every input, checked on all 256 strings of noughts and ones.

A sort that never looks at the answers

Most sorting decides its next comparison from the last one. A sorting network decides them all in advance: a fixed sequence of swaps-if-out-of-order, wired up before any number arrives. Whether such a thing sorts everything can be settled by trying 2ⁿ strings of noughts and ones instead of n! orderings. Nineteen comparators sort eight numbers, and proving that nothing shorter sorts eleven took decades and a satisfiability solver. Over neighbours only, one single test, the reversed row, decides the whole question.

computation · Permutation parity
A circle with a count running round it. Josephus circle, n=41, k=3: removal order 3,6,9,12,15,18,21,24,27,30,33,36,39,1,5,10,14,19,23,28,32,37,41,7,13,20,26,34,40,8,17,29,38,11,25,2,22,4,35,16,31.

The last place in the circle

Forty-one people stand in a circle and every third is removed. Which place is safe? Counting round by hand is not necessary: the survivor is a running sum on a dial that grows by one each step. With every second person it is n's binary digits rotated by one place, which is a tidier fact than anybody asked for. With every third the rule depends on repeatedly multiplying by three halves and rounding up, and the constant it reaches, 1.62227…, has no known closed form.

discrete · Modular arithmetic
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.

probability · Inclusion exclusion
A restaurant with room for one parameter. Seeded Chinese restaurants of 60 customers: 0.5: 4 tables, largest 44; 2: 10 tables, largest 17; 10: 22 tables, largest 10.

A restaurant and a shuffled deck

Each new customer sits at a table with chance proportional to the people there, or starts a new one with weight θ. That one rule gives the kinds of species in a catch and the alleles at a gene. At θ = 1 it is exactly the cycles of a shuffled deck, 62.4% of which lie in the longest, and the same shares describe the largest prime factors of a random number.

probability · Birthday problem
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.

probability · Inclusion exclusion

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchCounting argumentParityCounting two waysInvariantCyclee, the numberConjugacy classCovering spaceDerangementEuler characteristicOrbit

All concepts