Partition (number Theory) - Partition Function

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 ways of representing n as a sum of natural numbers (with order irrelevant). By convention p(0) = 1, p(n) = 0 for n negative.

The first few values of the partition function are (starting with p(0)=1):

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, … (sequence A000041 in OEIS).

The value of p(n) has been computed for large values of n, for example p(100)=190,569,292 and p(1000) is approximately 2.4×1031.

As of June 2012, the largest known prime number that counts a number of partitions is p(82352631), with 10101 decimal digits.

For every type of restricted partition there is a corresponding function for the number of partitions satisfying the given restriction. An important example is q(n), the number of partitions of n into distinct parts. As noted above, q(n) is also the number of partitions of n into odd parts. The first few values of q(n) are (starting with q(0)=1):

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, … (sequence A000009 in OEIS).