Concept

Generating function

A series whose coefficients are the terms of a counting sequence. Multiplying two of them convolves the coefficients, so combining independent choices becomes multiplication and a recursion becomes an equation that can be solved.

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

The partition 5 + 4 + 2 + 1 and its conjugate. A row of dots for each part, and the same dots read down the columns instead.

A diagram turned on its side

Write a partition as rows of dots, then read the columns instead. Every theorem in this essay is that one move, and the move proves things that no formula suggests.

number · Partitions
A product of 3 polynomials, and what its coefficients count. The coefficients of a product of small polynomials, with the combinations of choices that reach one marked total written out beneath it.

A polynomial that counts

Hang a counting sequence on the powers of a variable and the two ways of combining choices — this and that, this or that — become multiplication and addition, so a recursion turns into an equation and the equation can be solved.

discrete · Generating functions
The partition product's coefficients to q¹². A row of series coefficients computed by expanding a product, beside the same numbers obtained another way.

Every partition, hidden in a product

Multiply out one factor for each part size and the coefficient of q to the n is the number of partitions of n. Nothing is being approximated: the product is a bookkeeping device that does the counting by multiplying.

number · Partitions
The product of (1 − qᵏ), and what survives at 12. The coefficients of the pentagonal product drawn as signed bars, with the partitions into distinct parts that Franklin's move leaves unpaired.

The terms that cancel almost everything

Multiply out the product of 1 − q, 1 − q², 1 − q³ and so on, and nearly every coefficient is zero. What survives is a single plus or minus one at 1, 2, 5, 7, 12, 15 — and the reason is a way of pairing partitions off so that each pair cancels.

number · Partitions
p(n) to 60, against the Hardy–Ramanujan estimate. The number of partitions of each number up to sixty on a logarithmic scale, with the asymptotic estimate drawn over it and the ratio of the two tabulated.

The size of a number with no formula

There is no closed expression for the number of partitions of n. There is an expression for how large it is — with a square root in the exponent and a π in front — and it is accurate enough that rounding a few terms of its refinement gives the exact count.

number · Partitions
Every fifth partition count divides, and the rank that says why. A row of partition counts with the ones in a congruence class marked, and a histogram of partitions sorted by rank.

Every fifth one divides

p(4) is 5, p(9) is 30, p(14) is 135, and every partition count at a number leaving four on division by five is divisible by five. Ramanujan read it off a table; the explanation is a way of splitting those partitions into five equal heaps.

number · Partitions
The equation the objects satisfy. A diagram of the decomposition C = 1 + xC², with a table of the first several coefficients computed two ways: by the convolution the equation prescribes, and from the closed form.

The equation a sequence satisfies

Write the whole sequence as the coefficients of one series, and the recursion becomes an equation with a square in it. Solving the equation by the ordinary quadratic formula produces the closed form, the growth rate and the correction term, none of which the recursion offers.

discrete · Catalan numbers
The coefficients of (1 + x)¹² sorted by remainder mod 3. The binomial coefficients of the 12th power coloured by the remainder of their index on division by 3, beside the 3 points one plus a root of unity, whose powers averaged pick out each colour's total.

Every third coefficient

Add every third number in the twelfth row of Pascal's triangle and the answer is 1366 — a third of 4096, rounded up. Which way the rounding goes is decided by two arrows of length one in the complex plane, and the same average over the roots of unity counts dice totals, subsets and necklaces.

algebra · Roots of unity
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
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
Random partitions of 1,000, scaled, against their limit shape. The outlines of 4 uniformly random partitions of 1000, scaled by the square root of 1000, lying close to the curve e^(−cx) + e^(−cy) = 1 with c = π/√6.

The shape a random partition takes

There are about twenty-four thousand billion billion billion ways to write 1,000 as a sum of whole numbers. Pick one at random, draw its Ferrers diagram, shrink it by the square root of a thousand, and it is almost exactly the curve e^(−cx) + e^(−cy) = 1 with c = π/√6. So is the next one, and the next. A random partition of a large number has a shape, and the shape is known exactly.

number · Partitions
Two ways of counting that agree at every number. For n up to 40, the counts of partitions with gaps of at least two against partitions into parts congruent to 1 or 4 mod 5, on a logarithmic scale, equal at every n, with the second identity's counts beside them.

Two counts that agree for no visible reason

