Matpic
mathematics, in pictures
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 14 essays across 4 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

Named alongside it

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

PartitionCounting two waysBijectionBinomial coefficientConvolutionPermutationRecursionAsymptoticsCatalan numbersFerrers diagramFormal power seriesModular arithmetic

All concepts