Integer partitions, recurrences and asymptotics

A partition of a positive integer \(n\) is a way of writing \(n\) as a sum of positive integers where order does not matter. The number 5 has seven partitions: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1 and 1+1+1+1+1. Unlike compositions, which have the simple count \(2^{n-1}\), partitions have no closed formula, and their study has drawn in Euler, Jacobi, Sylvester, Hardy, Ramanujan and many others. This lesson develops the generating function approach, proves several classic identities, and then asks how fast counting sequences grow, which leads to asymptotic estimates.

Ferrers diagrams and conjugation

Write a partition as \(\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)\) with \(\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_k \ge 1\). Its Ferrers diagram has a row of \(\lambda_i\) boxes for each part, left-justified. Reading the diagram by columns instead of rows gives another partition \(\lambda'\), the conjugate, whose parts are \(\lambda'_j = |\{i : \lambda_i \ge j\}|\).

Conjugation is a bijection, since conjugating twice returns the original. It exchanges the number of parts with the size of the largest part. This proves at once: the number of partitions of \(n\) into at most \(k\) parts equals the number of partitions of \(n\) with largest part at most \(k\). A partition equal to its own conjugate is called self-conjugate; reading its diagram by hooks along the diagonal shows that self-conjugate partitions of \(n\) correspond to partitions of \(n\) into distinct odd parts. For instance \((3, 2, 1)\) is self-conjugate and corresponds to \(5 + 1\).

The partition generating function

A partition is determined by how many 1s, how many 2s, how many 3s, and so on, it contains. Choosing \(m_k\) parts equal to \(k\) contributes \(x^{km_k}\), and the choices are independent. Hence, as Euler showed in 1748, \[\sum_{n \ge 0}p(n)x^n = \prod_{k \ge 1}\frac{1}{1 - x^k} = (1 + x + x^2 + \cdots)(1 + x^2 + x^4 + \cdots)(1 + x^3 + \cdots)\cdots\] The infinite product makes sense formally because only the first \(n\) factors affect the coefficient of \(x^n\). Restricting the factors restricts the parts: \(\prod_{k=1}^{m}\frac{1}{1 - x^k}\) counts partitions with parts at most \(m\), \(\prod_{k}(1 + x^k)\) counts partitions into distinct parts, and \(\prod_{k \text{ odd}}\frac{1}{1 - x^k}\) counts partitions into odd parts.

Theorem (Euler). The number of partitions of \(n\) into distinct parts equals the number of partitions of \(n\) into odd parts.

Proof. Using \(1 + x^k = \frac{1 - x^{2k}}{1 - x^k}\), \[\prod_{k \ge 1}(1 + x^k) = \prod_{k \ge 1}\frac{1 - x^{2k}}{1 - x^k} = \frac{(1 - x^2)(1 - x^4)(1 - x^6)\cdots}{(1 - x)(1 - x^2)(1 - x^3)\cdots} = \prod_{k \text{ odd}}\frac{1}{1 - x^k},\] since every even factor in the denominator cancels against the numerator. For \(n = 6\): distinct parts 6, 5+1, 4+2, 3+2+1; odd parts 5+1, 3+3, 3+1+1+1, 1+1+1+1+1+1. Four each.

James Glaisher gave a bijection in 1883. Starting from a partition into odd parts, combine equal parts in pairs repeatedly: three 3s become 6 + 3, since \(3 + 3 = 6\); in general, write the multiplicity \(m\) of each odd part \(q\) in binary, \(m = 2^{a_1} + 2^{a_2} + \cdots\), and replace the copies of \(q\) by the distinct parts \(2^{a_1}q, 2^{a_2}q, \ldots\) Every positive integer is uniquely \(2^a q\) with \(q\) odd, and binary expansions are unique, so this is a bijection onto partitions into distinct parts.

Euler's pentagonal number theorem

Inverting the partition generating function means expanding \(\prod_{k \ge 1}(1 - x^k)\). Euler computed the first terms and found astonishing cancellation: \[\prod_{k \ge 1}(1 - x^k) = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - \cdots = \sum_{j=-\infty}^{\infty}(-1)^jx^{j(3j-1)/2}.\] The exponents \(j(3j - 1)/2\) for \(j = 1, 2, 3, \ldots\) are the pentagonal numbers 1, 5, 12, 22, and for \(j = -1, -2, \ldots\) they are 2, 7, 15, 26. Euler announced the theorem around 1740 and proved it in 1750.

