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.