The Theory of Partitions: How Many Ways Can You Add Up to n?

How many ways can you write the number $4$ as a sum of positive integers, where the order does not matter? Five:

$4, \quad 3 + 1, \quad 2 + 2, \quad 2 + 1 + 1, \quad 1 + 1 + 1 + 1.$

These five expressions are the partitions of $4$. The number of partitions of $n$ is denoted $p(n)$, so $p(4) = 5$. The first values of $p(n)$ for $n = 0, 1, 2, 3, 4, 5, 6, 7$ are $1, 1, 2, 3, 5, 7, 11, 15$. The sequence grows quickly, but at first it looks almost manageable.

By $n = 100$, $p(100) = 190{,}569{,}292$ — almost two hundred million ways to express $100$ as a sum of positive integers. By $n = 1000$, $p(1000)$ has $32$ digits. The function $p(n)$ grows faster than any polynomial but slower than any exponential, and tracking down its exact growth rate took some of the most spectacular mathematics of the early twentieth century.

This article is about the theory of partitions: what they are, how to count them, the wondrous asymptotic formula due to Hardy and Ramanujan, and the strange congruences Ramanujan discovered that even Hardy did not believe at first.

Visualising partitions: Young diagrams

A partition can be drawn as a Young diagram: a left-justified arrangement of boxes, with one row for each part of the partition, sorted in non-increasing order. The picture below shows the Young diagrams for the five partitions of $4$.

Young diagrams are more than visual aids. They are the foundation of an entire branch of combinatorics: transposing a Young diagram across its diagonal gives a new partition called the conjugate of the original. The partition $3 + 1$ has conjugate $2 + 1 + 1$ — flipping the diagram exchanges rows and columns. Conjugate partitions are an involution on the set of partitions of $n$, and the bijection generates a huge supply of partition identities.

Euler’s generating function

The systematic study of partitions begins with Euler’s generating function, one of the most beautiful identities in classical mathematics. The formal power series whose $n$-th coefficient is $p(n)$ has a remarkable factorisation:

$\sum_{n=0}^{\infty} p(n) \, x^n \;=\; \prod_{k=1}^{\infty} \frac{1}{1 - x^k}.$

To see why this is true, expand each factor: $1/(1 - x^k) = 1 + x^k + x^{2k} + x^{3k} + \cdots$. Multiplying out the infinite product, each term corresponds to choosing a non-negative number of each $k$ — that is, choosing how many times each positive integer appears in a partition. The exponent of $x$ in the resulting term is the sum of the contributions, which is exactly the total being partitioned. So the coefficient of $x^n$ is exactly $p(n)$, the number of ways to partition $n$.

This identity, due to Leonhard Euler in 1748, opened the door to most subsequent partition theory. From it follow many partition identities — for example, the identity that the number of partitions into distinct parts equals the number of partitions into odd parts (Euler 1748), proved by a one-line manipulation of generating functions.

How big is p(n)?

Euler gave the generating function but no asymptotic formula for $p(n)$. The first real progress was made by P. A. MacMahon in the early 20th century: he computed exact values up to $p(200) = 3{,}972{,}999{,}029{,}388$ using a complicated recursion, in pre-computer arithmetic by hand. But the growth rate of $p(n)$ remained mysterious.

The asymptotic formula was found by G. H. Hardy and Srinivasa Ramanujan in a landmark 1918 paper, building on a method of Hardy and Ramanujan now called the circle method. Their result:

$p(n) \;\sim\; \frac{1}{4n\sqrt{3}} \, \exp\!\left(\pi \sqrt{\tfrac{2n}{3}}\right) \quad \text{as } n \to \infty.$

The formula is approximately correct already for moderate $n$. For $n = 100$, it predicts $p(100) \approx 1.99 \times 10^8$; the true value is $1.91 \times 10^8$, an error of about $4\%$. For $n = 1000$, the asymptotic formula is accurate to about $0.4\%$. With a more refined version of the formula (the full Hardy–Ramanujan–Rademacher series), the exact integer value of $p(n)$ can be computed for any $n$.

