If $P(n, k)$ is the number of partitions of $n$ elements into $k$ sets, then $P(n, k) = kP(n-1, k) + P(n-1, k-1)$

Question

A partition of the set $\{1, 2, \dots , n\}$ into $k$ parts is a way of writing the set as a disjoint union of k subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup \{2, 3\} \cup \{5\}$ is a partition into 3 parts.

Let $P(n, k)$ be the number of partitions of $\{1, 2, …, n\}$ into $k$ parts. Prove the following: $$P(n, k) = kP(n – 1, k) + P(n - 1, k - 1)$$

Answer 1

Every partition counted in $p(n,k)$ is one of the following two forms.

• One of the subsets in the partition is $\{n\}$. There are $p(n-1,k-1)$ of these, since all you need to count is the number of ways to partition the remaining elements $1,\ldots, n-1$ into $k-1$ subsets.
• $\{n\}$ is not one of the subsets. Then, you need to count the number of ways of partitioning $1,\ldots, n-1$ into $k$ subsets (this is $p(n-1,k)$) and multiply it by $k$ since you need to add $n$ into one of the $k$ subsets.