Combinatorial meaning. The coefficient of \(x^n\) in \(\prod(1 - x^k)\) is \(E_n - O_n\), where \(E_n\) and \(O_n\) count partitions of \(n\) into an even and an odd number of distinct parts. Fabian Franklin gave a beautiful bijective proof in 1881. In a partition into distinct parts, let the slope be the longest run of parts \(\lambda_1, \lambda_1 - 1, \lambda_1 - 2, \ldots\) decreasing by one from the largest, and let the base be the smallest part. If the base is no longer than the slope, move the base boxes onto the ends of the first rows of the slope; otherwise remove the slope, one box from each of its rows, and make it a new smallest part. Each move changes the number of parts by one, so it pairs even with odd partitions. The moves fail only when the slope and the base overlap and have lengths \(j\) and \(j\) or \(j\) and \(j + 1\), which happens exactly when \(n = j(3j \mp 1)/2\), and then there is a single unpaired partition with \(j\) parts, giving the sign \((-1)^j\).

A recurrence for p(n). Multiplying \(\sum p(n)x^n\) by \(\prod(1 - x^k)\) gives 1. Comparing coefficients of \(x^n\) for \(n \ge 1\): \[p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15) - \cdots,\] with \(p(m) = 0\) for \(m < 0\) and \(p(0) = 1\). Only about \(2\sqrt{2n/3}\) terms are nonzero, so this computes \(p(n)\) quickly. Percy MacMahon used it in 1918 to compute \(p(n)\) up to \(n = 200\), finding \(p(200) = 3{,}972{,}999{,}029{,}388\), the table against which Hardy and Ramanujan tested their formula.

Ramanujan and the growth of p(n)

The partition numbers grow faster than any polynomial but slower than any exponential \(c^n\) with \(c > 1\). In 1918 G. H. Hardy and Srinivasa Ramanujan proved \[p(n) \sim \frac{1}{4n\sqrt3}\exp\Big(\pi\sqrt{\frac{2n}{3}}\Big),\] meaning the ratio tends to 1. Their method, the circle method, studies the generating function near every root of unity on the unit circle, and became one of the main tools of analytic number theory. Hans Rademacher refined it in 1937 into an exact convergent series for \(p(n)\). The approximation is already within about 4 parts in 100 at \(n = 100\), where \(p(100) = 190{,}569{,}292\).

Ramanujan also noticed divisibility patterns in MacMahon's table: \[p(5n + 4) \equiv 0 \pmod 5, \quad p(7n + 5) \equiv 0 \pmod 7, \quad p(11n + 6) \equiv 0 \pmod{11}.\] He proved the first two. Freeman Dyson in 1944 conjectured a combinatorial explanation, the rank of a partition (largest part minus number of parts), which splits the partitions of \(5n + 4\) into five equal classes; this was proved by Atkin and Swinnerton-Dyer in 1954. In 2011 Ken Ono and Jan Bruinier found an algebraic formula for \(p(n)\) as a finite sum of algebraic numbers.

Asymptotics of counting sequences

Exact formulas are often less informative than good estimates. Stirling's formula \(n! \sim \sqrt{2\pi n}\,(n/e)^n\), found by de Moivre and Stirling around 1730, is the basic tool. From it, \[\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}, \qquad C_n \sim \frac{4^n}{n^{3/2}\sqrt\pi}.\] So there are about \(4^n\) Dyck paths, and the correction factor \(n^{-3/2}\) records the constraint of staying above the axis.

The principle behind such estimates is that the growth of the coefficients of a generating function is controlled by its singularity nearest the origin. If \(A(x)\) is analytic for \(|x| < \rho\) and has a singularity at \(x = \rho\), then roughly \(a_n \approx \rho^{-n}\) times a smaller factor determined by the type of singularity. For rational functions, the smallest root of the denominator dominates: \(F(x) = \frac{x}{1 - x - x^2}\) has its smallest root at \(1/\phi\), so \(F_n \sim \phi^n/\sqrt5\). For \(\frac{e^{-x}}{1 - x}\) the only singularity is a simple pole at 1, so \(D_n/n! \to e^{-1}\), the residue there. The Catalan function \(\frac{1 - \sqrt{1 - 4x}}{2x}\) has a square-root singularity at \(\frac14\), which produces both the \(4^n\) and the \(n^{-3/2}\). The partition function has singularities at every root of unity, which is why \(p(n)\) grows subexponentially and needed the circle method.

Recurrences and growth rates. A linear recurrence with constant coefficients has a rational generating function, so its solution grows like \(r^n\) times a polynomial, where \(r\) is the largest root of the characteristic equation. A divide-and-conquer recurrence such as \(T(n) = 2T(n/2) + n\) behaves differently, giving \(T(n) \approx n\log_2 n\); this is the territory of the master theorem studied in CMPUT-204. Telling which kind of recurrence one has is the first step in estimating any counting sequence.

import math

