Partition function (number theory)

The partition function p(n) is a non-multiplicative function and 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. By convention p(0) = 1, p(n) = 0 for n negative.

One way of getting a handle on the partition function involves an intermediate function p(k,n) which represents the number of partitions of n using only natural numbers at least as large as k. For any given value of k, partitions counted by p(k,n) fit into exactly one of the following categories:

1. smallest addend is k

2. smallest addend is strictly greater than than k

The number of partitions meeting the first condition is p(k,n-k). To see this, imagine a list of all the partitions of the number n-k into numbers of size at least k, then imagine appending "+k" to each partition in the list. Now what is it a list of?

The number of partitions meeting the second condition is p(k+1,n) since a partition into parts of at least k which contains no parts of at exactly k must have all parts at least k+1.

Since the two conditions are mutually exclusive, the number of partitions meeting either condition is p(k+1,n)+p(k,n-k). The base cases of this recursive function are as follows:

p(k,n) = 0 if k > n
p(k,n) = 1 if k = n

This function tends to exhibit deceptive behavior.

p(1,4) = 5

p(2,8) = 7

p(3,12) = 9

p(4,16) = 11

p(5,20) = 13

p(6,24) = 16

Our original function p(n) is just p(1,n).

An alternative computation of the partition function involves generating functions. Consider the infinite product

Expanding each term as a geometric series, we can rewrite it as

(1 + x + x² + x³ + ...)(1 + x² + x⁴ + x⁶ + ...)(1 + x³ + x⁶ + x⁹ + ...) ...

The x^m term in this product counts the number of ways to write

n = a₁ + 2a₂ + 3a₃ + ... = (1 + 1 + 1 + 1 + ...) + (2 + 2 + 2 + 2 + ...) + (3 + 3 + 3 ...) + ...,

where each number i appears a_i 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 the generating function is similar to the product formulation of many modular forms, giving some idea of the connection between the two. It can also be used in conjunction with the pentagonal number theorem to derive a recurrence for the partition function stating that

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 +, +, -, -, +, +, ...

Some values of the partition function are as follows:

p(1) = 1
p(2) = 2
p(3) = 3
p(4) = 5
p(5) = 7
p(6) = 11
p(7) = 15
p(8) = 22
p(9) = 30
p(10) = 42
p(100) = 190569292
p(1000) = 24061467864032622473692149727991
p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144

External Links

Partition and composition calculator