Interestingly restricted compositions of $n$

Question

Let $n$ be a non-negative integer. How many compositions of $n$ are there where the $i$-th part has the same parity as $i$?

The main problem I'm having with this problem is that I can't really formulate a single generating function for the set of all tuples of natural numbers where the $i$-th element has the same parity as $i$. How should I proceed?

Answer 1

Let $a_n$ be the number of compositions of $n$ whose $i$-the part has the same parity as $i$, and let $b_n$ be the number of compositions of $n$ whose $i$-the part has the opposite parity to $i$. Considering the possible values of the first part of a composition of $n$, we see that

$$a_{2n+1}=\sum_{k=0}^nb_{2k}\quad\text{ and }\quad a_{2n}=\sum_{k=0}^{n-1}b_{2k+1}$$

and

$$b_{2n+1}=\sum_{k=0}^{n-1}a_{2k+1}\quad\text{ and }\quad b_{2n}=\sum_{k=0}^{n-1}a_{2k}\;,$$

and hence that

$$\left\{\begin{align*}a_n&=a_{n-2}+b_{n-1}\\ b_n&=a_{n-2}+b_{n-2}\;. \end{align*}\right.\tag{1}$$

If we make the blanket assumption that $a_n=b_n=0$ for all $n<0$ and set $a_0=0$ and $b_0=1$, $(1)$ is valid for all $n\in\Bbb Z$ except in the case of $b_0$, adding an Iverson bracket term to get

$$\left\{\begin{align*}a_n&=a_{n-2}+b_{n-1}\\ b_n&=a_{n-2}+b_{n-2}+[n=0]\;. \end{align*}\right.\tag{2}$$

fixes this.

Let

$$A(x)=\sum_{n\ge 0}a_nx^n\quad\text{and}\quad B(x)=\sum_{n\ge 0}b_nx^n$$

be the generating functions for the two sequences. Then multiplying the recurrences $(2)$ by $x^n$ and summing over $n\ge 0$ yields

$$\left\{\begin{align*} A(x)&=x^2A(x)+xB(x)\\ B(x)&=x^2A(x)+x^2B(x)+1\;. \end{align*}\right.$$

Then

$$B(x)=\frac{x^2}{1-x^2}A(x)+\frac1{1-x^2}$$

and

$$A(x)=\frac{x}{1-x^2}B(x)=\frac{x^3}{(1-x^2)^2}A(x)+\frac{x}{(1-x^2)^2}\;,$$

so

$$\begin{align*} A(x)&=\frac{x}{1-x^2}\left(1-\frac{x^3}{(1-x^2)^2}\right)^{-1}\\\\ &=\frac{x}{1-x^2}\cdot\frac{(1-x^2)^2}{1-2x^2-x^3+x^4}\\\\ &=\frac{x(1-x)}{1-2x^2-x^3+x^4} \end{align*}$$

and

$$\begin{align*} B(x)&=\frac{1-x^2}xA(x)\\\\ &=\frac{(1-x)^2(1+x)}{1-2x^2-x^3+x^4}\;. \end{align*}$$

Some actual numbers:

$$\begin{array}{rccc} n:&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\ a_n:&0&1&0&2&1&3&4&5&10&11&21&27&43&64\\ b_n:&1&0&1&1&1&3&2&6&6&11&16&22&37&43 \end{array}$$

OEIS has $\langle a_n+b_n:n\ge 0\rangle=\langle b_{n+2}:n\ge 0\rangle$ as OEIS A062200 and $\langle a_n:n\ge 0\rangle$ as OEIS A122514. It has little more information beyond the recurrence

$$b_n=2b_{n-2}+b_{n-3}-b_{n-4}\;,$$

which is easily derived from $(1)$.

Answer 2

Let the OGF of odd parts be $o(z)=\frac{z}{1-z^2}$ (i.e. one of each odd size), and of (non-zero) even parts be $e(z)=\frac{z^2}{1-z^2}$ .

The compositions you require consist of a (possibly empty) sequence of pairs of "odd part followed by even part", and then an optional final odd part, so the OGF is $$c(z)\;=\; \frac{1}{1-o(z)e(z)}(1+o(z))\;=\;\frac{(1-z^2) (1+z-z^2)}{1 -2 z^2-z^3+z^4}. $$ For $n\geqslant0$, the series begins $1, 1, 0, 2, 1, 3, 4, 5, 10, 11, 21, 27, 43, 64, 92, 144$.