An integer partition of a nonnegative integer is a way of writing as a sum of positive integers, with the order of the summands disregarded. The summands are called parts. Integer partitions are fundamental objects in combinatorics and number theory, where they connect elementary counting problems with infinite products, congruences, and the representation theory of groups. The number of partitions of is denoted by , the partition function.
Definition and examples
A partition of can be represented uniquely as a finite, weakly decreasing sequence
The notation means that is a partition of . Its size is , and its length is its number of parts.
The five partitions of are
Thus . The expressions and describe the same partition.
There is one partition of : the empty partition, containing no parts. Consequently, . It is also convenient to define for negative integers . The first values are
An alternative representation records the multiplicity of each part :
The exponents here indicate repetition, not ordinary exponentiation.
Distinction from related objects
A composition of is an ordered sum of positive integers. Thus and are different compositions but the same partition.
A set partition divides a set of distinguishable elements into disjoint, nonempty blocks. The block sizes determine an integer partition, but generally many set partitions have the same block sizes. Integer partitions record sizes without retaining the identities of the elements.
Diagrams and conjugation
A partition can be visualized by arranging rows of dots or square boxes whose lengths are its parts. Dot representations are commonly called Ferrers diagrams, while box representations are called Young diagrams, although terminology varies.
In the convention with rows aligned on the left and the longest row at the top, the partition has diagram
□□□□
□□
□
Transposing the diagram exchanges rows and columns and gives the conjugate partition . Its parts satisfy
For example,
Conjugation is an involution: . It exchanges the largest part and the number of parts. As a result, the number of partitions of into exactly parts equals the number whose largest part is exactly . Likewise, partitions into at most parts are equinumerous with partitions whose parts are all at most .
A partition equal to its conjugate is self-conjugate. Such partitions correspond bijectively to partitions into distinct odd parts: the hook lengths of the diagonal boxes provide those odd parts.
Generating functions
The ordinary generating function for is Euler’s product:
For each possible part size , the geometric series
records the choice of its multiplicity. Multiplying the factors records all choices of multiplicities, and the exponent of records the resulting total.
The identity can be interpreted as a formal power series identity: computing the coefficient of requires only the factors with . It also holds analytically for complex with .
A second variable can track the number of parts:
where counts partitions of into exactly parts.
Restricted partitions
Many partition problems restrict the allowed sizes or multiplicities of parts. Their generating functions follow from the same principle:
Parts in a set of positive integers:
Distinct parts:
Odd parts:
Parts at most :
The generating function for exactly positive parts is
Subtracting from every part turns such a partition into one of with at most parts.
Partition identities
A partition identity states that two differently restricted classes of partitions have the same number of elements for every size. Such identities may be established through generating functions or by constructing an explicit bijection.
Euler’s odd–distinct identity
Leonhard Euler proved that the number of partitions of into distinct parts equals the number into odd parts. The generating-function proof uses
A bijective proof repeatedly replaces two equal parts by one part . Starting from odd parts, this process produces distinct parts. The reverse operation splits every even part into equal halves until all parts are odd.
Rogers–Ramanujan identities
A deeper example is the first Rogers–Ramanujan identity:
with the denominator in the term interpreted as .
Combinatorially, it states that partitions whose successive parts differ by at least are equinumerous with partitions whose parts are congruent to or modulo . Such results connect difference conditions on neighboring parts with arithmetic conditions on individual part sizes.
Recurrences and computation
Euler’s pentagonal number theorem states
Combining this identity with the generating function for yields the recurrence
Only terms with nonnegative arguments contribute. Its beginning is
The offsets are generalized pentagonal numbers. Computing all values through by this recurrence requires integer additions and subtractions and stored values, using big-O notation. This counts arithmetic operations rather than bit operations; the integers themselves grow with .
A simpler dynamic-programming method begins with an array , for . For each allowed part size , it updates
for , in increasing order. Using every size from through computes unrestricted partition numbers in arithmetic operations. Restricting the processed sizes gives corresponding restricted partition counts.
Counting partitions is much cheaper than explicitly listing them when is large, because listing requires producing all objects.
Congruences and asymptotic growth
Ramanujan’s congruences
Srinivasa Ramanujan discovered striking divisibility patterns:
These statements belong to modular arithmetic and arise within a broader theory relating partition generating functions to modular forms.
The Hardy–Ramanujan formula
In 1918, G. H. Hardy and Ramanujan obtained the asymptotic formula
Here means that the ratio of the two expressions tends to .
Thus grows faster than every fixed power of , but slower than for every fixed . The leading expression is an approximation, not an exact formula for finite .
Their work helped establish the circle method, which extracts coefficients by analyzing generating functions near roots of unity. In 1937, Hans Rademacher obtained a convergent series giving exactly. Unlike a leading asymptotic approximation, sufficiently many terms of that series, combined with an error bound, can determine the exact integer value.
Algebraic and probabilistic connections
Symmetric groups and symmetric functions
The symmetric group has conjugacy classes indexed by partitions of : the partition records the cycle lengths of a permutation. Its irreducible complex representations are also indexed by partitions of , making partitions central to representation theory.
Young diagrams support additional structures called Young tableaux. In a standard Young tableau of size , the boxes contain , increasing along each row and each column. The number of standard tableaux of shape equals the dimension of the irreducible representation associated with .
Partitions also index important bases of symmetric functions, including Schur functions, providing links among algebra, geometry, and combinatorial identities.
Random partitions
A probability distribution on partitions turns their shapes and statistics into random objects. One model assigns equal probability to each partition of . Other models weight partitions using representation-theoretic quantities.
These choices give different typical behavior. Questions include the distribution of the largest part, the number of parts, and the limiting profile of a suitably rescaled diagram. A probability model must therefore be specified before statements about a “typical partition” have a definite meaning.