0

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.

1 Answers1

0

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.

Brian M. Scott
  • 616,228
  • How does $P_0(n,k)$ and $P_1(n,k)$ relate to $g(n-2,k-1)$ and $g(n-k,k)$? –  Aug 16 '16 at 19:46
  • 1
    @MathMuse: $g(n-2,k-1)$ is the cardinality of one of those two sets, and $g(n-k,k)$ is the cardinality of the other. Here’s an additional hint: if you take a partition in $P_0(n,k)$ and subtract $1$ from each part, you get a partition in $P(n-k,k)$. – Brian M. Scott Aug 16 '16 at 19:59
  • Wait, how is that correct? Could you explain it to me? And how does $P_1(n,k)$ have the same amount as $P(n-1,k-1)$? –  Aug 16 '16 at 20:12
  • 1
    @MathMuse: $P_1(n,k)$ is the same size as $P(n-\color{red}{2},k-1)$: if a partition is in $P_1(n,k)$, it has a $2$ part, and when you throw away that $2$ part, what’s left is a partition of $n-2$ into $k-1$ parts, none of which is a $1$. – Brian M. Scott Aug 16 '16 at 20:17
  • Okay, I get it. But what about $P_0(n,k)$ and $P(n-k,k)$? How does "if you take a partition in $P_0(n,k)$ and subtract 1 from each part, you get a partition in $P(n−k,k)$" work? –  Aug 16 '16 at 20:21
  • @MathMuse: Have you been introduced to Ferrers diagrams of partitions? – Brian M. Scott Aug 16 '16 at 20:24
  • No. Could that proof be complete without Ferrers diagrams? –  Aug 16 '16 at 20:25
  • 1
    @MathMuse: Sure; the diagrams just make it very easy to understand what’s going on. Consider the partition $5+5+4+3$ of $17$; it’s in $P_0(17,4)$. If you subtract $1$ from each part, you get $4+4+3+2$, which is in $P(17-4,4)=P(13,4)$. Can you see why something like this will always happen? The original partition of $17$ has no $1$ parts, so subtracting $1$ from each part still leaves $4$ parts, and it also has no $2$ parts, so the reduced partition has no $1$ parts. – Brian M. Scott Aug 16 '16 at 20:30
  • Okay, I see it now! Thanks for responding to my ongoing questions and taking the time to explain the answers! Answer accepted and +1! –  Aug 16 '16 at 20:34
  • @MathMuse: You’re welcome! – Brian M. Scott Aug 16 '16 at 20:35
  • Let us continue this discussion in chat. –  Aug 16 '16 at 20:55
  • @MathMuse: I may have to leave before too long, but I’m there now. – Brian M. Scott Aug 16 '16 at 21:02