The formula has several remarkable features. First, the exponential factor $\exp(\pi\sqrt{2n/3})$ grows sub-exponentially in $n$: not as fast as $\exp(cn)$, not as slow as any polynomial, but somewhere in between. This intermediate growth rate — exponential in $\sqrt{n}$ — is characteristic of combinatorial counting functions arising from generating functions like Euler’s. Second, the appearance of $\pi$ in the formula is unexpected: there are no circles in the definition of $p(n)$. The $\pi$ comes from contour integration in the circle method, just as it does in Stirling’s formula.

The Hardy–Ramanujan paper of 1918 inaugurated analytic combinatorics as a distinct mathematical discipline. The circle method has since been applied to many other problems — Waring’s problem on representing integers as sums of $k$-th powers, the Goldbach problem on writing integers as sums of primes, and many others — making it one of the most influential tools in 20th-century analytic number theory.

Ramanujan’s congruences

Beyond the asymptotic formula, Ramanujan noticed something remarkable in the table of partition values that he and MacMahon had computed:

• $p(4) = 5, p(9) = 30, p(14) = 135, p(19) = 490, \dots$ — all divisible by $5$.
• $p(5) = 7, p(12) = 77, p(19) = 490, p(26) = 2436, \dots$ — all divisible by $7$.
• $p(6) = 11, p(17) = 297, p(28) = 3718, p(39) = 37338, \dots$ — all divisible by $11$.

Ramanujan summarised the pattern in three short congruences:

$p(5k + 4) \equiv 0 \pmod{5}, \qquad p(7k + 5) \equiv 0 \pmod{7}, \qquad p(11k + 6) \equiv 0 \pmod{11}.$

He proved the first two; the third he conjectured. The proof of the third had to wait until 1934, when H. S. Vaughan completed Ramanujan’s program. The congruences seemed isolated — three quirky observations with no obvious common explanation. Ramanujan conjectured that there should be similar congruences for higher primes, but no systematic pattern was apparent.

The deep reason behind these congruences was found only in the late 20th century. In a series of papers culminating in 2000, Ken Ono showed that for every prime $p \geq 5$, there exist infinitely many congruences of the form $p(An + B) \equiv 0 \pmod{p^k}$, for appropriate constants $A, B, k$. The congruences are not isolated anomalies; they are members of an infinite family, and the structural reason for their existence lies in the theory of modular forms and the action of certain Hecke operators on partition generating functions.

This is one of the most spectacular vindications of Ramanujan’s intuition. He guessed that something deep was going on, but he did not have the modern machinery of modular forms to articulate why. A century later, his intuition was proven precisely correct.

Why partitions matter

The theory of partitions might appear, at first glance, to be a recreational corner of combinatorics. The depth comes from how partitions connect to other branches of mathematics.

Representation theory. The irreducible representations of the symmetric group $S_n$ are indexed by partitions of $n$. Young diagrams encode the dimensions and characters of these representations, and the entire representation theory of $S_n$ — and through it, much of the representation theory of general linear groups — can be developed using partition combinatorics.

Symmetric functions. Schur polynomials, Hall–Littlewood polynomials, and Macdonald polynomials are families of symmetric functions indexed by partitions. These functions are central to algebraic combinatorics and have applications across pure and applied mathematics, from the geometry of Grassmannians to integrable systems in mathematical physics.

Modular forms. Euler’s generating function for $p(n)$ is closely related to the Dedekind eta function $\eta(\tau)$, a fundamental example of a modular form. The connection between partition theory and modular forms, hinted at by Ramanujan’s congruences and made precise by Ono’s theorems, is part of an extended bridge between combinatorics and algebraic geometry that continues to be developed.

Statistical mechanics. In statistical mechanics, the partition function of certain models is literally a generating function for partitions — Euler’s product appears, for example, in the theory of free bosons. The “partition function” terminology of statistical mechanics in fact comes from partition theory.

Quantum field theory. Partition counts appear in the dimensions of cohomology rings, in instanton counts, and in many computations of supersymmetric quantum field theory. Donaldson–Thomas invariants and Gromov–Witten invariants are often expressible in terms of partition functions.

A combinatorial backbone

