Prove Partition Recurrence Relation

Question

I read in a snippet of a paper by G.E. Andrews that Euler discovered the partition identity,

$D(m, n) = D(m, n − m) + D(m − 1, n − m).$

where $D(m, n)$ is the number of ways to partition n into m parts. Using more conventional notation, I suppose it could be rewritten as,

$P(n, k) = P(n-k, k) + P(n-k, k-1).$

Is there a way to prove this using a combinatorial argument? A very common one I see is $P(n, k) = P(n-1, k-1) + P(n-k, k)$, and I understand why that identity is true, but I can't wrap my head around this one. My intuition is that the RHS describes splitting up P(n, k) into cases where there's at least 1 partition of size k and where there's no partitions of size k, but I'm not sure if that's correct.

Thanks!

Answer 1

These are recurrence relations for different problems. You could not simultaneously have $$P(n,k) = P(n-1,k-1) + P(n-k, k)$$ (your second identity) and $$P(n,k) = P(n-k,k-1) + P(n-k, k)$$ (the identity Euler discovered) because that would imply $P(n-1,k-1) = P(n-k,k-1)$.

I suspect that Euler's identity is for the problem of partitioning $n$ into distinct parts. If we define $D(n,k)$ to be the number of ways to partition $n$ into $k$ parts all of different sizes, allowing $10 = 5+3+2$ but not $10 = 4+3+3$, then we have the recursion $$D(n,k) = D(n-k,k-1) + D(n-k,k).$$ The argument is by the following two cases:

• If all parts have size $2$ or more, decrease each part by $1$ (e.g., turning $10=5+3+2$ into $7=4+2+1$). There are still $k$ parts, and now their total size is $n-k$, so there are $D(n-k,k)$ partitions of this type.
• If there is a part of size $1$ (there can be only one), do the same thing, but remove the empty part we get (e.g., turning $10 = 6+3+1$ into $7=5+2$). There are now $k-1$ parts, and their total size is $n-k$, so there are $D(n-k,k-1)$ partitions of this type.