Partition (number theory)

Question

Please someone explain the reasoning behind the recurrence relation p[k][n] = p[k][n − k] + p[k − 1][n − 1], where

p[k][n] denotes the number of partitions of n into exactly k parts.

For details, refer to https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Restricted_part_size_or_number_of_parts

Answer 1

Let $p_k(n)$ be the number of partitions of $n$ into exactly $k$ parts. We say such a partition is of Type A if every part is $\ge 2$, and that it is of Type B if at least one of the parts is $1$.

Then $p_k(n)$ is the number of Type A partitions of $n$ into $k$ parts plus the number of Type B partitions of $n$ into $k$ parts.

Any Type A partition is obtained by adding $1$ to each member of a partition of $n-k$ into exactly $k$ parts. There are $p_{k}(n-k)$ such partitions.

Any Type B partition is obtained by taking a partition of $n-1$ into $k-1$ parts and appending a $1$. There are $p_{k-1}(n-1)$ such partitions.

It follows that $p_k(n)=p_k(n-k)+p_{k-1}(n-1)$.