0

Let $p_n$ be the number of partitions of n into size either 1 or 2, and by definition take $p_0=1$. For example, one such partition of 5 is $5=2+2+1$. I have been given that the generating function for $p_n$ is

$P(x)=\sum_{n\ge0} p_nx^n=\frac{1}{1-x-x^2-x^3}$

and from that have found the following recurrence relation for $p_n$:

$p_{n+3}=p_{n+2}+p_{n+1}-p_{n}$

My question is how do I come up with a combinatorial explanation for the above recurrence relation?

My first thought was to consider whether the "last" term in the sum was either a one or a two. If the last term is a 1, then we have $p_{n+2}$ partitions for the remaining contribution of n+2. If the last term is 2, then we have $p_{n+1}$ partitions for the remaining contribution of n+1. Of course, this doesn't explain why we subtract off a $p_n$ term. We must be double counting $p_n$ somehow, but I am unsure as to why. We are also considering partitions of n rather than compositions where order doesn't matter, so there isn't really a "last" term.

If anyone can provide some explanation/hints as to justify this recurrence relation combinatorically I would greatly appreciate it!

RobPratt
  • 45,619
nak17
  • 359
  • 1
  • 9

1 Answers1

1

For a combinatorial explanation, you want to move the subtracted term to the other side. Let $P_n$ be the partitions of $n$ with parts from $\{1, 2\}$. We show $P_{n+3} \cup P_n \cong P_{n+2} \cup P_{n+1}$.

Given a partition in $P_{n+3}$, remove the smallest part. Given a partition in $P_n$, add a part 1. For the reverse direction, given a partition in $P_{n+2}$, add a part 1. Given a partition in $P_{n+1}$, if the smallest part is 1, then remove it; if the smallest part is 2, then add another 2.

To show that this is a bijection, one has to consider the parity of $n$. If $n$ is odd, then $n+3$ is even and $P_{n+3}$ includes a partition of all 2s. That partition is sent to the all-2s partition of $n+1$ which, in the reverse map, gets sent back to the all-2s partition of $n+3$. If $n$ is even, the smallest part of a partition in $P_{n+3}$ is 1, same for $P_{n+1}$.

However, the easiest way to see that $p_{n+3} = p_{n+2} + p_{n+1} - p_n$ is to develop a formula for $p_n$. A partition in $P_n$ is determined by its number of 2s, and there can be from 0 to $\lfloor n/2 \rfloor$ parts 2 (that's the integer floor function). Therefore $p_n = \lfloor n/2 \rfloor + 1$ and it's straightforward to verify that $p_{n+3} = p_{n+2} + p_{n+1} - p_n$.

Brian Hopkins
  • 2,257