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?
Best Answer
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:
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)$$