|
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),\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.
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: $$ \label{product} \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}. $$
- 1
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 2003.
|
