0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Aug 24 '20 at 0:32
  • $\begingroup$ My bad. I had confused the notation $(\cdot )?$ in regular expressions for the parentheses notation, which doesn't rly make sense. $\endgroup$ Aug 24 '20 at 1:00
  • $\begingroup$ 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. $\endgroup$
    – J.-E. Pin
    Aug 25 '20 at 5:42
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Aug 23 '20 at 23:12
  • $\begingroup$ @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. $\endgroup$ Aug 24 '20 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.