Partition (number theory)
A partition of a positive integer (n) is a representation of (n) as a sum of positive integers in which the order of the summands is disregarded. The number of partitions of (n) is denoted by (p(n)), with the conventional initial value (p(0)=1). Thus, the integer (4) has five partitions:
[ 4,\qquad 3+1,\qquad 2+2,\qquad 2+1+1,\qquad 1+1+1+1, ]
and consequently (p(4)=5). This notion differs from a composition, in which changing the order of the summands generally produces a distinct object.
Integer partitions are central objects in additive number theory and enumerative combinatorics. Their study connects formal power series, modular forms, representation theory, and asymptotic analysis. Although the definition concerns unordered sums, much of the structure of partition theory becomes visible only after partitions are encoded as sequences, diagrams, or coefficients of generating functions.
Formal definition and diagrammatic representation
A partition (\lambda) of (n), written (\lambda\vdash n), is a finite nonincreasing sequence
[ \lambda=(\lambda_1,\lambda_2,\ldots,\lambda_r) ]
of positive integers satisfying
[ \lambda_1+\lambda_2+\cdots+\lambda_r=n. ]
The values (\lambda_i) are the parts of the partition, while (r) is its length. An equivalent frequency notation records the multiplicity (m_j) of each possible part (j):
[ \lambda=(1^{m_1}2^{m_2}3^{m_3}\cdots), \qquad \sum_{j\geq 1}j,m_j=n. ]
A Ferrers diagram represents each part by a row of equally spaced points, with row lengths arranged in nonincreasing order. Replacing the points by left-justified boxes produces a Young diagram, which is extensively used in the representation theory of symmetric groups and general linear groups.
Reflection of a Ferrers or Young diagram across its main diagonal defines the conjugate partition (\lambda'). Under this operation, the number of parts of (\lambda) becomes the largest part of (\lambda'), and the largest part of (\lambda) becomes the number of parts of (\lambda'). Consequently, partitions of (n) into exactly (k) parts are equinumerous with partitions of (n) whose largest part is (k).
A partition equal to its conjugate is called self-conjugate. The diagonal boxes of its Young diagram determine distinct odd integers through their hook lengths. This correspondence gives a bijection between self-conjugate partitions of (n) and partitions of (n) into distinct odd parts.
Generating function
The ordinary generating function for the partition numbers is
[ \sum_{n=0}^{\infty}p(n)q^n
\prod_{m=1}^{\infty}\frac{1}{1-q^m}. ]
Each factor has the formal expansion
[ \frac{1}{1-q^m}=1+q^m+q^{2m}+q^{3m}+\cdots, ]
where the exponent (jm) records the inclusion of (j) parts of size (m). Multiplication over all positive values of (m) therefore records every partition exactly once.
Leonhard Euler established this product formulation during the eighteenth century and used it to derive the pentagonal number theorem:
[ \prod_{m=1}^{\infty}(1-q^m)
\sum_{k=-\infty}^{\infty} (-1)^k q^{k(3k-1)/2}. ]
Taking coefficients after multiplying by the partition generating function gives Euler’s recurrence
[ p(n)= \sum_{k=1}^{\infty} (-1)^{k+1} \left( p!\left(n-\frac{k(3k-1)}{2}\right) + p!\left(n-\frac{k(3k+1)}{2}\right) \right), ]
where (p(m)=0) for negative (m). For each fixed (n), only finitely many terms contribute. The recurrence reflects cancellation among partitions rather than direct decomposition into smaller unrestricted partitions.
The product also has a modular interpretation. If (q=e^{2\pi i\tau}), then
[ \eta(\tau)=q^{1/24}\prod_{m=1}^{\infty}(1-q^m) ]
is the Dedekind eta function, and hence
[ \sum_{n=0}^{\infty}p(n)q^n=\frac{q^{1/24}}{\eta(\tau)}. ]
The transformation law of (\eta(\tau)) under the modular group is responsible for several exact formulas, congruences, and asymptotic properties of (p(n)).
Asymptotic and exact formulas
The partition function grows faster than every polynomial but slower than every exponential function (c^n) with fixed (c>1). In 1918, G. H. Hardy and Srinivasa Ramanujan applied the circle method to the partition generating function and obtained
[ p(n)\sim \frac{1}{4n\sqrt{3}} \exp\left(\pi\sqrt{\frac{2n}{3}}\right) \qquad (n\to\infty). ]
Their analysis divides a contour around the origin into arcs associated with rational points on the unit circle. The dominant contribution comes from the singular behavior near (q=1), while the remaining rational points supply lower-order corrections.
In 1937, Hans Rademacher and You Watanabe developed the Farey-arc estimates that convert the Hardy–Ramanujan asymptotic expansion into a convergent series. In its standard normalization, the resulting expression is
[ p(n)= \frac{1}{\pi\sqrt{2}} \sum_{k=1}^{\infty} A_k(n)\sqrt{k}, \frac{d}{dn} \left[ \frac{ \sinh\left( \frac{\pi}{k} \sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)} \right) }{ \sqrt{n-\frac{1}{24}} } \right], ]
where (A_k(n)) is a finite exponential sum determined by modular transformations of the eta function. These sums are closely related to Kloosterman sums. The convergence of the series distinguishes it from the earlier asymptotic expansion and permits exact recovery of (p(n)) after sufficiently many controlled terms.
The leading (k=1) contribution yields the Hardy–Ramanujan approximation. Terms with larger (k) encode the influence of other roots of unity on the generating function, with exponentially decreasing contributions governed by the corresponding denominator (k).
Restricted partitions and bijections
Many classical partition theorems compare restrictions that appear unrelated at the level of summands. If (d(n)) denotes the number of partitions of (n) into distinct parts and (o(n)) denotes the number using only odd parts, then Euler’s identity gives
[ d(n)=o(n). ]
The generating-function proof follows from
[ \prod_{m=1}^{\infty}(1+q^m)
\prod_{m=1}^{\infty}\frac{1}{1-q^{2m-1}}. ]
On the left, the factor (1+q^m) allows the part (m) to occur at most once. On the right, each odd part may occur with arbitrary multiplicity. A direct bijection replaces repeated equal parts by powers-of-two groupings until all resulting parts are distinct; reversing the binary decomposition recovers the odd-part partition.
The Rogers–Ramanujan identities provide more intricate correspondences. One identity equates partitions whose adjacent parts differ by at least two with partitions whose parts belong to specified residue classes modulo five:
[ \sum_{r=0}^{\infty} \frac{q^{r^2}}{(q;q)_r}
\prod_{m=0}^{\infty} \frac{1}{(1-q^{5m+1})(1-q^{5m+4})}, ]
where
[ (q;q)r=\prod{j=1}^{r}(1-q^j). ]
The sum encodes a difference condition among parts, whereas the product encodes congruence restrictions. Their equality demonstrates that local spacing constraints and arithmetic residue conditions can define equinumerous partition families.
Congruences and partition statistics
Ramanujan discovered three fundamental congruence families:
[ p(5n+4)\equiv 0\pmod 5, ]
[ p(7n+5)\equiv 0\pmod 7, ]
[ p(11n+6)\equiv 0\pmod {11}. ]
These congruences arise from the modular structure of the partition generating function. They are not explained merely by rearranging Euler’s product, because the divisibility occurs uniformly across entire arithmetic progressions.
To formulate combinatorial explanations, Freeman Dyson introduced the rank of a partition, defined as its largest part minus its number of parts. Rank residue classes divide the partitions appearing in the congruences modulo five and seven into equally sized groups. The rank does not supply the analogous decomposition modulo eleven.
The missing statistic was later identified by George Andrews and Frank Garvan as the crank. For a partition containing no part equal to one, its crank is its largest part. When parts equal to one occur, the crank is the number of parts larger than the number of ones minus the number of ones. Residue classes of the crank provide uniform combinatorial decompositions for all three Ramanujan congruences.
These statistics also support refinements in which the generating function records both the integer being partitioned and the value of the statistic. Such two-variable series connect partition congruences with Jacobi forms, mock modular forms, and harmonic Maass forms.
Representation-theoretic significance
Partitions index the conjugacy classes of the symmetric group (S_n), since each permutation decomposes into disjoint cycles whose lengths form a partition of (n). They also index the irreducible complex representations of (S_n). Under this correspondence, a partition determines a Specht module, while standard Young tableaux describe a natural basis.
The dimension of the irreducible representation associated with (\lambda\vdash n) is given by the hook-length formula:
[ f^\lambda
\frac{n!}{\prod_{u\in\lambda}h(u)}, ]
where (h(u)) is the hook length of the box (u) in the Young diagram. Summing the squares of these dimensions gives
[ \sum_{\lambda\vdash n}(f^\lambda)^2=n!, ]
in agreement with the decomposition of the regular representation of (S_n). This setting makes partitions structural labels for algebraic objects rather than solely representations of integers as sums.