Partition Function p(n)

Why the partition function matters

The partition function is a perfect compact example of how a simple-looking counting problem opens onto modular forms, analytic number theory, asymptotic combinatorics, and statistical mechanics. Each layer reveals more structure than the previous; the sequence p(n) is the entry point.

• Combinatorics. Partitions are the fundamental ordered-versus-unordered counting object, side by side with compositions, multisets, and Young tableaux. The Robinson-Schensted-Knuth correspondence sets up bijections between matrices, pairs of Young tableaux, and permutation patterns — partition shapes parametrize the entire theory.
• Modular forms. The Dedekind eta function η(τ) = q^{1/24} ∏(1 − q^k) makes 1/η a near-modular generating function for partitions; the modular transformation laws of η give Hardy-Ramanujan-Rademacher exact formulas for p(n) and force Ramanujan's congruences mod 5, 7, 11.
• Statistical mechanics. The grand canonical partition function for non-interacting bosons confined to integer-energy levels is exactly Σ p(n) e^{−βn}; the partition function in physics borrowed both name and structure from the combinatorial original. Bose-Einstein condensation, gap statistics in random matrix theory, and Hagedorn temperature all use partition asymptotics.
• Asymptotic analysis. The Hardy-Ramanujan circle method — bound the integrand on a Farey-sequence dissection of the unit circle, identify the dominant arcs near rational points — was developed for p(n) and is now a workhorse for sums in additive number theory (Goldbach, Waring, Vinogradov).
• Number theory and arithmetic of congruences. Ramanujan's congruences led to deep developments — Atkin-Lehner theory, l-adic Galois representations, Ono's work on infinite families of partition congruences for primes p ≥ 13. The Bringmann-Ono theory of mock modular forms generalizes the framework.
• Algorithms. Coin-change and subset-sum problems are partition-style counts. Dynamic-programming algorithms for these problems mirror the recursion that builds up the partition table; the same DP solves "minimum coins for amount n" and many scheduling problems.
• Random partitions. Plancherel measure on Young diagrams (probability proportional to (dim λ)² / n!) gives a random partition; Vershik-Kerov shows the limit shape converges to a deterministic curve, with fluctuations governed by the Airy process. Connections to random matrix theory and the longest-increasing-subsequence problem.

Small values and growth

Reading partitions of small n gives a sense of how the count grows.

• p(0) = 1 (the empty partition).
• p(1) = 1: {1}.
• p(2) = 2: {2}, {1+1}.
• p(3) = 3: {3}, {2+1}, {1+1+1}.
• p(4) = 5: {4}, {3+1}, {2+2}, {2+1+1}, {1+1+1+1}.
• p(5) = 7.
• p(10) = 42.
• p(20) = 627.
• p(50) = 204,226.
• p(100) = 190,569,292.
• p(1000) ≈ 2.4 × 10^31.
• p(10000) ≈ 3.6 × 10^106.

The growth is sub-exponential: p(n) increases faster than any polynomial but much slower than 2^n. The Hardy-Ramanujan asymptotic e^(π √(2n/3)) / (4n√3) gives the leading-order rate.

The Euler generating function

Euler observed that listing the contribution of each part size k separately and then convolving gives:

Σ_{n ≥ 0} p(n) x^n = ∏_{k = 1}^{∞} 1/(1 − x^k).

The k-th factor 1 + x^k + x^{2k} + x^{3k} + ⋯ encodes "how many parts of size k". The product expansion picks one term from each factor, contributing total Σ (multiplicity of k) · k summed across k = 1, 2, …. Reading the coefficient of x^n collects all such contributions whose total is n — that is, all partitions of n.

Variations:

• Partitions into distinct parts: Σ p_d(n) x^n = ∏ (1 + x^k).
• Partitions into odd parts: Σ p_o(n) x^n = ∏ 1/(1 − x^{2k−1}).
• Euler's identity p_d(n) = p_o(n) — the number of partitions into distinct parts equals the number into odd parts. Bijection: write each part m of an odd-only partition as m · 2^j; collect distinct (m · 2^j).
• Restricted partitions p(n, k): parts ≤ k, generating function ∏_{j=1}^{k} 1/(1 − x^j).

