** Next:** Multiplicative Number Theory and
** Up:** Generating Series
** Previous:** Fibonacci Numbers

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

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

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

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 .
A
remarkable identity can be proved:

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

The notation means a sum of *m*_{1} 1's added to a sum of *m*_{2} 2's
added to a sum of *m*_{3} 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

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

We multiply out this product by choosing one term in each expansion and
multiplying these together. Thus, we obtain one term *T*^{n} 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

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.

** Next:** Multiplicative Number Theory and
** Up:** Generating Series
** Previous:** Fibonacci Numbers
*David J. Wright*

*2000-08-24*