A diagram turned on its side

A partition of a whole number is a way of writing it as a sum of positive whole numbers, order disregarded. Twelve can be written as $5+4+2+1$, or $6+6$, or twelve ones, and there are seventy-seven ways altogether.

Counting them is a question with no formula and a great deal of structure, and almost all of the structure comes from one operation.

Reading the columns instead of the rows gives another partition of the same number, called the conjugate. Doing it twice gives back the original, because the second reading of a transposed diagram is the first reading of the original.

That is the whole apparatus. What follows is what can be proved with it.

The first theorem, for free #

Partitions of $n$ into at most $k$ parts correspond exactly to partitions of $n$ with no part larger than $k$.

The proof is conjugation. A diagram with at most $k$ rows has no column longer than $k$; conjugating swaps the two conditions; and since conjugation is its own inverse, the correspondence is a bijection.

Nothing was computed. Two counting problems that look different — one bounding how many summands, one bounding how large they are — turned out to be the same problem seen from two sides, and the argument is a quarter turn.

The statement is worth checking against the smallest case, since small cases in this field mislead more often than they illuminate and this one does not. Partitions of four into at most two parts: $4$, $3+1$, $2+2$ — three of them. Partitions of four with no part above two: $2+2$, $2+1+1$, $1+1+1+1$ — three of them. The correspondence pairs $4$ with $1+1+1+1$, $3+1$ with $2+1+1$, and $2+2$ with itself, and each pair is one diagram read two ways.

This is the first move in a style that runs through combinatorics: prove two things are equinumerous by exhibiting a bijection rather than by counting either. A bijection is stronger than an equal count, because it says how they correspond, and it survives generalisation in ways a count does not.

Odd parts and distinct parts #

Here is the identity that made the subject.

Six and six, and the same equality holds for every number anybody has checked. The two conditions have nothing obvious in common: one restricts the parts to be odd, the other restricts them to be different from each other.

Euler proved it with generating functions in 1748. The partitions into distinct parts are counted by $\prod_k (1 + x^k)$, one factor per part with a choice of taking it or not; the partitions into odd parts by $\prod_{k \text{ odd}} (1 - x^k)^{-1}$, each factor a geometric series allowing a part to repeat. Then

$$\prod_k (1 + x^k) = \prod_k \frac{1 - x^{2k}}{1 - x^k} = \prod_{k \text{ odd}} \frac{1}{1 - x^k},$$

because the numerator cancels every even-indexed factor of the denominator. The identity is telescoping, and it is not a picture.

Glaisher’s bijection, from 1883, is the picture. Given a partition into odd parts, take each part appearing $m$ times, write $m$ in binary, and split the repeats into groups of sizes the powers of two — a part $3$ appearing $5$ times becomes $3 \times 4 = 12$ and $3 \times 1 = 3$. The results are distinct because every whole number factors uniquely as a power of two times an odd number, which is unique factorisation used exactly once. Running it backwards recovers the odd partition.

So the identity has a formal proof and a structural one, and the structural one explains where the two comes from: it is the base of the binary expansion, and the odd numbers are the numbers with no factor of two to give.

The Durfee square #

The most useful thing to do with a Ferrers diagram is to find the largest square that fits in its corner.

A partition with a Durfee square of side $d$ splits into three pieces: the square, the part of the rows to the right of it, and the part of the diagram below it. The arm is a partition into at most $d$ parts; the leg is a partition with no part exceeding $d$; and the two are independent.

That decomposition gives the identity

$$\sum_{n} p(n) x^n = \sum_{d \ge 0} \frac{x^{d^2}}{(1-x)^2(1-x^2)^2\cdots(1-x^d)^2},$$

which is a sum over the possible Durfee squares. It is one of the standard ways to get at $p(n)$ computationally, and it comes from asking a picture where its biggest square is.

The square also bounds things. A partition of $n$ has Durfee square of side at most $\sqrt{n}$, so a partition with many parts must have small parts and one with large parts must have few — an obvious statement that becomes quantitative the moment the square is drawn.

