Partition Proof Using One-to-One Correspondences

Question

Let $g(n,k)$ be the number of partitions of $n$ into exactly $k$ parts, in which no part is a $1$. Show that $$g(n,k) = g(n-2,k-1) + g(n-k,k).$$

I know that the solution involves a one-to-one correspondence. I tried listing a few examples, but I didn't find anything.

Answer 1

HINT: Let $P(n,k)$ be the set of partitions of $n$ into exactly $k$ parts, none of which is a $1$. We can split $P(n,k)$ into two subsets:

• Let $P_0(n,k)$ be the set of partitions in $P(n,k)$ that do not have a part that is a $2$. In other words, $P_0(n,k)$ is the set of partitions of $n$ into $k$ parts, all of which are at least $3$.
• Let $P_1(n,k)$ be the set of partitions in $P(n,k)$ that do have a $2$ part.

Clearly $P_0(n,k)$ and $P_1(n,k)$ are disjoint, and $P_0(n,k)\cup P_1(n,k)=P(n,k)$, so

$$g(n,k)=|P_0(n,k)|+|P_1(n,k)|\;.$$

Now try to match up the cardinalities $|P_0(n,k)|$ and $|P_1(n,k)|$ with the two terms on the righthand side of the recurrence that you’re trying to prove.