PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
partition function (Definition)

The partition function $ p(n)$ is defined to be the number of partitions of the integer $ n$. 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 $ p(n)$ and
$\displaystyle \frac{ e^{\pi \sqrt{ 2n/3} } } {4n \sqrt{3} } $
approaches 1.

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

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

$ F$ 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 $ n$ with $ a_i$ parts of size $ i \geq 1$, we get a term $ x^n$ 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 $ x^n$ in the expansion arises in this way from a partition of $ n$.

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

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

Bibliography

1
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 2003.



Anyone with an account can edit this entry. Please help improve it!

"partition function" is owned by silverfish. [ full author list (3) ]
(view preamble)

View style:

See Also: integer partition, non-multiplicative function

Also defines:  partition generating function
Log in to rate this entry.
(view current ratings)

Cross-references: size, power series, term, expand, product, infinite, generating function, ratio, function, sequence, integer, partitions, number
There are 4 references to this entry.

This is version 6 of partition function, born on 2006-06-09, modified 2006-09-30.
Object id is 7980, canonical name is PartitionFunction2.
Accessed 2282 times total.

Classification:
AMS MSC05A17 (Combinatorics :: Enumerative combinatorics :: Partitions of integers)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)