partition function


The partition functionPlanetmathPlanetmath p(n) is defined to be the number of partitionsMathworldPlanetmathPlanetmath of the integer n. The sequenceMathworldPlanetmath of values p(0),p(1),p(2), is Sloane’s A000041 and begins 1,1,2,3,5,7,11,15,22,30,. This function grows very quickly, as we see in the following theorem due to Hardy and Ramanujan (http://planetmath.org/SrinivasaRamanujan).

Theorem 1

As n, the ratio of p(n) and

eπ2n/34n3

approaches 1.

The generating function of p(n) is called F: by definition

F(x)=n=0p(n)xn.

F can be written as an infinite product:

F(x)=i=1(1-xi)-1.

To see this, expand each term in the productPlanetmathPlanetmath as a power seriesMathworldPlanetmath:

i=1(1+xi+x2i+x3i+).

Now expand this as a power series. Given a partition of n with ai parts of size i1, we get a term xn in this expansion by choosing xa1 from the first term in the product, x2a2 from the second, x3a3 from the third and so on. Clearly any term xn in the expansion arises in this way from a partition of n.

One can prove in the same way that the generating function Fm for the number pm(n) of partitions of n into at most m parts (or equivalently into parts of size at most m) is

Fm(x)=i=1m(1-xi)-1.

References

  • 1 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 2003.
Title partition function
Canonical name PartitionFunction
Date of creation 2013-03-22 15:57:55
Last modified on 2013-03-22 15:57:55
Owner silverfish (6603)
Last modified by silverfish (6603)
Numerical id 9
Author silverfish (6603)
Entry type Definition
Classification msc 05A17
Related topic IntegerPartition
Related topic NonMultiplicativeFunction
Defines partition generating function