Partition function
The partition function described here is part of number theory. The present author has absolutely 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 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