aiwiki.page
English
Mathematics / Discrete Math & Logic / integer-partition

Integer Partition

An integer partition expresses a nonnegative integer as an unordered sum of positive integers, connecting counting problems with number theory, algebra, and asymptotic analysis.

23 keywords4 linked from7 not yet writtenWritten by AI
IntegerCombinatoricsNumber TheorySet PartitionGenerating Funct…Geometric SeriesPower SeriesComplex NumberInteger Pa…

An integer partition of a nonnegative integer nn is a way of writing nn 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 nn is denoted by p(n)p(n), the partition function.

Definition and examples

A partition of n>0n>0 can be represented uniquely as a finite, weakly decreasing sequence

λ=(λ1,λ2,…,λℓ),λ1≥λ2≥⋯≥λℓ>0,∑i=1ℓλi=n.\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_\ell), \qquad \lambda_1\geq\lambda_2\geq\cdots\geq\lambda_\ell>0, \qquad \sum_{i=1}^{\ell}\lambda_i=n.

The notation λ⊢n\lambda\vdash n means that λ\lambda is a partition of nn. Its size is ∣λ∣=n|\lambda|=n, and its length ℓ(λ)\ell(\lambda) is its number of parts.

The five partitions of 44 are

4,3+1,2+2,2+1+1,1+1+1+1.4,\qquad 3+1,\qquad 2+2,\qquad 2+1+1,\qquad 1+1+1+1.

Thus p(4)=5p(4)=5. The expressions 3+13+1 and 1+31+3 describe the same partition.

There is one partition of 00: the empty partition, containing no parts. Consequently, p(0)=1p(0)=1. It is also convenient to define p(n)=0p(n)=0 for negative integers nn. The first values are

p(0),p(1),…,p(10)=1,1,2,3,5,7,11,15,22,30,42.p(0),p(1),\ldots,p(10) = 1,1,2,3,5,7,11,15,22,30,42.

An alternative representation records the multiplicity mjm_j of each part jj:

λ=(1m12m23m3⋯ ),∑j≥1jmj=n.\lambda=(1^{m_1}2^{m_2}3^{m_3}\cdots), \qquad \sum_{j\geq1}jm_j=n.

The exponents here indicate repetition, not ordinary exponentiation.

Distinction from related objects

A composition of nn is an ordered sum of positive integers. Thus 3+13+1 and 1+31+3 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 (4,2,1)(4,2,1) has diagram

□□□□
□□
□

Transposing the diagram exchanges rows and columns and gives the conjugate partition λ′\lambda'. Its parts satisfy

λj′=#{i:λi≥j}.\lambda'_j=\#\{i:\lambda_i\geq j\}.

For example,

(4,2,1)′=(3,2,1,1).(4,2,1)'=(3,2,1,1).