Write 10 as a sum of whole numbers that differ from each other by at least two, and there are six ways. Write 10 as a sum of numbers that each leave 1 or 4 on division by 5, and there are six ways. The same happens for 20 (thirty-one each), for 40 (three hundred and seventy-four each), for every number anyone has checked and every number there is. The two lists look nothing alike, and no one has found a simple way to turn one into the other.

number · Partitions
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
A spider's matchings have real roots and its independent sets do not. Spider with legs 3, 3, 3: matching polynomial 1, 9, 27, 32, 12, roots -0.5000, -0.2324, -0.5000, -1.4343; independence polynomial 1, 10, 36, 57, 38, 9, 1, 4 non-real roots.

The roots every matching polynomial keeps real

Count a graph's matchings by size and make the counts the coefficients of a polynomial. On every one of 35,664 graphs tested, that polynomial has only real roots — a theorem of Heilmann and Lieb from 1972. Count independent sets instead and the roots wander off the axis on a growing share of graphs, but never on a graph without a claw, and matchings are the independent sets of a graph that never has one.

discrete · Generating functions
A chromatic polynomial with complex roots and log-concave coefficients. Wheel W5: P(x) = x⁶ − 10x⁵ + 40x⁴ − 80x³ + 79x² − 30x; |coefficients| 30, 79, 80, 40, 10, 1; min ratio 2.0000; roots 3.000, 0.000, 2.000−1.000i, 2.000, 1.000, 2.000+1.000i.

Log-concave with nothing to make it so

The chromatic polynomial of a graph counts its colourings, and its coefficients rise to one peak and fall, each squared at least the product of its neighbours. For a real-rooted polynomial that would be automatic. But by nine vertices fewer than one graph in twenty has only real chromatic roots, and the coefficients stay log-concave anyway — on every graph tested, and, by June Huh's theorem of 2012, on every graph there is.

discrete · Generating functions
A partition in two directions is a pile of cubes. Plane partition 5 4 3 1 / 4 3 2 / 3 2 1 / 1 of 29, drawn as stacked cubes; PL(29) = 3759612.

A partition piled into a corner

A partition is a row of numbers that never increases. Let it never increase down the columns too, and it becomes a pile of cubes pushed into the corner of a room. MacMahon counted the piles with one change to Euler's product — each part size k in k colours — and in a box with a product over its cells. The second direction moves the growth from e^(√n) to e^(n^(2/3)), puts ζ(3) where π was, and makes a count that grows with a box's area. One direction further, his guess fails at six.

number · Partitions
The bipartite share falls before it rises. n=1: 1 of 1 (100.00%); n=2: 2 of 2 (100.00%); n=3: 7 of 7 (100.00%); n=4: 41 of 41 (100.00%); n=5: 376 of 388 (96.91%); n=6: 5177 of 5789 (89.43%); n=7: 103237 of 133501 (77.33%); n=8: 2922446 of 4682270 (62.42%); n=9: 116011231 of 246348115 (47.09%).

Triangle-free, and two-sided eventually

Every graph with no triangle and the most edges possible is bipartite. Erdős, Kleitman and Rothschild proved that almost every triangle-free graph is bipartite too — and yet among the 246,348,115 triangle-free graphs on nine labelled vertices, fewer than half are. The share falls before it rises, and the reason is that small graphs are sparse.

discrete · Extremal graphs
Ramanujan's tau, scaled by the power it grows like. τ(n)/n^5.5 for n ≤ 400; τ(1..8) = 1, -24, 252, -1472, 4830, -6048, -16744, 84480; largest |τ(n)|/n^5.5 for n ≤ 10000: 3.2796 at 4841.

The product raised to the twenty-fourth power

Euler's product (1 − q)(1 − q²)(1 − q³)… has the partition numbers for its reciprocal. Raise it to the twenty-fourth power and multiply by q, and the coefficients that come out — 1, −24, 252, −1472, 4830, −6048 — multiply like the primes they are indexed by, stay inside a bound Ramanujan guessed and Deligne proved fifty-eight years later, agree with a divisor sum modulo 691, and know, modulo 23, how a cubic equation factors.

number · Partitions
The twenty-three trees on eight points. 23 shapes on 8 points by Prüfer search; diameters 2,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,7.

How many shapes a tree can take

