Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Counting > Objects In Boxes > Partition Recurrence Relation

Jay asked me to explain the relation,

part(n,k) = part(n-1,k-1) + part(n-k,k),

where part(n,k) is defined as the number of k-element partitions of n.  So, Jay wants to know why the number of k-element partitions of n is equal to the number of k-1-element partitions of n-1 plus the number of k-element partitions of n-k.

First, I want to make sure you understand what I mean by a k-element partition of n? It's the number of ways to add up two numbers to equal n, where order of the addends isn't important.

For example, the 2-element partitions of 7 are 1+6, 2+5, and 3+4. 4+3 isn't different from 3+4, so it doesn't count as another 2-element partition of 7.

Now, I'm dividing the k-element partitions of n into two groups:

Group A: partitions with a "1" in them, i.e. 1+something
Group B: partitions without a "1" in them.

The number of k-element partitions in group A are the number of ways to make "something" in 1+something, which is the number of k-1 element partitions of n-1.

Notice that you can subtract 1 from each part of the partitions in group B. For example, one of the 4-element partitions of 19 that is in group B is 2+3+5+9. You can subtract 1 from each of these parts to get 1+2+4+8, which is one of the 4-element partitions of 15 (which is 19-4). So, for every k-element partition of n in group B you can find a k-element partition of n-k.

So the number of elements in group A is part(n-1,k-1), and the number of elements in group B is part(n-k,k).

Thus, part(n,k) = part(n-1,k-1) + part(n-k,k)

Internet references

Partitioning Integers, from Bob's Positive Integer Pages (fascinating reading!)

Sloan's A000041: the number of partitions of n.
Sloan's A008284: part(n,k), the number of partitions of n into exactly k parts, and also (by conjugate partitions) the number of partitions of n whose largest part is k.

Related pages in this website

Partitions - the number of ways to express n as a sum of positive integers, where the order of the addends doesn't matter.

"hyper-binary" partition

Combination identities

 

The webmaster and author of this Math Help site is Graeme McRae.