Partitions

Given a natural number n, in how many ways p(n)can n be written as a sum of natural numbers, not counting the order of summation? For n=4, all the possibilities are listed below

$$\begin{eqnarray*}4 &=& 1+1+1+1 \\ &=& 1+1+2 \\ &=& 1+3 \\ &=& 2+2 \\ &=& 4 \\ \end{eqnarray*}$$

Thus, p(4)=5. As n becomes larger, the number of partitions of n grows very rapidly. For example:

$$\begin{eqnarray*}9&=&1+1+1+1+1+1+1+1+1\\ &=&1+1+1+1+1+1+1+2\\ &=&1+1+1+1+1+1... ...&2+3+4\\ &=&2+7\\ &=&3+3+3\\ &=&3+6\\ &=&4+5\\ &=&9\\ \end{eqnarray*}$$

Therefore, p(9)=30. To study the partition function, we introduce the generating function:

$$\phi(T) = 1+ \sum_{n=1}^\infty p(n) T^n.$$

Once again, this Taylor expansion contains all the information we desire about the partition function. As in the case of the Fibonacci numbers, the main problem is to find another way of identifying $\phi(T)$. A remarkable identity can be proved:

$$\phi(T) = \prod_{n=1}^\infty (1-T^n)^{-1}.$$

On the right side, we have an infinite product expansion. This is defined in the same way as an infinite series using multiplication instead of addition. Here, we will only sketch how such an identity is proved. First of all, any partition of n may be written

$$n = \overbrace{1+\cdots +1}^{m_1 \;{\rm times}}+ \overbrace{... ... times}}+ \overbrace{3+\cdots +3}^{m_3 \;{\rm times}}+ \cdots$$

The notation means a sum of m₁ 1's added to a sum of m₂ 2's added to a sum of m₃ 3's, etc. We have taken pains to write the partition so that the summands are listed in increasing order. By the geometric series expansion

$$\begin{eqnarray*}(1-T^n)^{-1} &=& \sum_{m=0}^\infty (T^n)^m\\ &=& \sum_{m=0}^\infty T^{\overbrace{n+\cdots +n}^{m \;{\rm times}}}\\ \end{eqnarray*}$$

Thus, when we take the product of these terms over all n, we write down the following

$$\sum_{m_1=0}^\infty T^{\overbrace{1+\cdots +1}^{m_1 \;{\rm ti... ... T^{\overbrace{3+\cdots +3}^{m_3 \;{\rm times}}} \times \cdots$$

We multiply out this product by choosing one term in each expansion and multiplying these together. Thus, we obtain one term Tⁿ for precisely each possible partition of n. This explains the identity for the partition function's generating series. This identity is the first step in analyzing the partition function. Using more advanced techniques, Rademacher, Hardy and Ramanujan proved the following limit

$$\lim_{n\to \infty} {p(n)\over \left({\exp\left(\pi\sqrt{ 2n\over3}\right)\over 4\sqrt{3} n}\right)} =1$$

In fact, they obtained a refinement of this limit that is so precise that for any large n it is possible to easily calculate the value of p(n) without actually listing all the partitions. This kind of theorem belongs to the subject of Analytic Number Theory.