N = 200
p = [1] + [0] * N
for part in range(1, N + 1):
    for n in range(part, N + 1):
        p[n] += p[n - part]
print("p(1..15):", p[1:16])
print("p(100) =", p[100], "  p(200) =", p[200])

def pentagonal_p(N):
    q = [1] + [0] * N
    for n in range(1, N + 1):
        total, j = 0, 1
        while True:
            g1, g2 = j * (3 * j - 1) // 2, j * (3 * j + 1) // 2
            if g1 > n:
                break
            sign = 1 if j % 2 else -1
            total += sign * q[n - g1]
            if g2 <= n:
                total += sign * q[n - g2]
            j += 1
        q[n] = total
    return q
print("pentagonal recurrence agrees up to 200:", pentagonal_p(N) == p)

def count_parts(N, allowed, distinct=False):
    c = [1] + [0] * N
    for part in allowed:
        rng = range(N, part - 1, -1) if distinct else range(part, N + 1)
        for n in rng:
            c[n] += c[n - part]
    return c
dist = count_parts(40, range(1, 41), distinct=True)
odd = count_parts(40, range(1, 41, 2))
print("distinct parts = odd parts for n <= 40:", dist == odd, " e.g. n=10:", dist[10])

def at_most_k_parts(n, k, largest=None):
    if largest is None:
        largest = n
    if n == 0:
        return 1
    if k == 0:
        return 0
    return sum(at_most_k_parts(n - first, k - 1, first) for first in range(1, min(n, largest) + 1))
k_parts = [at_most_k_parts(12, k) for k in range(1, 7)]
max_part = [count_parts(12, range(1, k + 1))[12] for k in range(1, 7)]
print("n=12, at most k parts:", k_parts, "  largest part <= k:", max_part)

for n in [10, 50, 100, 200]:
    hr = math.exp(math.pi * math.sqrt(2 * n / 3)) / (4 * n * math.sqrt(3))
    print(f"n={n}: p(n)={p[n]}, Hardy-Ramanujan estimate {hr:.4g}, ratio {p[n] / hr:.4f}")

print("p(5n+4) divisible by 5:", all(p[5 * n + 4] % 5 == 0 for n in range(39)))
print("p(7n+5) divisible by 7:", all(p[7 * n + 5] % 7 == 0 for n in range(28)))
print("p(11n+6) divisible by 11:", all(p[11 * n + 6] % 11 == 0 for n in range(18)))

for n in [10, 100, 500]:
    exact = math.comb(2 * n, n) // (n + 1)
    approx = 4 ** n / (n ** 1.5 * math.sqrt(math.pi))
    print(f"Catalan C_{n}: exact/approx = {exact / approx:.5f}")
for n in [10, 50, 100]:
    print(f"Stirling ratio n!/(sqrt(2 pi n)(n/e)^n), n={n}: {math.factorial(n) / (math.sqrt(2 * math.pi * n) * (n / math.e) ** n):.6f}")

p(1..15): [1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176]
p(100) = 190569292   p(200) = 3972999029388
pentagonal recurrence agrees up to 200: True
distinct parts = odd parts for n <= 40: True  e.g. n=10: 10
n=12, at most k parts: [1, 7, 19, 34, 47, 58]   largest part <= k: [1, 7, 19, 34, 47, 58]
n=10: p(n)=42, Hardy-Ramanujan estimate 48.1, ratio 0.8731
n=50: p(n)=204226, Hardy-Ramanujan estimate 2.176e+05, ratio 0.9386
n=100: p(n)=190569292, Hardy-Ramanujan estimate 1.993e+08, ratio 0.9563
n=200: p(n)=3972999029388, Hardy-Ramanujan estimate 4.1e+12, ratio 0.9690
p(5n+4) divisible by 5: True
p(7n+5) divisible by 7: True
p(11n+6) divisible by 11: True
Catalan C_10: exact/approx = 0.89780
Catalan C_100: exact/approx = 0.98886
Catalan C_500: exact/approx = 0.99775
Stirling ratio n!/(sqrt(2 pi n)(n/e)^n), n=10: 1.008365
Stirling ratio n!/(sqrt(2 pi n)(n/e)^n), n=50: 1.001668
Stirling ratio n!/(sqrt(2 pi n)(n/e)^n), n=100: 1.000834

The two methods for \(p(n)\) agree, Euler's distinct-equals-odd identity checks to 40, and conjugation is confirmed for \(n = 12\). The Hardy–Ramanujan ratio creeps toward 1 slowly, about 0.96 at \(n = 100\), as the next term of Rademacher's series would correct. Ramanujan's three congruences hold throughout the table, and the Catalan and Stirling estimates improve as \(n\) grows, with relative errors of order \(1/n\).