# partition function

The $p(n)$ is defined to be the number of partitions of the integer $n$. The sequence of values $p(0),p(1),p(2),\ldots$ is Sloane’s A000041 and begins $1,1,2,3,5,7,11,15,22,30,\ldots$. 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\rightarrow\infty$, the ratio of $p(n)$ 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}^{\infty}p(n)x^{n}.$

$F$ can be written as an infinite product:

 $F(x)=\prod_{i=1}^{\infty}(1-x^{i})^{-1}.$

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

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

Now expand this as a power series. Given a partition of $n$ with $a_{i}$ parts of size $i\geq 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}.$

## References

• 1 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 2003.
Title partition function PartitionFunction 2013-03-22 15:57:55 2013-03-22 15:57:55 silverfish (6603) silverfish (6603) 9 silverfish (6603) Definition msc 05A17 IntegerPartition NonMultiplicativeFunction partition generating function