The partition function is defined to be the number of partitions of the integer . The sequence of values is Sloane’s A000041 and begins . This function grows very quickly, as we see in the following theorem due to Hardy and Ramanujan (http://planetmath.org/SrinivasaRamanujan).
As , the ratio of and
The generating function of is called : by definition
can be written as an infinite product:
Now expand this as a power series. Given a partition of with parts of size , we get a term in this expansion by choosing from the first term in the product, from the second, from the third and so on. Clearly any term in the expansion arises in this way from a partition of .
One can prove in the same way that the generating function for the number of partitions of into at most parts (or equivalently into parts of size at most ) is
- 1 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 2003.
|Date of creation||2013-03-22 15:57:55|
|Last modified on||2013-03-22 15:57:55|
|Last modified by||silverfish (6603)|
|Defines||partition generating function|