no consecutive even parts

Question

A composition of $n$ is an ordered sequence $(a_1,\cdots, a_k)$ so that $\sum_{j=1}^k a_j = n$ and $a_j \in \mathbb{N}\,\forall j$. The $a_j$'s are parts of the composition. Let $c_j$ be the number of compositions of $j$ with no consecutive pairs of even parts. For instance, for $n=4$, the possible compositions would be $(1,1,1,1),(2,1,1),(1,2,1),(1,1,2),(1,3),(3,1),(4).$ Prove that $\sum_{j=0}^\infty c_jx^j = \dfrac{1-x^2}{1-x-2x^2+x^4}$.

I know that in order for there to be no consecutive pairs of even parts, each pair of even parts must be separated by one or more odd parts. Letting $E$ represent an even part and $O$ represent an odd part and $Q+$ represent $1$ or more occurrences of $Q$, and $R^*$ represent $0$ or more occurrences of $R$, each composition seems to be of the form $(EO+)^*$. I know the generating series for the odd natural numbers is $x(1-x^2)^{-1}$ and that of the even natural numbers is $x^2(1-x^2)^{-1}$. How can I determine the set on which the generating series is defined and define the weight function?

Answer 1

You could also start with $0$ or more $O$ or end with $E$: $$O^*(EO+)^*(\epsilon|E)$$

If $f(x)$ is the generating function for $A$, then three basic facts are:

1. The generating function for $A^*$ is $1/(1-f(x))$.
2. The generating function for $A+$ is $f(x)/(1-f(x))$.
3. The generating function for $\epsilon|A$ is $1+f(x)$.

By fact 1, $O^*$ yields generating function $$\frac{1}{1-x(1-x^2)^{-1}}$$

By facts 1 and 2, the generating function for $(EO+)^*$ is: $$\frac{1}{1-x^2(1-x^2)^{-1}\frac{x(1-x^2)^{-1}}{1-x(1-x^2)^{-1}}}$$

By fact 3, the generating function for $\epsilon|E$ is $1+x^2(1-x^2)^{-1}$.

Putting it all together by multiplication, the final generating function is: $$\frac{1}{1-x(1-x^2)^{-1}} \cdot \frac{1}{1-x^2(1-x^2)^{-1}\frac{x(1-x^2)^{-1}}{1-x(1-x^2)^{-1}}} \cdot \left(1+\frac{x^2}{1-x^2}\right)$$

Answer 2

I found it easier to start by finding a recurrence for the coefficients $c_n$. Let $C_n$ be the set of compositions of $n$ that do not have two consecutive even parts, so that $c_n=|C_n|$; clearly $c_1=1$, $c_2=2$, $c_3=4$, and $c_4=7$. Suppose that $n\ge 5$, and let $n=a_1+\ldots+a_m$ be a composition in $C_n$.

• If $a_m=1$, $a_1+\ldots+a_{m-1}$ is a composition of $n-1$ in $C_{n-1}$, and every composition in $C_{n-1}$ can be extended to a composition in $C_n$ that ends in $1$.
• If $a_m=2$, $a_1+\ldots+a_{m-1}$ is a composition of $n-2$ in $C_{n-2}$, and every composition in $C_{n-2}$ that ends in an odd number can be extended to a composition in $C_n$ that ends in $2$.
• If $a_m\ge 3$, $a_1+\ldots+a_{m-1}+(a_m-2)$ is a composition of $n-2$ in $C_{n-2}$.

Thus, $c_n$ is $c_{n-1}+2c_{n-2}$ minus the number of compositions in $C_{n-2}$ that end in an even number. If $b_1+\ldots+b_\ell$ is a composition in $C_{n-4}$, then either $b_\ell$ is odd, in which case $b_1+\ldots+b_\ell+2$ is a composition in $C_{n-2}$ that ends in $2$, or $b_\ell$ is even, in which case $b_1+\ldots+(b_\ell+2)$ is a composition in $C_{n-2}$ that ends in an even number greater than $2$. These two possibilities account for all of the compositions in $C_{n-2}$ that end in an even number, so there are $C_{n-4}$ such compositions. Thus, the recurrence is

$$c_n=c_{n-1}+2c_{n-2}-c_{n-4}\,.$$

From this you should be able to work backwards to the generating function.