Generating function
Named by 26 essays across 5 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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!.
Named alongside it
The objects these essays reach for when they reach for this one.
PartitionAsymptoticsCounting two waysBijectionBinomial coefficientCatalan numbersExhaustive searchConvolutionLog-concavityPermutationReal rooted polynomialRecursion