partition function

The partition function $p(n)$ is defined to be the number of partitions of the integer $n$. The sequence of values $p(0),p(1),p(2),\mathrm{\dots }$ is Sloane’s A000041 and begins $1,1,2,3,5,7,11,15,22,30,\mathrm{\dots }$. This function grows very quickly, as we see in the following theorem due to Hardy and Ramanujan (http://planetmath.org/SrinivasaRamanujan).

Theorem 1

As $n\mathrm{\to }\mathrm{\infty }$, the ratio of $p\mathit{}\mathrm{(}n\mathrm{)}$ and

$$\frac{e^{\pi \sqrt{2n/3}}}{4n\sqrt{3}}$$

approaches 1.

The generating function of $p(n)$ is called $F$: by definition

$$F(x)=\sum _{n=0}^{\mathrm{\infty }}p(n)x^n.$$

$F$ can be written as an infinite product:

$$F(x)=\prod _{i=1}^{\mathrm{\infty }}{(1-x^i)}^{-1}.$$

To see this, expand each term in the product as a power series:

$$\prod _{i=1}^{\mathrm{\infty }}(1+x^i+x^{2i}+x^{3i}+\mathrm{\cdots }).$$

Now expand this as a power series. Given a partition of $n$ with $a_i$ parts of size $i\ge 1$, we get a term $x^n$ in this expansion by choosing $x^{a_1}$ from the first term in the product, $x^{2a_2}$ from the second, $x^{3a_3}$ from the third and so on. Clearly any term $x^n$ in the expansion arises in this way from a partition of $n$.

One can prove in the same way that the generating function $F_m$ for the number $p_m(n)$ of partitions of $n$ into at most $m$ parts (or equivalently into parts of size at most $m$) is

$$F_m(x)=\prod _{i=1}^m{(1-x^i)}^{-1}.$$