partition function

A partition function $p (n)$ counts the number of integer partitions of $n$ .

It has generating function

\sum_{n \geq 0} p (n) x^{n} = \prod_{i \geq 1} \frac{1}{1 - x^{i}}

and satisfies the recurrence relation (Euler's pentagonal number theorem):

p (n) = \sum_{k = \pm 1, \pm 2, \dots} (- 1)^{k - 1} p (n - \frac{k (3 k - 1)}{2})

for $n \geq 1$ . (note it is $0$ for $n < 0$ and $p (0) = 1$ ). Equivalently,

{(\sum_{n \geq 0} p (n) x^{n})}^{- 1} = \prod_{i \geq 1} (1 - x^{i}) = \sum_{k \in Z} (- 1)^{k} x^{k (3 k - 1) / 2}

Note that $\frac{k (3 k - 1)}{2}$ are the pentagonal numbers

Variants

The generating function for partitions with distinct parts is given by

\sum_{n \geq 0} p_{d i s t} (n) x^{n} = \prod_{i = 1}^{\infty} (1 + x^{i})

Here are the first couple values: