PlanetMath: partition function

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

partition function

(Definition)

The partition function is defined to be the number of partitions of the integer . 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.

Theorem 1 As $n \rightarrow \infty$ , the ratio of and

$\displaystyle \frac{ e^{\pi \sqrt{ 2n/3} } } {4n \sqrt{3} }$

approaches 1.

The generating function of is called : by definition

$\displaystyle F(x) = \sum _{n=0} ^\infty p(n) x ^n.$

can be written as an infinite product:

$\displaystyle F(x) = \prod _{i=1} ^\infty (1-x^i) ^{-1}.$

To see this, expand each term in the product as a power series:

$\displaystyle \prod _{i=1} ^\infty (1+ x^i + x^{2i} + x^{3i} + \cdots ).$

Now expand this as a power series. Given a partition of

with

parts of size $i \geq 1$ , we get a term

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

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