Back to July Calendar

September21, 2005

So much for summer, huh?

Back to partitions.  It's been hard to find good info on this topic.  PlanetMath has some interesting stuff visualizing partitions with Young and Ferrers diagrams--sort of n-ominoes.  This looks like a good way to get back to the theme of my sabbatical study...but first I need to understand the theory of partitions more better.  http://www.reference.com/browse/wiki/Integer_partition

Scratching too hard at this partition thing will lead you to people like James Sellers, who archives his numerous very erudite articles on the topic: all of which are beyond my level at this point, it seems. So I retreat to http://www.reference.com/browse/wiki/Integer_partition .

Remember the recursive function asserted by, but not justified by Dr. Math (he has a master's degree....in math!) a few days ago?

P(n,k) = P(n–1, k–1) + P(n–k, k)

Well, the reference.com/wiki site is introduces something a little different they call the "intermediate function:"

F(n, k) = the number of partitions of n using only natural numbers at least as large as k.

For example, F(9,3) = 4 since the partitions of 9: 3³,3-6,4-5,9 are the only ones involving no integers less than 3.  Note that the superscript is not an exponent in the usual sense, but, in the standard notation for partitions, 3³ simply indicate three 3's.

For a given k, partitions counted by F(n, k) fit into one two categories:

1. the smallest addend = k
2. the smallest addend > k

For our example, two partitionsof 9; that is, 3³ and 3-6, have 3 as the smallest integer and two (4-5,9) have the smallest integer greater than 3. 

The number of partitions meeting the first condition is F(n − k, 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?

In our example, we have 2 partitions with minimal addend 3.  Now consider the partitions comprising F(3,6), which are 3² and 6.  Appending 3 to each of these gives the two partitions of 9 with 3 as the minimal element.

Obviously, the number of partitions meeting the second condition is F(n, k + 1) and, since the two conditions are mutually exclusive, the number of partitions meeting either condition is given by the recursive relation:

F(n,k) = F(n, k + 1) + F(n − k, k). 

The base cases of this recursive function are as follows:

• F(n, k) = 0 if k > n
• F(n, k) = 1 if k = n

It's helpful to list out a few, to get a feeling for how some patterns vary with the parameters:

F(4, 1) = 5 : {4, 3-1, 2², 2-1², 1⁴}

F(8, 2) = 7 : {8, 6-2, 5-3, 4², 4-2², 3²-2, 2⁴}

F(12, 3) = 9 : {12, 9-3, 8-4, 7-5, 6², 6-3², 5-4-3, 4³, 3⁴}

F(16, 4) = 11 :  (16, 12-4, 11-5, 10-6, 9-7, 8², 8-4², 7-5-4, 6²-4, 6-5², 4⁴)

F(20, 5) = 13 :  (20, 15-5, 14-6, 13-7, 12-8, 11-9, 10², 10-5², 9-6-5, 8-7-5, 8-6², 7²-6, 5³)

F(24, 6) = 16 :  (24, 18-6, 17-7, 16-8, 15-9, 14-10, 13-11, 12², 12-6², 11-7-6, 10-8-6, 10-7², 9²-6, 9-8-7, 8³, 6⁴)

The simple partition function p(n) is just F(n, 1).

http://www.maths.ex.ac.uk/~mwatkins/zeta/partitioning.htm has some interesting connections with physics...also relevant links are