It is worth noticing what kind of object the Durfee square is. It is not a choice: every diagram has exactly one largest corner square, so the decomposition is canonical and applies to every partition without exception. That is the property a decomposition needs if it is going to be summed over, and it is why the identity above is a clean sum with one term per side length rather than an inclusion–exclusion with corrections. A canonical decomposition is worth much more than a clever one, and finding the canonical one is usually the work.

Self-conjugate partitions, and a third equality #

A partition can be its own conjugate. $4+3+2+1$ is not, but $5+1+1+1+1$ is, and so is $3+2+1$ — the diagram is symmetric about its diagonal.

Counting the self-conjugate ones gives another identity of the same kind. Fold a symmetric diagram along its diagonal: each hook — a row and its matching column, sharing the corner dot — becomes one row of odd length, and different hooks have different lengths because they nest. So the self-conjugate partitions of $n$ correspond exactly to the partitions of $n$ into distinct odd parts.

For $n = 8$: the self-conjugate partitions are $4+2+1+1$ and $3+3+2$, and the partitions into distinct odd parts are $7+1$ and $5+3$. Two of each.

The proof is again a physical operation on a diagram, and it composes with the earlier one: distinct odd parts is a stronger condition than either “odd” or “distinct”, and the three-way relationship between the counts is a small lattice of bijections. That is the pleasant thing about this method — the proofs are objects rather than arguments, so they can be combined.

What the count does #

The number of partitions, $p(n)$, grows fast and irregularly: $p(10) = 42$, $p(50) = 204226$, $p(100) = 190569292$.

There is no simple formula. What there is, is one of the most remarkable results in analysis: Hardy and Ramanujan’s 1918 asymptotic,

$$p(n) \sim \frac{1}{4n\sqrt3} \exp\left(\pi\sqrt{\frac{2n}{3}}\right),$$

which is accurate to within about two percent at $n = 100$ and better afterwards. Rademacher later turned it into an exact convergent series — a formula that computes $p(n)$ precisely, as a sum of infinitely many terms involving $\pi$, square roots and roots of unity.

That a count of ways to add up whole numbers requires $\pi$ and $\sqrt3$ to describe is the sort of thing that makes this subject worth doing. Nothing about the definition of a partition mentions circles. The constants arrive from the generating function’s behaviour near the unit circle, which is where the circle method — invented for this problem — does its work.

What the picture cannot show #

The diagrams here have a dozen dots and the interesting cases have millions.

More importantly, conjugation proves identities of one particular shape — a condition on rows swapped for a condition on columns — and most partition identities are not of that shape. The Rogers–Ramanujan identities, which say that partitions with parts differing by at least two are equinumerous with partitions into parts congruent to $1$ or $4$ modulo $5$, are true, deep, and have no known bijective proof that anybody would call natural. Garsia and Milne found one in 1981; it runs to many pages and is generally agreed to explain nothing.

So the method has a boundary and the boundary is not where it looks. Turning a diagram on its side handles the conditions that are geometrically dual and fails completely on conditions that are arithmetic — parts congruent to something modulo five is not a statement about rows or columns, and no rearrangement of dots produces it.

There is a third limitation worth naming. The figures show partitions of eight and twelve, and small cases in this subject are notoriously misleading: Ramanujan’s congruences — $p(5n+4)$ divisible by five, $p(7n+5)$ by seven, $p(11n+6)$ by eleven — are invisible below $n = 4$ and were found by staring at a table Macmahon had computed to two hundred terms. A pattern in this field needs a great deal of data before it is even a conjecture.

Where the numbers came from #

Partitions arrived in mathematics as a question in a letter. Philipp Naudé wrote to Euler in 1740 asking how many ways fifty could be written as a sum of seven distinct positive whole numbers; Euler answered — $522$ — and then spent years on the general theory, inventing generating functions to do it.

