Permutation
Named by 61 essays across 11 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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