Partition function (number theory)
Partition function in 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. The partition function is easy to calculate. One way of doing so 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). If the reason for this is not immediately apparent, 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). Can anyone explain to us why?
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 will mess with one's mind if one lets it. Consider the following:
- p(1,4)=5
- p(2,8)=7
- p(3,12)=9
- p(4,16)=11
- p(5,20)=13
- p(6,24)=16