The subject’s second great episode is Ramanujan’s. Working from Macmahon’s hand-computed table of $p(n)$ up to $n = 200$, he noticed that $p(4), p(9), p(14), \ldots$ are all divisible by five, that $p(5), p(12), p(19), \ldots$ are divisible by seven, and that a similar pattern holds modulo eleven. Nothing about the definition suggests that a count of ways to add up numbers should be divisible by five whenever the number is four more than a multiple of five.

The congruences are true, and they were proved by Ramanujan and later given much better proofs. The natural next question — what happens modulo thirteen — has the answer nothing, and it took until 2000 for Ono to show that congruences do exist for every prime above three, at moduli much larger than the small cases suggest. Five, seven and eleven are special, and thirteen is not, and there is no elementary reason for the difference.

That is one more instance of the standing hazard in this collection: a table of two hundred values was enough to see three real patterns and to make the fourth look overdue, and it was not.

Where the same move shows up #

Counting one collection two ways is the engine of this whole field, and the Ferrers diagram is its most literal instance: the collection is a set of dots, and the two ways are along and down.

Every square is a stack of odd numbers is the same picture with the partition chosen so that the answer is a square. The divisor lattice is a box counted by rows to get the divisor sum. Fermat’s little theorem counts strings directly and then by rotation class. Quadratic reciprocity counts a rectangle above and below a diagonal. Four theorems in four corners of the subject, one method.

What partitions add is that the objects being counted are themselves the diagrams, so the correspondence is not merely a count but a transformation of the objects. That is why partition identities so often have bijective proofs when other identities do not, and why the ones that resist — Rogers–Ramanujan — are the famous ones.

The additive and multiplicative sides #

Partitions are the additive analogue of factorisation, and the comparison is instructive because it fails.

Factoring a number is rigid: there is one factorisation, as the fundamental theorem insists, and the divisor count is a tidy product over exponents. Partitioning a number is the opposite: there are many ways, the count has no closed form, and the answer depends on $n$ in a way that requires analysis to describe.

The reason is that multiplication has unique factorisation and addition does not. There is no “additive prime” — every number above one is a sum of smaller ones in many ways — so nothing plays the structural role the primes play, and the additive theory is a theory of counting rather than of structure.

That asymmetry is the reason additive number theory and multiplicative number theory are different subjects with different tools. Questions mixing the two, like Goldbach’s conjecture — every even number a sum of two primes — sit exactly on the fault line, and are hard for exactly that reason: they ask an additive question about a multiplicatively defined set.

The one place the two sides meet cleanly is Euler’s pentagonal number theorem, which says that the generating function for partitions has an inverse with almost all coefficients zero:

$$\prod_{k\ge1}(1 - x^k) = \sum_{j=-\infty}^{\infty} (-1)^j x^{j(3j-1)/2},$$

the exponents being the pentagonal numbers $1, 2, 5, 7, 12, 15, \ldots$. Expanded, it gives a recurrence computing $p(n)$ from earlier values using only about $\sqrt n$ terms, which is how partition numbers were computed before Rademacher’s formula and is still the practical method.

Franklin found a bijective proof in 1881, and it is the best advertisement the diagram method has. He defines an operation on Ferrers diagrams that pairs up partitions into distinct parts of opposite parity — moving dots between the smallest part and the top-right diagonal — and shows it fails to pair exactly the partitions counted by the pentagonal numbers. An identity whose right-hand side is almost entirely zeros is proved by an involution that almost always cancels, and the leftovers are the terms that survive.

Where the ladder goes next #

The immediate continuation is the generating function, which this essay used twice and did not explain. Reading a sequence off the coefficients of a power series turns counting problems into algebra, and it is how Catalan numbers and partitions are both handled once the pictures run out.

The other direction stays with the diagrams. A Ferrers diagram with its cells filled by numbers is a Young tableau, and counting those is the beginning of the representation theory of the symmetric group — where the partitions of $n$ index the irreducible representations, and the same conjugation that proved the first theorem here corresponds to tensoring with the sign representation. A quarter turn of a dot diagram is doing work at both ends of the subject.