Permutation
Named by 39 essays across 8 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 asserted 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.
Named alongside it
The objects these essays reach for when they reach for this one.
Counting argumentExhaustive searchParityCounting two wayse, the numberInvariantDerangementEuler characteristicGenerating functionGroup actionSymmetryAssignment