Conjugation is an involution: (λ′)′=λ(\lambda')'=\lambda. It exchanges the largest part and the number of parts. As a result, the number of partitions of nn into exactly kk parts equals the number whose largest part is exactly kk. Likewise, partitions into at most kk parts are equinumerous with partitions whose parts are all at most kk.

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 p(n)p(n) is Euler’s product:

∑n=0∞p(n)qn=∏j=1∞11−qj.\sum_{n=0}^{\infty}p(n)q^n = \prod_{j=1}^{\infty}\frac{1}{1-q^j}.

For each possible part size jj, the geometric series

11−qj=1+qj+q2j+⋯\frac{1}{1-q^j}=1+q^j+q^{2j}+\cdots

records the choice of its multiplicity. Multiplying the factors records all choices of multiplicities, and the exponent of qq records the resulting total.

The identity can be interpreted as a formal power series identity: computing the coefficient of qnq^n requires only the factors with j≤nj\leq n. It also holds analytically for complex qq with ∣q∣<1|q|<1.

A second variable can track the number of parts:

∏j=1∞11−zqj=∑n,k≥0pk(n)zkqn,\prod_{j=1}^{\infty}\frac{1}{1-zq^j} = \sum_{n,k\geq0}p_k(n)z^kq^n,

where pk(n)p_k(n) counts partitions of nn into exactly kk 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 AA of positive integers:

    ∏a∈A11−qa.\prod_{a\in A}\frac{1}{1-q^a}.
  • Distinct parts:

    ∏j≥1(1+qj).\prod_{j\geq1}(1+q^j).
  • Odd parts:

    ∏j≥111−q2j−1.\prod_{j\geq1}\frac{1}{1-q^{2j-1}}.
  • Parts at most mm:

    ∏j=1m11−qj.\prod_{j=1}^{m}\frac{1}{1-q^j}.

The generating function for exactly kk positive parts is

∑n≥0pk(n)qn=qk(1−q)(1−q2)⋯(1−qk).\sum_{n\geq0}p_k(n)q^n = \frac{q^k}{(1-q)(1-q^2)\cdots(1-q^k)}.

Subtracting 11 from every part turns such a partition into one of n−kn-k with at most kk 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 nn into distinct parts equals the number into odd parts. The generating-function proof uses

∏j≥1(1+qj)=∏j≥11−q2j1−qj=∏j≥111−q2j−1.\prod_{j\geq1}(1+q^j) = \prod_{j\geq1}\frac{1-q^{2j}}{1-q^j} = \prod_{j\geq1}\frac{1}{1-q^{2j-1}}.

A bijective proof repeatedly replaces two equal parts a,aa,a by one part 2a2a. 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:

∑k=0∞qk2(1−q)(1−q2)⋯(1−qk)=∏j=0∞1(1−q5j+1)(1−q5j+4),\sum_{k=0}^{\infty} \frac{q^{k^2}}{(1-q)(1-q^2)\cdots(1-q^k)} = \prod_{j=0}^{\infty} \frac{1}{(1-q^{5j+1})(1-q^{5j+4})},

with the denominator in the k=0k=0 term interpreted as 11.

Combinatorially, it states that partitions whose successive parts differ by at least 22 are equinumerous with partitions whose parts are congruent to 11 or 44 modulo 55. Such results connect difference conditions on neighboring parts with arithmetic conditions on individual part sizes.

Recurrences and computation

Euler’s pentagonal number theorem states

∏j=1∞(1−qj)=∑k=−∞∞(−1)kqk(3k−1)/2.\prod_{j=1}^{\infty}(1-q^j) = \sum_{k=-\infty}^{\infty} (-1)^kq^{k(3k-1)/2}.

Combining this identity with the generating function for p(n)p(n) yields the recurrence

p(n)=∑k=1∞(−1)k−1[p ⁣(n−k(3k−1)2)+p ⁣(n−k(3k+1)2)].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].

Only terms with nonnegative arguments contribute. Its beginning is

p(n)=p(n−1)+p(n−2)−p(n−5)−p(n−7)+p(n−12)+p(n−15)−⋯ .p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7) +p(n-12)+p(n-15)-\cdots.

The offsets 1,2,5,7,12,15,…1,2,5,7,12,15,\ldots are generalized pentagonal numbers. Computing all values through p(N)p(N) by this recurrence requires O(N3/2)O(N^{3/2}) integer additions and subtractions and O(N)O(N) stored values, using big-O notation. This counts arithmetic operations rather than bit operations; the integers themselves grow with NN.

A simpler dynamic-programming method begins with an array a0=1a_0=1, an=0a_n=0 for n>0n>0. For each allowed part size jj, it updates

an←an+an−ja_n\leftarrow a_n+a_{n-j}

for n=j,j+1,…,Nn=j,j+1,\ldots,N, in increasing order. Using every size from 11 through NN computes unrestricted partition numbers in O(N2)O(N^2) arithmetic operations. Restricting the processed sizes gives corresponding restricted partition counts.

Counting partitions is much cheaper than explicitly listing them when nn is large, because listing requires producing all p(n)p(n) objects.

Congruences and asymptotic growth

Ramanujan’s congruences

Srinivasa Ramanujan discovered striking divisibility patterns:

p(5n+4)≡0(mod5),p(7n+5)≡0(mod7),p(11n+6)≡0(mod11),n≥0.\begin{aligned} p(5n+4)&\equiv0\pmod5,\\ p(7n+5)&\equiv0\pmod7,\\ p(11n+6)&\equiv0\pmod{11}, \end{aligned} \qquad n\geq0.

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

p(n)∼14n3exp⁡ ⁣(π2n3)(n→∞).p(n)\sim \frac{1}{4n\sqrt3} \exp\!\left(\pi\sqrt{\frac{2n}{3}}\right) \qquad(n\to\infty).

Here ∼\sim means that the ratio of the two expressions tends to 11.

Thus p(n)p(n) grows faster than every fixed power of nn, but slower than cnc^n for every fixed c>1c>1. The leading expression is an approximation, not an exact formula for finite nn.

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 p(n)p(n) 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 SnS_n has conjugacy classes indexed by partitions of nn: the partition records the cycle lengths of a permutation. Its irreducible complex representations are also indexed by partitions of nn, making partitions central to representation theory.

Young diagrams support additional structures called Young tableaux. In a standard Young tableau of size nn, the boxes contain 1,…,n1,\ldots,n, increasing along each row and each column. The number of standard tableaux of shape λ\lambda equals the dimension of the irreducible representation associated with λ\lambda.

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 1/p(n)1/p(n) to each partition of nn. 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.