Partition function (mathematics)
The partition function (p(n)) counts the distinct ways in which a nonnegative integer (n) can be expressed as a sum of positive integers, where rearrangements of the summands are not regarded as different. Each such expression is an integer partition. The function is therefore defined by
[ p(n)=#\left{(\lambda_1,\ldots,\lambda_k): \lambda_1\geq\cdots\geq\lambda_k\geq1,\ \sum_{j=1}^{k}\lambda_j=n\right}. ]
The empty partition gives the conventional value (p(0)=1), while (p(n)=0) for negative integers. The first values are
[ p(0)=1,\quad p(1)=1,\quad p(2)=2,\quad p(3)=3,\quad p(4)=5,\quad p(5)=7,\quad p(6)=11. ]
For example, the five partitions of (4) are represented by (4), (3+1), (2+2), (2+1+1), and (1+1+1+1). This counting function is unrelated to the thermodynamic partition function, although both concepts are expressed through generating sums and products.
Generating function
The ordinary generating function of (p(n)) is Euler's infinite product
[ \sum_{n=0}^{\infty}p(n)q^n
\prod_{m=1}^{\infty}\frac{1}{1-q^m}, \qquad |q|<1. ]
Each factor has the geometric expansion
[ \frac{1}{1-q^m}=1+q^m+q^{2m}+q^{3m}+\cdots. ]
Selecting the term (q^{a_m m}) from the factor indexed by (m) records the occurrence of (a_m) parts of size (m). Consequently, the coefficient of (q^n) in the full product counts precisely the sequences of multiplicities satisfying
[ \sum_{m\geq1}m a_m=n. ]
The reciprocal product
[ (q;q)\infty=\prod{m=1}^{\infty}(1-q^m) ]
is expressed in standard (q)-series notation through the (q)-Pochhammer symbol. Leonhard Euler connected this product with the generalized pentagonal numbers through the pentagonal number theorem:
[ \prod_{m=1}^{\infty}(1-q^m)
\sum_{k=-\infty}^{\infty} (-1)^k q^{k(3k-1)/2}. ]
This identity converts the product representation into a recurrence for the partition numbers.
Recurrence relations
Euler's recurrence takes the form
[ 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], ]
with the conventions (p(0)=1) and (p(r)=0) whenever (r<0). For any fixed (n), only finitely many terms have nonnegative arguments, so the displayed infinite sum represents a finite recurrence.
A second recurrence follows from the logarithmic derivative of the generating function. If
[ \sigma_1(k)=\sum_{d\mid k}d ]
denotes the sum-of-divisors function, then
[ n,p(n)=\sum_{k=1}^{n}\sigma_1(k),p(n-k). ]
This relation reflects the identity
[ q\frac{d}{dq} \log\left(\prod_{m=1}^{\infty}\frac{1}{1-q^m}\right)
\sum_{k=1}^{\infty}\sigma_1(k)q^k. ]
Both recurrences determine (p(n)) from earlier values, although they arise from different structural properties of Euler's product.
Asymptotic growth
The partition function grows faster than every polynomial but more slowly than every exponential function (c^n) with fixed (c>1). In 1918, G. H. Hardy and Srinivasa Ramanujan applied the circle method to obtain the leading asymptotic formula
[ p(n)\sim \frac{1}{4n\sqrt{3}} \exp\left(\pi\sqrt{\frac{2n}{3}}\right) \qquad (n\to\infty). ]
Equivalently,
[ \log p(n)\sim \pi\sqrt{\frac{2n}{3}}. ]
The exponential term originates from the behavior of Euler's product near (q=1), while the factor (1/(4n\sqrt3)) results from the local analytic contribution around the dominant singularity. The circle method also incorporates contributions from roots of unity, where the generating function exhibits additional singular behavior governed by modular transformations.
Hardy and Ramanujan developed a finite asymptotic expansion whose truncations approximate (p(n)) with progressively refined error terms. Their analysis established a connection between partition enumeration and the transformation theory of modular forms, particularly through the Dedekind eta function.
Convergent series
In 1937, Hans Rademacher and You Watanabe reformulated the circle-method analysis by decomposing the integration contour into arcs associated with Farey sequences. Their construction replaced the earlier asymptotic expansion with an infinite series that converges exactly to (p(n)). In a standard normalization, the resulting formula is
[ p(n)= \frac{1}{\pi\sqrt2} \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]. ]
The coefficient (A_k(n)) is a finite exponential sum over residue classes relatively prime to (k). Its phase contains a Dedekind sum, arising from the modular transformation law of the eta function. The term with (k=1) produces the principal Hardy–Ramanujan asymptotic, while the terms with larger (k) encode successively smaller contributions from the remaining roots of unity.
Convergence distinguishes this expression from an ordinary asymptotic series. The complete sum equals the integer (p(n)), whereas a finite truncation differs from it by a quantitatively controlled remainder. The construction became the model for later exact expansions involving modular forms of negative weight and their Fourier coefficients.
Modular interpretation
The generating function is related to the Dedekind eta function by
[ \eta(\tau)
e^{\pi i\tau/12} \prod_{m=1}^{\infty} \left(1-e^{2\pi i m\tau}\right), \qquad \operatorname{Im}(\tau)>0. ]
Writing (q=e^{2\pi i\tau}) gives
[ \sum_{n=0}^{\infty}p(n)q^n
\frac{q^{1/24}}{\eta(\tau)}. ]
The fractional power (q^{1/24}) accounts for the shift (n-\tfrac{1}{24}) in the convergent series. Although (1/\eta(\tau)) is not a modular form with an ordinary integral-weight transformation law, it transforms with weight (-\tfrac12) and a nontrivial multiplier system. These transformation properties control the analytic behavior of the partition generating function near rational points on the unit circle.
The modular interpretation also explains why arithmetic information about (p(n)) can emerge from analytic identities. Congruences among partition numbers are reflected in identities between modular forms after the generating function is modified by suitable powers of the eta function.
Congruences
Ramanujan discovered the congruences
[ p(5m+4)\equiv0\pmod5, ]
[ p(7m+5)\equiv0\pmod7, ]
and
[ p(11m+6)\equiv0\pmod{11}. ]
These relations hold for every nonnegative integer (m). They demonstrate that the values of (p(n)), despite their rapid and irregular numerical growth, possess systematic behavior in selected arithmetic progressions.
Later work interpreted such congruences through modular forms and Hecke-type operators. The subject extends beyond the three classical identities to infinite families of congruences involving powers of primes and more general arithmetic progressions. This theory belongs to the broader study of partition congruences and the arithmetic of modular generating functions.
Restricted partitions
Many related counting functions arise by restricting the permitted parts or their multiplicities. The generating function for partitions into distinct parts is
[ \prod_{m=1}^{\infty}(1+q^m), ]
since each positive integer may occur either once or not at all. The generating function for partitions into odd parts is
[ \prod_{m=1}^{\infty}\frac{1}{1-q^{2m-1}}. ]
Euler's identity
[ \prod_{m=1}^{\infty}(1+q^m)
\prod_{m=1}^{\infty}\frac{1}{1-q^{2m-1}} ]
shows that the number of partitions into distinct parts equals the number of partitions into odd parts. This equality is also realized by direct bijective proofs, which transform one type of restricted partition into the other without comparing coefficients analytically.
Partitions may additionally be represented by Young diagrams or Ferrers diagrams. Conjugating such a diagram exchanges its rows and columns, establishing that the number of partitions of (n) into at most (k) parts equals the number whose largest part is at most (k). This geometric symmetry underlies many identities for restricted partition functions.