8.1 Integer partitions and partition functions

Integer Partitions and Partition Functions

An integer partition of a positive integer $n$ is a way of writing $n$ as a sum of positive integers, where the order of the summands doesn't matter. The partition function $p(n)$ counts how many such partitions exist for a given $n$. This topic sits at the crossroads of combinatorics, number theory, and algebra, and the techniques used here (generating functions, recurrences, asymptotics) show up repeatedly across all three fields.

Integer Partitions

Definition and Representation

Take $n = 4$. Its partitions are:

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

So $p(4) = 5$. Notice that $3+1$ and $1+3$ count as the same partition because order doesn't matter. By convention, parts are listed in non-increasing order.

Ferrers and Young diagrams give a visual way to represent partitions. For the partition $5 + 3 + 1$ of 9, you draw left-aligned rows of dots (or boxes), one row per part:

</>Code
● ● ● ● ●
● ● ●
●

The conjugate partition is what you get by reflecting a Ferrers diagram across its main diagonal (swapping rows and columns). The conjugate of $5 + 3 + 1$ is $3 + 2 + 2 + 1 + 1$. A self-conjugate partition is one that equals its own conjugate, meaning its Ferrers diagram is symmetric about the main diagonal.

Classification and Properties

Several important types of partitions come up repeatedly:

• Odd partitions use only odd parts. For example, $7 = 5 + 1 + 1$ or $7 = 3 + 3 + 1$.
• Distinct partitions have no repeated parts. For example, $7 = 4 + 2 + 1$.
• Restricted partitions impose constraints on the size or number of parts. For instance, the partitions of 7 with all parts $\leq 3$ are: $3+3+1$, $3+2+2$, $3+2+1+1$, $2+2+2+1$, $2+2+1+1+1$, $2+1+1+1+1+1$, $1+1+1+1+1+1+1$.

One of the most elegant results in this area is Euler's theorem: for any positive integer $n$, the number of partitions into odd parts equals the number of partitions into distinct parts. You can prove this using generating functions (covered below) or by constructing an explicit bijection between the two sets.

Partition Functions

Calculation Methods

Computing $p(n)$ directly by listing partitions gets impractical fast ($p(100) = 190{,}569{,}292{,}356$). Here are the main approaches, from most elementary to most advanced:

1. Dynamic programming. Build a table of partition counts bottom-up. To count partitions of $n$ with parts at most $k$, use the recurrence: a partition either includes $k$ as a part (reduce to partitions of $n-k$ with parts $\leq k$) or it doesn't (reduce to partitions of $n$ with parts $\leq k-1$). This runs in $O(n^2)$ time and is the most practical method for moderate $n$.

2. Euler's pentagonal number theorem. This gives a recurrence for $p(n)$ directly:

$p(n) = \sum_{k \neq 0} (-1)^{k+1} \, p\!\left(n - \tfrac{k(3k-1)}{2}\right)$

where the sum runs over $k = 1, -1, 2, -2, 3, -3, \ldots$ and you stop when the argument goes negative. The values $\frac{k(3k-1)}{2}$ are the generalized pentagonal numbers (1, 2, 5, 7, 12, 15, ...). This is more efficient than brute force because only $O(\sqrt{n})$ terms are needed.

1. Hardy-Ramanujan-Rademacher formula. This gives an exact expression for $p(n)$ as a convergent infinite series involving complex exponentials and Kloosterman-type sums. It draws on deep ideas from complex analysis and is mainly of theoretical importance, though it can also be used for computation.

Modular Properties

Ramanujan discovered striking congruences for $p(n)$:

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

These connect partition theory to modular forms and have been generalized extensively. Modular arithmetic properties of $p(n)$ also have applications in areas like cryptography.

Generating Functions for Partitions

Derivation and Applications

The central identity in partition theory is Euler's partition generating function:

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

Why does this work? Each factor $\frac{1}{1-x^k} = 1 + x^k + x^{2k} + x^{3k} + \cdots$ represents choosing how many copies of the part $k$ to include (0, 1, 2, ...). When you multiply all these factors together, the coefficient of $x^n$ collects every way to combine parts that sum to $n$.

You can modify this product to handle restricted partitions:

• Distinct parts only: replace each factor with $(1 + x^k)$, giving $\prod_{k=1}^{\infty}(1+x^k)$.
• Odd parts only: keep only odd values of $k$, giving $\prod_{j=0}^{\infty}\frac{1}{1-x^{2j+1}}$.

The fact that these two products are equal is exactly Euler's odd-distinct theorem, proved at the generating function level.

The q-binomial coefficients (Gaussian binomial coefficients) extend this framework to partitions that fit inside a given bounding box (parts $\leq m$, at most $k$ parts). They satisfy analogues of Pascal's identity and appear throughout combinatorics and algebra.

Analysis Techniques

• Coefficient extraction: Techniques like partial fractions or residue calculus let you pull explicit formulas for $p(n)$ (or restricted variants) from generating functions.
• Multivariate generating functions: These handle more complex objects like plane partitions (3D analogues of ordinary partitions) or vector partitions.
• Differential operators: Applying $x\frac{d}{dx}$ to a generating function and extracting coefficients lets you compute partition statistics, such as the average number of parts or the average largest part.

Asymptotic Behavior of Partitions

Asymptotic Formulas

For large $n$, the Hardy-Ramanujan asymptotic formula gives:

$p(n) \sim \frac{1}{4n\sqrt{3}}\, e^{\pi\sqrt{2n/3}}$

The $\sim$ means the ratio of the two sides approaches 1 as $n \to \infty$. The key takeaway: $p(n)$ grows sub-exponentially in $n$ itself but exponentially in $\sqrt{n}$. This is much faster than any polynomial but slower than functions like $2^n$.

To get a feel for the growth: $p(10) = 42$, $p(50) = 204{,}226$, $p(100) \approx 1.9 \times 10^{8}$, and $p(200) \approx 3.97 \times 10^{12}$.

Rademacher's convergent series refines the Hardy-Ramanujan estimate into an exact formula by adding correction terms. With enough terms, it gives $p(n)$ exactly (you round the result to the nearest integer).

Advanced Analytical Methods

• The circle method (Hardy-Ramanujan-Littlewood) analyzes $p(n)$ by studying the generating function on carefully chosen arcs of the unit circle in the complex plane. Major arcs near roots of unity contribute the main asymptotic terms; minor arcs contribute negligible error.
• Saddle-point methods offer an alternative route to asymptotics by deforming the contour of integration to pass through a saddle point of the integrand.
• Restricted partition functions have their own asymptotic behavior, often studied with Mellin transforms and related analytic number theory tools.
• Deep connections exist between partition asymptotics and modular forms. Ramanujan's congruences (mentioned above) are one manifestation; the modularity of the Dedekind eta function $\eta(\tau) = q^{1/24}\prod_{n=1}^{\infty}(1-q^n)$ underlies much of the theory.