Skip to main content
1 of 2
Brian Hopkins
  • 4.6k
  • 32
  • 45

This is a postscript to Carlo Beenakker's answer, a combinatorial explanation for the relationship between $a_n$ and $c_n$.

Your $F(z)=\sum_n c_nz^n$ is the generating function for the number of partitions of $n$ into odd parts 3 or greater where there are two kinds of each part. Carlo's $G(z) = \sum_n a_nz^n$ allows two kinds of 1's also, matching one of the descriptions given for A022567.

Rewrite the equation in Carlo's comment as $a_n = c_n + 2a_{n-1} - a_{n-2}$. To see this, condition the partitions counted by $a_n$ by whether they contain (either kind of) 1 as a part. Those with no 1's are given by your $c_n$. To build these partitions of $n$ with 1's from smaller partitions, take the partitions of $n-1$ counted by $a_{n-1}$ and include a $1_1$. Repeat and include a $1_2$ to complete the $2a_{n-1}$ term. Some partitions of $n$ arise twice, though, precisely those that include both a $1_1$ and a $1_2$; the number of those is $a_{n-2}$ by adding $1_1$ and $1_2$ to the partitions of $n-2$. So $a_n = c_n + (2a_{n-1}-a_{n-2})$.

Brian Hopkins
  • 4.6k
  • 32
  • 45