In number theory, the partition function p(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.

No closed-form expression for the partition function is known, but it has both asymptotic expansions that accurately approximate it and recurrence relations by which it can be calculated exactly. It grows as an exponential function of the square root of its argument. The multiplicative inverse of its generating function is the Euler function; by Euler's pentagonal number theorem, this function is an alternating sum of pentagonal number powers of its argument.

Srinivasa Ramanujan first discovered that the partition function has nontrivial patterns in modular arithmetic, now known as Ramanujan's congruences. For instance, whenever the decimal representation of n ends in the digit 4 or 9, the number of partitions of n will be divisible by 5.

For a positive integer n, p(n) is the number of distinct ways of representing n as a sum of positive integers. For the purposes of this definition, the order of the terms in the sum is irrelevant: two sums with the same terms in a different order (e.g., 1 + 1 + 2 and 1 + 2 + 1) are not considered distinct.

By convention p(0) = 1, as there is one way of representing 0 as a sum of positive integers (the empty sum). Furthermore p(n) = 0 when n is negative.

The first few values of the partition function, starting with p(0) = 1, are

Some exact values of p(n) for larger values of n include $${\displaystyle {\begin{aligned}p(100)&=190,\!569,\!292\\p(1000)&=24,\!061,\!467,\!864,\!032,\!622,\!473,\!692,\!149,\!727,\!991\approx 2.40615\times 10^{31}\\p(10000)&=36,\!167,\!251,\!325,\!\dots ,\!906,\!916,\!435,\!144\approx 3.61673\times 10^{106}\end{aligned}}}$$

The generating function for p(n) is given by $${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)x^{n}&=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right)\\&=\left(1+x+x^{2}+\cdots \right)\left(1+x^{2}+x^{4}+\cdots \right)\left(1+x^{3}+x^{6}+\cdots \right)\cdots \\&={\frac {1}{1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}-\cdots }}\\&=1{\Big /}\sum _{k=-\infty }^{\infty }(-1)^{k}x^{k(3k-1)/2}.\end{aligned}}}$$The equality between the products on the first and second lines of this formula is obtained by expanding each factor ${\displaystyle 1/(1-x^{k})}$ into the geometric series ${\displaystyle (1+x^{k}+x^{2k}+x^{3k}+\cdots ).}$ To see that the expanded product equals the sum on the first line, apply the distributive law to the product. This expands the product into a sum of monomials of the form ${\displaystyle x^{a_{1}}x^{2a_{2}}x^{3a_{3}}\cdots }$ for some sequence of coefficients ${\displaystyle a_{i}}$, only finitely many of which can be non-zero. The exponent of the term is ${\textstyle n=\sum ia_{i}}$, and this sum can be interpreted as a representation of ${\displaystyle n}$ as a partition into ${\displaystyle a_{i}}$ copies of each number ${\displaystyle i}$. Therefore, the number of terms of the product that have exponent ${\displaystyle n}$ is exactly ${\displaystyle p(n)}$, the same as the coefficient of ${\displaystyle x^{n}}$ in the sum on the left. Therefore, the sum equals the product.