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)
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.
Partitions - the number of ways to express n as a sum of positive integers, where the order of the addends doesn't matter.
The webmaster and author of this Math Help site is Graeme McRae.