The shape a random partition takes

The number of partitions of $n$ has no formula but has a size: it grows like $e^{\pi\sqrt{2n/3}}$ divided by $4n\sqrt3$, accurately enough that rounding a few terms of the refinement gives the exact count. For $n = 1000$ the count is $24{,}061{,}467{,}864{,}032{,}622{,}473{,}692{,}149{,}727{,}991$, about $2.4 \times 10^{31}$. That essay asked how many there are. This one asks what a typical one looks like.

The answer is one of the most surprising facts about partitions, and one of the easiest to see. Pick a partition of $1000$ uniformly at random from all of them, draw its Ferrers diagram — a row of dots for each part, longest first — and shrink it by $\sqrt{1000}$ in both directions. The staircase it makes is almost exactly the curve

$$e^{-cx} + e^{-cy} = 1, \qquad c = \frac{\pi}{\sqrt 6} = 1.2825\ldots$$

Pick another and the same thing happens. Among the $2.4 \times 10^{31}$ partitions, all but a vanishing fraction have this shape. Anatoly Vershik proved it in 1996, and Harold Temperley had found the curve in 1952, from a model of crystal surfaces rather than from number theory.

Many random partitions, one curve #

The outlines differ in detail — one has an unusually long first part, another a few extra ones at the end — and agree in shape. Each is a staircase that starts high and steep near the vertical axis, where the largest parts are, bends through a corner near $(0.54, 0.54)$, and runs out long and flat along the horizontal axis, where the many small parts are. The curve through them is the same for all four.

Choosing a partition uniformly at random is not as easy as choosing a number at random, and it is worth saying how the figure does it, because the method explains the curve. Treat each possible part size $k$ independently, and choose how many times it appears — its multiplicity — from a geometric distribution with parameter $q^k$, where $q = e^{-c/\sqrt n}$. The total $\sum k \cdot m_k$ is then a random number close to $n$, and every partition of that total is equally likely, because the probability of a given set of multiplicities is proportional to $q$ raised to the total. Keep only the samples whose total is exactly $n$ — about one in three hundred and fifty, for $n = 1000$ — and the result is uniform on the partitions of $n$. This is Boltzmann sampling, named for the physics it comes from, and the independence of the multiplicities is the key to the shape.

The rejection rate is itself a small measurement. The random total spreads about $n$ with a standard deviation that grows like $n^{3/4}$ — the multiplicities are independent, and their variances add up to about $n^{3/2}$ times a constant — so the chance that it lands exactly on $n$ is of order $n^{-3/4}$. For $n = 1000$, $n^{-3/4}$ is about one in a hundred and eighty, and the sampler’s observed one in three hundred and fifty is that rate times a constant close to a half. Choosing $q$ is choosing a temperature: $q$ closer to one makes larger totals likelier, and $e^{-c/\sqrt n}$ is exactly the temperature at which the average total is $n$.

Why the curve is symmetric #

The curve $e^{-cx} + e^{-cy} = 1$ is unchanged when $x$ and $y$ are swapped, and it has to be, for a reason that has nothing to do with probability.

Turning a Ferrers diagram on its side — reading its columns instead of its rows — turns a partition into another partition of the same number, and turns the largest part into the number of parts. It is a one-to-one correspondence on the partitions of $n$, so a uniformly random partition, turned over, is still a uniformly random partition. Every statement about the typical shape must therefore hold equally for the shape reflected in the diagonal. The figure counts the partitions of thirty both ways, by largest part and by number of parts, and the two tallies agree exactly at every size.

The symmetry pins down where the curve crosses the diagonal. On the diagonal $x = y$, so $2e^{-cx} = 1$, and $x = \ln 2 / c = \sqrt6 \ln 2 / \pi = 0.5404$. That crossing is the corner of the Durfee square — the largest square of dots that fits in the diagram’s corner — so the typical Durfee square has side about $0.54\sqrt n$.

