Partition function
The partition function described here is part of number theory. The present author has absotely no idea whether this is the same function referred to as a partition function in statistical mechanics or game 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. 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 case of this recursive function are as follows:
- p(k,n)=0 if k>n
- p(k,n)=1 if k=n
Actually p(k,n)=1 if 2k>n. Also, p(k,n)=floor(n/2)-k+2 if 3k>n>2k.