Determine a Generating Series of a Composition

Question

Question: Let H be the set of compositions = $\{c_{1},c_{2},c_{3},....c_{k}\}$ of any length, in which each part $\{c_{b}\}$ is congruent to b (modulo 2). Determine a rational function formula for the generating series of the set H.

Solution Attempt:

It's obvious that the element in $\{c_{1},c_{3},....c_{2i+1}\}$ are odd, and that the elements in $\{c_{2},c_{4},....c_{2i}\}$ are even.

The generating series for a set where all elements are even is given by $\frac{x^2}{1-x^2}$, and the generating series for a set where all the elements are odd is given by $\frac{x}{1-x^2}$. The part where I'm stuck is determine how to combine these series for a composition of total length of $k$.

Answer 1

We show a generating function $A(x)$ for the number of compositions starting with an odd term and continuing with terms of alternating parity is \begin{align*} \color{blue}{A(x)}&\color{blue}{=\frac{x}{1-2x^2-x^3+x^4}}\\ &=x + 2 x^3 + x^4 + \color{blue}{3} x^5 + \color{blue}{4} x^6 + 5 x^7\\ &\qquad + 10 x^8 + 11 x^9 + 21 x^{10} + 27 x^{11} + \cdots\tag{1} \end{align*}

At first we look at small examples $n=5$ and $n=6$. We list the partitions $p$ of $n$ in the first column, give the number $c(p)$ of compositions of the partition $p$ in the second column and count the number $w(p)$ of wanted compositions in the third column.

\begin{align*} \begin{array}{lcc} p&c(p)&w(p)\\ \hline 5&\quad 1&\quad 1\\ 4+1&\quad 2&\quad 1\\ 3+2&\quad 2&\quad 1\\ 3+1+1&\quad 3&\quad 0\\ 2+2+1&\quad 3&\quad 0\\ 2+1+1+1&\quad 4&\quad 0\\ 1+1+1+1+1&\quad 1&\quad 0\\ \hline &2^4=16&\quad \color{blue}{3}\\ \\ p&c(p)&w(p)\\ \hline 6&1&0\\ 5+1&2&0\\ 4+2&2&0\\ 4+1+1&3&1\\ 3+3&1&0\\ 3+2+1&6&2\\ 3+1+1+1&4&0\\ 2+2+2&1&0\\ 2+2+1+1&6&1\\ 2+1+1+1+1&5&0\\ 1+1+1+1+1+1&1&0\\ \hline &2^5=32&\color{blue}{4} \end{array} \end{align*}

We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We observe from the tables above in accordance with (1) \begin{align*} [x^5]A(x)=\color{blue}{3}\qquad\qquad[x^6]A(x)=\color{blue}{4} \end{align*}

Odd terms: In order to build up the generating series $A(x)$ we split the valid compositions into two parts. The first part contains the odd terms with generating function $O(x;s)$ \begin{align*} \color{blue}{O(x;s)}&=\sum_{q=1}^\infty\left(x+x^3+x^5+\cdots\right)^qs^q\\ &=\sum_{q=1}^{\infty}\left(\frac{xs}{1-x^2}\right)^q\\ &\,\,\color{blue}{=\frac{xs}{1-sx-x^2}} \end{align*}

We use a variable $s$ as marker for the number of odd terms a valid composition contains. A valid composition of the number $n$ containing precisely $k$ odd terms is consequently \begin{align*} [x^ns^k]O(x;s)&=[x^ns^k]\sum_{q=1}^{\infty}\left(\frac{xs}{1-x^2}\right)^q\\ &=[x^n]\left(\frac{x}{1-x^2}\right)^k \end{align*}

Even terms: The second part contains the even terms with generating function $E(x;t)$ \begin{align*} \color{blue}{E(x;t)}&=\sum_{q=1}^\infty\left(x^2+x^4+x^6+\cdots\right)^qt^q\\ &=\sum_{q=1}^{\infty}\left(\frac{x^2t}{1-x^2}\right)^q\\ &\,\,\color{blue}{=\frac{x^2t}{1-x^2(1+t)}} \end{align*}

We use a variable $t$ as marker for the number of even terms a valid composition contains. A valid composition of the number $n$ containing precisely $k$ even terms is consequently \begin{align*} [x^nt^k]E(x;t)&=[x^nt^k]\sum_{q=1}^{\infty}\left(\frac{x^2t}{1-x^2}\right)^q\\ &=[x^n]\left(\frac{x^2}{1-x^2}\right)^k \end{align*}

Valid compositions consist of either an even number $2k$ of terms, which means $k$ odd numbers and $k$ even numbers starting with an odd number and ending with an even number or they consist of an odd number $2k+1$ of terms, which means $k+1$ odd numbers and $k$ even numbers starting and ending with an odd number.

$2k$ terms: \begin{align*} \color{blue}{\sum_{k=1}^\infty}&\color{blue}{[s^kt^k]\left(O(x)E(x)\right)}\\ &=\sum_{k=1}^\infty\left(\frac{x}{1-x^2}\right)^k\left(\frac{x^2}{1-x^2}\right)^k\\ &=\sum_{k=1}^\infty\frac{x^{3k}}{\left(1-x^2\right)^{2k}}\\ &=\frac{\frac{x^3}{\left(1-x^2\right)^2}}{1-\frac{x^3}{\left(1-x^2\right)^2}}\\ &\,\,\color{blue}{=\frac{x^3}{1-2x^2-x^3+x^4}}\tag{2} \end{align*} $2k+1$ terms: \begin{align*} \color{blue}{\sum_{k=0}^\infty}&\color{blue}{[s^{k+1}t^k]\left(O(x)E(x)\right)}\\ &=\sum_{k=0}^\infty\left(\frac{x}{1-x^2}\right)^{k+1}\left(\frac{x^2}{1-x^2}\right)^k\\ &=\frac{x}{1-x^2}\sum_{k=0}^\infty\frac{x^{3k}}{\left(1-x^2\right)^{2k}}\\ &=\frac{x}{1-x^2}\,\frac{1}{1-\frac{x^3}{\left(1-x^2\right)^2}}\\ &\,\,\color{blue}{=\frac{x-x^3}{1-2x^2-x^3+x^4}}\tag{3} \end{align*} Adding (2) and (3) we finally obtain \begin{align*} \color{blue}{A(x)=\frac{x}{1-2x^2-x^3+x^4}} \end{align*} and the claim (1) follows.