There are 262,144 labelled trees on eight points and only twenty-three shapes. Labels make counting easy — Cayley's nⁿ⁻² — and shapes make it hard, because a symmetric shape absorbs labellings. The count of shapes comes instead from a recurrence for trees with a root and a theorem of Richard Otter's for taking the root away: in every tree there is exactly one more class of points than of edges. Run to two hundred points, the counts grow like 0.535 × 2.9558ⁿ ÷ n^(5/2), and the same arithmetic counts the alkanes.

discrete · Labelled trees
The forests of a complete graph on four points. K4 forests by size: 1, 6, 15, 16; ratios 2.4000, 2.3438.

The forests a graph can hold

Count the sets of edges in a graph that contain no cycle, sorted by size, and the counts rise and fall in a single peak — more sharply peaked, John Mason conjectured in 1972, than the binomial coefficients with the same number of edges. On every graph with up to six points the strongest of his three inequalities holds, with equality exactly where cycles are too long to matter; on random graphs with nine points it holds with a margin of about one per cent. It was proved for every graph, and every matroid, in 2018.

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

A card game almost nobody wins

Shuffle a deck and deal it face up, calling ace, two, three, up to king and round again, four times through. If a card ever matches the rank being called, the game is lost, and it is won about one time in sixty-two. The chance is 0.016232727…, exact, because the forbidden pairings form thirteen separate four-by-four squares and inclusion–exclusion turns their rook numbers into a sum — a sum whose terms climb past ten before they cancel to a sixtieth, and which is also the integral of a power of a Laguerre polynomial. The obvious guess, e to the minus four, is eleven per cent too high, and two hundred thousand deals can tell.

probability · Inclusion exclusion
When to stop tossing a coin. 1:1 2:2 3:3 4:2 5:3 6:2 7:3 8:2 9:3 10:4 11:3 12:4 13:3 14:4 15:3 16:4 17:5 18:4 19:5 20:4 21:5 22:4 23:5 24:4 25:5 26:4 27:5 28:4 29:5 30:6

When to stop tossing a coin

Toss a fair coin as many times as you like and stop whenever you choose; you are paid the proportion of heads so far. Stopping after a first head pays one, so the only question is what to do after a tail. Waiting for the first moment heads lead pays exactly π/4 on average. Waiting for a lead of two pays exactly ln 2. The best possible rule pays about 0.79295, a number known to six decimal places only since 2013 — and it stops when the lead reaches about 0.84 times the square root of the number of tosses, a constant that comes from Brownian motion.

probability · Optimal stopping
A curve that crosses a line twelve times. n=6: upper 9,8,7,6,5,4,3,2,1,0,11,10; lower 3,2,1,0,7,6,5,4,11,10,9,8; meanders 1828 of 17424.

Curves that cross a line and close

Draw a closed curve that crosses a straight line 2n times and never crosses itself. Above the line it is a set of nested arches, below it another, and every such curve is a pair of the Catalan number's arch systems that happen to close into one loop. There are 1, 2, 8, 42, 262, 1,828 of them, and every count computed so far grows by a factor creeping towards 12.26 — a number nobody can prove, with an exponent conjectured from the physics of random surfaces.

topology · Homotopy
Every way to make change for two pounds. Number of ways to make each amount up to 200 pence from British coins, on a logarithmic scale: 451 for 50p, 4563 for £1, 73682 for £2; a dollar in United States coins has 292.

Two pounds in 73,682 ways

Count the ways to pay an amount exactly with a fixed set of coins and the answer is almost a polynomial in the amount — a polynomial plus waves that repeat with the periods of the coins. With parts 1, 2 and 3 the whole formula fits on a line; with British coins the leading term is still 3% off at four hundred pounds. And the fewest coins is a different question, which the cashier's rule answers correctly only for some coinages.

number · Partitions
A family of 16, and the walk that counts it. seed 11: children 2,1,2,2,0,2,1,1,2,0,0,0,0,1,1,0; walk 0,1,1,2,3,2,3,3,3,4,3,2,1,0,0,0,-1

The walk that counts a family

Start with one ancestor, give everyone a random number of children, and ask how big the whole family gets. Visit the family member by member and keep a running total of children minus one: the total is a random walk, and the family is finished at the exact step the walk first drops below zero. A theorem about rotating sequences then gives the size's law in one line, and when each person has on average one child it is Cayley's count of labelled trees, multiplied by e⁻ⁿ/n!.

probability · Random walk

Named alongside it

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

PartitionAsymptoticsCounting two waysBijectionBinomial coefficientCatalan numbersExhaustive searchConvolutionLog-concavityPermutationReal rooted polynomialRecursion

All concepts