Where the curve comes from #

The independence in the sampling method makes the curve computable in a few lines. Under the Boltzmann distribution, the number of parts equal to $k$ has mean $q^k/(1 - q^k)$. The number of parts that are at least $k$ — which is the height of the Ferrers diagram at column $k$ — is the sum of those means from $k$ upward. With $q = e^{-c/\sqrt n}$ and $k = x\sqrt n$, each term is $e^{-cx}/(1 - e^{-cx})$ and the sum becomes an integral:

$$\frac{1}{\sqrt n}\sum_{j \ge k}\frac{q^j}{1 - q^j} \approx \int_x^\infty \frac{e^{-ct}}{1 - e^{-ct}}\,dt = -\frac{1}{c}\ln\!\left(1 - e^{-cx}\right).$$

So the scaled height at $x$ is $y = -\ln(1 - e^{-cx})/c$, which rearranges to $e^{-cx} + e^{-cy} = 1$. The constant $c$ is fixed by requiring the total to be $n$, which means the area under the curve must be one: $\int_0^\infty -\ln(1 - e^{-cx})/c\,dx = \pi^2/(6c^2)$, and setting that to one gives $c = \pi/\sqrt 6$. The $\pi^2/6$ is Euler’s sum of the reciprocal squares, $1 + \tfrac14 + \tfrac19 + \cdots$, turning up because the area is a sum of $\tfrac1{m^2}$ terms in disguise.

That same $\pi/\sqrt6$ is what put $\pi\sqrt{2n/3} = 2c\sqrt n$ in the exponent of Hardy and Ramanujan’s formula for the count. The count and the shape come from one computation: the number of partitions is dominated by the shapes near this curve, and the curve is where the dominant term’s exponent is largest. The two constants are one constant.

The staircase smoothing #

For small $n$ the diagram is visibly a staircase, and the resemblance to the curve is rough. As $n$ grows the steps shrink.

At fifty the diagrams are coarse and scatter visibly about the curve; at five thousand they hug it. Each step of the staircase is one dot, which is $1/\sqrt n$ after scaling, so the steps vanish at that rate. The random wobble of the outline about the curve vanishes more slowly: Boris Pittel showed in 1997 that it is of order $n^{-1/4}$ after scaling, and approximately Gaussian at each point. So the limit shape is a law of large numbers, and its fluctuations obey a central limit theorem, exactly as the average of many coin tosses does — except that here the “average” is a whole curve.

How many ones, and how many of each #

The same independence answers a question that sounds harder than it is: how many parts equal to $1$ does a random partition have? Under Boltzmann sampling the multiplicity of $1$ is geometric with mean $q/(1 - q)$, which for $q = e^{-c/\sqrt n}$ is very nearly $\sqrt n / c$. For $n = 1000$ that predicts $24.66$. The exact average, over all $2.4 \times 10^{31}$ partitions — computable because the number of partitions of $1000$ with at least $k$ ones is just $p(1000 - k)$ — is $24.47$.

More generally the number of parts equal to $k$ is roughly geometric with mean $1/(e^{ck/\sqrt n} - 1)$: about $\sqrt n/(ck)$ for small $k$, falling off exponentially once $k$ is a sizeable multiple of $\sqrt n$. So a typical partition of $1000$ has about twenty-five ones, twelve twos, eight threes, and then fewer and fewer of each larger size, with the last few parts appearing once or not at all. That profile, integrated up, is the curve. It is the pattern of a gas at a low temperature, where each energy level holds a number of particles that falls off with its energy — the same $1/(e^x - 1)$ that Planck wrote down in 1900 for the light inside a heated box, where the energy levels are the frequencies and the parts are photons.

The largest part #

The curve says nothing about the very largest parts, because they sit near the vertical axis where the curve shoots up to infinity. The largest part of a random partition is a separate question, and it has a separate and older answer.

Paul Erdős and Joseph Lehner showed in 1941 that the largest part is about $\frac{\sqrt n}{c}\ln\frac{\sqrt n}{c}$, with fluctuations of order $\sqrt n/c$ that follow the Gumbel distribution — the law of the maximum of many independent quantities, which is what the largest part is, under Boltzmann sampling: the largest $k$ with a nonzero multiplicity. For $n = 3000$ the centre is $160.3$ and the scale $42.7$, and the exact distribution, counted from the numbers of partitions with all parts at most $k$, follows the Gumbel curve to within $0.034$. The fit improves as $n$ grows — the figure checks that the gap shrinks from $n = 300$ to $1000$ to $3000$ — but slowly, and at any size a small shift remains.

The largest part grows like $\sqrt n \ln n$, faster than the $\sqrt n$ scaling of the shape, which is exactly why the curve’s vertical axis is an asymptote. And by the symmetry of the previous section, the number of parts has precisely the same distribution: half of all partitions of $3000$ have a largest part of at most $178$, and half have at most $178$ parts.

The Durfee square, exactly #

The corner of the shape can be checked without sampling at all, because the Durfee square has an exact count.

A partition with Durfee square of side $d$ is the $d \times d$ square, plus a partition into parts of size at most $d$ hanging below it, plus the mirror image — a partition with at most $d$ parts — to its right. So the number of partitions of $n$ with Durfee side $d$ is a convolution of two counts of restricted partitions, and summing $d$ times that count over $d$ gives the average side exactly. The figure checks that the counts over all $d$ add up to $p(n)$, which confirms that every partition is counted exactly once, and then plots the average side divided by $\sqrt n$. It falls steadily towards $\sqrt6 \ln 2/\pi = 0.5404$, the crossing point of the curve — the shape’s corner predicted by the symmetry argument, reached by pure counting. This is the same square that the essay on the diagram turned on its side used to prove identities; here it measures where every large partition bends.

Counting by the corner square #

The Durfee decomposition used above is also an identity, and it is worth writing down because it points straight at the next essay. A partition is its Durfee square, of side $d$, together with a partition into parts at most $d$ below it and a partition into at most $d$ parts beside it. Partitions into parts at most $d$ are counted by $1/((1-q)(1-q^2)\cdots(1-q^d))$, and by conjugation so are partitions into at most $d$ parts. So, counting by the corner square,

$$\prod_{k\ge1}\frac{1}{1-q^k} \;=\; \sum_{d\ge0}\frac{q^{d^2}}{\big((1-q)(1-q^2)\cdots(1-q^d)\big)^2}.$$

The left side is the product that holds every partition; the right side sorts them by where the diagram bends. The $q^{d^2}$ is the square itself. Replace the square by a staircase of $d$ rows — $1 + 3 + 5 + \cdots$, which also adds up to $d^2$ — and remove one of the two flanking partitions, and the same bookkeeping produces the sum side of the Rogers–Ramanujan identities, $\sum q^{d^2}/((1-q)\cdots(1-q^d))$. The corner of the typical shape and the most famous identity in the subject are built from the same square number of dots.

Partitions into different parts have a different shape #

Restrict to partitions whose parts are all different and the shape changes, which is a useful check that the curve is not an artefact of scaling. Under Boltzmann sampling each part size now appears zero times or once, with probability $q^k/(1+q^k)$ of appearing, and the same integral gives the curve $e^{c'y} = 1 + e^{-c'x}$ with $c' = \pi/\sqrt{12}$, the constant now coming from Euler’s alternating sum $1 - \tfrac14 + \tfrac19 - \cdots = \pi^2/12$. The new curve meets one axis at a finite height instead of running off to infinity: since no part can repeat, the number of parts cannot pile up, and a random partition into distinct parts has about $\sqrt{12}\,\ln 2/\pi \cdot \sqrt n \approx 0.76\sqrt n$ parts, where an unrestricted one has about $\sqrt n \ln n$ times a constant, which is larger for every large $n$. These partitions are also far rarer: of the $2.4 \times 10^{31}$ partitions of $1000$, only $8.6 \times 10^{21}$ have all their parts different, a fraction of about $3.6 \times 10^{-10}$. So the distinct-part partitions are a thin, differently shaped slice of the whole, and a uniformly random partition essentially never lands in it. Euler’s theorem that partitions into distinct parts are as numerous as partitions into odd parts means the odd-part partitions share that count — and, pleasingly, not that shape.

