| Version current |
Version 5 |
|
The {\sl 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 \PMlinkname{Ramanujan}{SrinivasaRamanujan}.
|
The {\sl 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.
|
|
|
| \begin{thm} |
\begin{thm} |
| As $n \rightarrow \infty$, the ratio of $p(n)$ and |
As $n \rightarrow \infty$, the ratio of $p(n)$ and |
| \[ \frac{ e^{\pi \sqrt{ 2n/3} } } {4n \sqrt{3} } \] |
\[ \frac{ e^{\pi \sqrt{ 2n/3} } } {4n \sqrt{3} } \] |
| approaches 1. |
approaches 1. |
| \end{thm} |
\end{thm} |
|
|
|
|
| The generating function of $p(n)$ is called $F$: by definition |
The generating function of $p(n)$ is called $F$: by definition |
|
|
| \[ F(x) = \sum _{n=0} ^\infty p(n) x ^n. \] |
\[ F(x) = \sum _{n=0} ^\infty p(n) x ^n. \] |
|
|
| $F$ can be written as an infinite product: |
$F$ can be written as an infinite product: |
|
|
| \[ F(x) = \prod _{i=1} ^\infty (1-x^i) ^{-1}. \] |
\[ F(x) = \prod _{i=1} ^\infty (1-x^i) ^{-1}. \] |
| To see this, expand each term in the product as a power series: |
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 ). \] |
\[ \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$. |
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 |
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}. \] |
\[ F_m(x) = \prod _{i=1} ^m (1-x^i) ^{-1}. \] |
|
|
| \begin{thebibliography}{5} |
\begin{thebibliography}{5} |
| \bibitem{HandW} G. H. Hardy and E. M. Wright, {\em An Introduction to the Theory of Numbers}, Oxford University Press, 2003. |
\bibitem{HandW} G. H. Hardy and E. M. Wright, {\em An Introduction to the Theory of Numbers}, Oxford University Press, 2003. |
|
|
|
|
|
|
| \end{thebibliography} |
\end{thebibliography} |
