Partition function (number theory)

In number theory, the partition function p(n) represents the number of possible partitions of a natural number n, which is to say the number of distinct (and order independent) ways of representing n as a sum of natural numbers. For example, 4 can be partitioned in 5 distinct ways

Generating function

A generating function for p(n) is given by the reciprocal of Euler's function:

Related Topics:
Generating function - Reciprocal - Euler's function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:sum_{n=0}^infty p(n)x^n = prod_{k=1}^infty left(rac {1}{1-x^k} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Expanding each term on the right-hand side as a geometric series, we can rewrite it as

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:(1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)(1 + x3 + x6 + x9 + ...) ...

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The xm term in this product counts the number of ways to write

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:n = a1 + 2a2 + 3a3 + ... = (1 + 1 + 1 + 1 + ...) + (2 + 2 + 2 + 2 + ...) + (3 + 3 + 3 ...) + ...,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where each number i appears ai times. This is precisely the definition of a partition of n, so our product is the desired generating function. More generally, the generating function for the partitions of n into numbers from a set A can be found by taking only those terms in the product where k is an element of A. This result is due to Euler.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The formulation of Euler's generating function is a special case of a q-series and is similar to the product formulation of many modular forms, and specifically the Dedekind eta function. It can also be used in conjunction with the pentagonal number theorem to derive a recurrence for the partition function stating that

Related Topics:
Q-series - Modular form - Dedekind eta function - Pentagonal number theorem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:p(k) − p(k − 1) − p(k − 2) + p(k − 5) + p(k − 7) − p(k − 12) − ... = 0,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where the sum is taken over all pentagonal numbers of the form ½n(3n − 1), including those where n < 0, and the terms continue to alternate +, +, −, −, +, +, ...

~ ~ ~ ~ ~ ~ ~ ~ ~ ~