The same curve elsewhere #

Temperley found the curve in 1952 in a model of how a crystal grows: a corner of a crystal, built of cubes stacked into a staircase, whose surface at equilibrium takes exactly this shape. A Ferrers diagram is such a staircase — the dots are cubes seen end-on — and the uniform distribution on partitions is the equilibrium of a crystal with no preference for any arrangement. The same mathematics describes Bose–Einstein statistics: the multiplicities of part sizes are the occupation numbers of energy levels, geometric because any number of indistinguishable bosons may share a level, and the limit shape is the energy distribution of a cold gas.

In three dimensions the analogue is the plane partition — cubes stacked in the corner of a room — and a random large one has a limit shape too, computed by Andrei Okounkov and Nicolai Reshetikhin in 2003: a curved surface with a frozen flat region near each wall and a disordered region in the middle, separated by a curve. And for random partitions under a different distribution, the Plancherel measure that arises from counting Young tableaux, the limit shape is a completely different curve, found by Vershik and Kerov and independently by Logan and Shepp in 1977. Its fluctuations at the edge are those of the largest eigenvalue of a random matrix, which is how the longest increasing subsequence of a random permutation acquired its famous $n^{1/6}$ wobble.

What the samples cannot show #

They cannot show uniformity at the scale of all partitions. The figures draw a few samples; that almost all of the $2.4 \times 10^{31}$ partitions of $1000$ lie near the curve is Vershik’s theorem, and a handful of samples is evidence, not a proof. The exact counts — the largest-part distribution, the Durfee averages, the conjugation symmetry — are complete for the sizes they cover.

They cannot show the limit. At every finite $n$ the Gumbel fit is off by a few hundredths and the Durfee ratio is above its limit by a few thousandths. The limits are theorems; the figures show the approach, and the slowness of the approach is itself part of what they show.

And they cannot show the fluctuations’ shape. Pittel’s Gaussian fluctuations of order $n^{-1/4}$ are quoted; eight samples at three sizes show the distance shrinking, not its distribution.

Where the shape leads next #

The shape describes a partition’s size profile and says nothing about its arithmetic — which partitions have parts differing by at least two, or all parts leaving one on division by five. Those restricted families have their own counts, and some of them agree with each other for reasons no shape can explain. The most famous such agreement, the pair of identities Rogers and Ramanujan found, has been named in these essays since the product that hides every partition and never developed. It is the next essay.

A shape out of noise #

A uniformly random partition of a large number $n$, shrunk by $\sqrt n$, is almost certainly close to the curve $e^{-cx} + e^{-cy} = 1$ with $c = \pi/\sqrt6$. The curve comes from treating each part size’s multiplicity as an independent geometric random variable, and its constant from making the area one — which brings in Euler’s $\pi^2/6$ and is the same constant as in Hardy and Ramanujan’s count.

Turning diagrams over makes the curve symmetric, so it crosses the diagonal at $\sqrt6\ln2/\pi = 0.540$, the typical Durfee square’s side over $\sqrt n$, confirmed by exact counting. The largest part escapes the curve, growing like $\sqrt n \ln n$ with Gumbel fluctuations, and the whole staircase smooths as $n$ grows, its wobble shrinking like $n^{-1/4}$.

Uniform randomness over an enormous set is often not formless at all — count the set cleverly, and the typical member has a shape.