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

Intermediate function

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:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• smallest addend is k
• smallest addend is strictly greater 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 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:

Related Topics:
Mutually exclusive - Recursive

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• 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).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The values of this function:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:{|border=1 cellspacing=1 cellpadding=2

~ ~ ~ ~ ~ ~ ~ ~ ~ ~