# partition function

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),\mathrm{\dots}$ is Sloane’s A000041 and begins $1,1,2,3,5,7,11,15,22,30,\mathrm{\dots}$. 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\mathrm{\to}\mathrm{\infty}$, the ratio of $p\mathit{}\mathrm{(}n\mathrm{)}$ and

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

approaches 1.

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

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

$F$ can be written as an infinite product:

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

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

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

Now expand this as a power series. Given a partition of $n$ with ${a}_{i}$ parts of size $i\ge 1$, we get a term ${x}^{n}$ in this expansion by choosing ${x}^{{a}_{1}}$ from the first term in the product, ${x}^{2{a}_{2}}$ from the second, ${x}^{3{a}_{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

$${F}_{m}(x)=\prod _{i=1}^{m}{(1-{x}^{i})}^{-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 |