The theory of partitions is one of the deepest examples in mathematics of how a simple counting question can open onto vast structure. Counting the number of ways to write $n$ as a sum of positive integers sounds like an elementary exercise — a problem you might pose to a curious child. But the answer, $p(n)$, turns out to be governed by an asymptotic law involving $\pi$ and $\sqrt{n}$, by mysterious congruences modulo small primes, by generating functions that are modular forms in disguise, and by combinatorial structures (Young diagrams) that connect to the representation theory of every symmetric group.

The trajectory from Euler in 1748 to Hardy–Ramanujan in 1918 to Ono in 2000 traces an arc of progressively deeper understanding of a fundamentally combinatorial question. Each step revealed new structure: Euler gave the generating function, Hardy and Ramanujan extracted its asymptotic behaviour using analytic methods, Ono explained the congruences via modular-forms machinery developed across the entire twentieth century.

That a single sequence — $1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, \dots$ — should sit at the intersection of so many subjects is one of the small wonders of mathematics. Ramanujan, who first sensed the depth of partition theory in 1918, did not live to see most of what would unfold from his observations. But his short paper with Hardy remains one of the most influential in the history of analytic number theory, and the function $p(n)$ remains a touchstone — a sequence simple to define, beautiful to compute, and deep enough to support a century of subsequent mathematics.

Frequently asked

Who developed the modern theory of partitions?

Leonhard Euler began the systematic theory in the 1740s, introducing generating functions and proving the celebrated identity expressing the partition generating function as ∏ 1/(1−x^n). The asymptotic theory was largely developed by G. H. Hardy and Srinivasa Ramanujan in their 1918 paper, which derived the asymptotic formula for p(n) and introduced the powerful circle method. Ramanujan also discovered the famous congruences p(5k+4) ≡ 0 (mod 5), p(7k+5) ≡ 0 (mod 7), and p(11k+6) ≡ 0 (mod 11) — patterns of divisibility that remain among the most mysterious results in the subject.

What is a Young diagram?

A graphical representation of a partition, in which each part of the partition corresponds to a row of left-justified boxes of the appropriate length. The partition 4 = 3 + 1 corresponds to a row of three boxes on top of a row of one box. Young diagrams are not merely visual aids — they encode combinatorial structure that generalises to the representation theory of symmetric groups, the theory of symmetric functions, and many parts of combinatorics. The bijections between Young diagrams are the foundation of an entire mathematical subject called algebraic combinatorics.

What are Ramanujan's partition congruences?

Ramanujan noticed in 1919 that the partition counts seem to follow surprising divisibility patterns: p(5k+4) is always divisible by 5, p(7k+5) is always divisible by 7, and p(11k+6) is always divisible by 11. He proved the first two and conjectured the third; the third was proved by H. S. Vaughan in 1934. The congruences are the visible tip of a deep iceberg connecting partitions to modular forms. In 2000, Ken Ono showed that there are infinitely many such congruences for every prime ≥ 5, finally giving a structural explanation that Ramanujan and Hardy could not have anticipated.

How fast does p(n) grow?

Faster than any polynomial but slower than any exponential. The Hardy–Ramanujan asymptotic formula gives p(n) ~ (1 / (4n√3)) · exp(π · √(2n/3)) as n → ∞. So p(100) is about 190 million, p(1000) about 2.4 × 10^31, and p(10000) has about 110 digits. The growth is sub-exponential but super-polynomial — it sits in its own intermediate regime, characteristic of combinatorial functions arising from generating functions of this kind.

Continue reading

Person

Leonhard Euler

Swiss mathematician of extraordinary range and productivity. Formulated Euler's identity, founded graph theory, and produced more mathematical output than any mathematician before or since.

Read →Blog

RSA Encryption: How Two Primes Lock the World's Secrets

Pick two large primes. Multiply them. Publish the product. Every HTTPS connection and every encrypted message rests on the fact that nobody can factor that product back into the two primes.

Read →Blog

Perfect Numbers and Mersenne Primes: A Twenty-Three-Centuries-Old Hunt

A perfect number equals the sum of its proper divisors. Euclid in 300 BCE showed how to make them from a special prime. Twenty-three centuries later, 52 are known — and no more proven to exist.

Read →