Euler's pentagonal recursion

Euler's pentagonal number theorem ∏(1 − x^k) = Σ_{j ∈ ℤ} (−1)^j x^{j(3j − 1)/2} gives a clean recursion for p(n):

p(n) = p(n − 1) + p(n − 2) − p(n − 5) − p(n − 7) + p(n − 12) + p(n − 15) − ⋯

The offsets are the generalized pentagonal numbers ω(j) = j(3j − 1)/2 for j = ±1, ±2, ±3, …, namely 1, 2, 5, 7, 12, 15, 22, 26, …; signs alternate in pairs. This recursion computes p(n) in O(n √n) time — fast enough to tabulate billions of values.

The Hardy-Ramanujan circle method

To prove the asymptotic, write p(n) as a contour integral around the origin:

p(n) = (1 / 2πi) ∮ (1 / x^{n+1}) · ∏_{k} 1/(1 − x^k) dx.

The integrand has its biggest singularity at x = 1; near x = 1 the η-function modular transformation gives an asymptotic. Hardy and Ramanujan dissect the unit circle into Farey arcs near each rational point e^{2πi h/k}, evaluate the integrand on each arc using the η transformation under SL(2, ℤ), and sum. The dominant contribution from x = 1 gives the leading asymptotic; subleading contributions from x = e^{2πi/q} and beyond give the Hardy-Ramanujan-Rademacher exact convergent series. This was the birth of the modern circle method.

Ramanujan's congruences

Ramanujan computed the first few hundred values of p(n) by hand and noticed:

• p(5n + 4) ≡ 0 (mod 5). E.g. p(4) = 5; p(9) = 30; p(14) = 135; p(19) = 490.
• p(7n + 5) ≡ 0 (mod 7). E.g. p(5) = 7; p(12) = 77; p(19) = 490; p(26) = 2436.
• p(11n + 6) ≡ 0 (mod 11). E.g. p(6) = 11; p(17) = 297; p(28) = 3718.

He conjectured higher-power refinements: p(5^a · 7^b · 11^c · n + r) ≡ 0 (mod 5^a · 7^b · 11^c) for some r depending on a, b, c. Most of these were proved by Watson (1938) and Atkin (1967); some refinements failed for higher 7-powers and were corrected by Atkin-Garvan-Ono. Ono (2000) proved that for every prime p ≥ 5 there are infinitely many congruences p(an + b) ≡ 0 (mod p^k) for some a, b, k — a vast generalization beyond the original three.

Common misconceptions

• "p(n) is polynomial." It grows sub-exponentially as e^(π√(2n/3)) / (4n√3); polynomial bounds are vastly too small. p(100) is already 190 million; a polynomial of degree d would give n^d ≈ 100^d.
• "p ~ 2^n." Compositions of n number 2^(n−1) (each gap between adjacent 1's gets a comma or not). Partitions are much fewer because order does not matter — p(n) grows exponentially in √n, not n.
• "Easy to enumerate." Listing p(50) = 204,226 partitions takes meaningful time; p(1000) is 10^31 partitions, far beyond physical enumeration. The recursion computes p(n) without listing the partitions.
• "Partitions and compositions are the same." Compositions are ordered, partitions unordered. 2 + 1 and 1 + 2 are the same partition (both have parts {2, 1}) but different compositions.
• "Ramanujan congruences exist for every prime." Ramanujan's three were special — only primes p = 5, 7, 11 admit single-progression congruences for p(n). For p ≥ 13, congruences are still infinite (Ono) but more subtle and require refining moduli.
• "Hardy-Ramanujan asymptotic is approximate." Hardy-Ramanujan gives the leading term; Hardy-Ramanujan-Rademacher gives a convergent exact series — the n-th partial sum produces p(n) exactly when truncated correctly. So "asymptotic" undersells: it's an exact convergent expansion.