# no consecutive even parts

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?

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)$$

• I had used parentheses just for grouping, not to indicate that $E$ is optional. I removed them now and updated to use $\epsilon$ for the empty string. Aug 24 '20 at 0:32
• My bad. I had confused the notation $(\cdot )?$ in regular expressions for the parentheses notation, which doesn't rly make sense. Aug 24 '20 at 1:00
• You need to be more careful, as your three basic facts only apply to unambiguous regular expressions. Thus (1) and (2) are wrong if $A$ is not a code, that is, if $A^*$ is not free and (3) is wrong if $A$ contains the empty word. You also seem to use implicitly a formula for the product, which also requires unambiguity. Aug 25 '20 at 5:42

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.

• sorry I'm new to recurrence relations; I've just learned them. So do I have to solve the characteristic equation $\lambda^4 - \lambda^3 - 2\lambda^2 + 1 = 0$? And then what will be the significance of the roots? Say the roots are $r_1,r_2,r_3,r_4.$ Will the solution be of the form $c_n = A\cdot r_1^n + B\cdot r_2^n + C \cdot r_3^n + D\cdot r_4^n$, where $A,B,C,D\in \mathbb{R}$? Correct me if I'm wrong. Aug 23 '20 at 23:12
• @FredJefferson: That’s one way to get a closed form for $c_n$, but in this case it would be pretty miserable, since that quartic doesn’t have nice roots. I wasn’t thinking of that: I was just thinking of deriving the generating function. Since you’re not familiar with the technique, I’ll add it to my answer hen I get a bit of time, if only for future reference. Aug 24 '20 at 4:33