Generating series for binary string: odd blocks of 1s and no 0001 string

Question

Question: Find a generating function for a binary string where each block of ones must have an odd length and the string cannot contain the substring 0001.

My approach:

First, a general block decomposition for all binary strings is $(0^*(0^*01^*1)^*1^*)$. I modified this to $0^*(0^*01(11)^*)^*(1(11)^*\cup\epsilon)$ to account for the fact that the 1 blocks must be odd.

Now, to not include 0001, I know that you can use the recursive method wherein you define two sets, call them A and B, where A is the set of all strings not containing 0001 and B is the set of all strings ending in 0001.

Then, we have that $A\cup B = \epsilon \cup A(0\cup 1)$ so $A(x) + B(x) = 1 + 2xA(x)$. Similarly, $B = A0001$ so $B(x) = x^4A(x)$ so I get the relation $$A(x) = \frac{1}{1-2x+x^4}$$ but I'm not sure how to factor in the fact that the 1 block must have odd length.

Any help solving this problem would be appreciated. Thanks!

Answer 1

We start with looking for a regular expression and the corresponding generating function of a somewhat simpler problem, namely considering block lengths of $1$ having length one only.

(Simpler) problem: Find a generating function for a binary string where each block of $1$s has length one and the string cannot contain the substring $0001$.

A regular expression generating strings for this problem is \begin{align*} (\varepsilon|1)(01|001)^{\ast}0^{\ast}\tag{1} \end{align*} In (1) we specify the strings which

• start with the empty string or a $1$, followed by

• zero or more occurrences of $01$ or $001$ this way guaranteeing that no pattern $0001$ can occur and ending with

• zero or more occurrences of $0$.

The corresponding generating function of (1) is \begin{align*} (1+z)&(1+(z^2+z^3)+(z^2+z^3)^2+\cdots)(1+z+z^2+\cdots)\\ &=(1+z)\cdot\frac{1}{1-(z^2+z^3)}\cdot\frac{1}{1-z}\tag{2}\\ &=\frac{1}{1-z^2-z^3} \end{align*}

From (1) and (2) we can obtain a regular expression and generating function for the original problem by substituting each occurrence of $1$ by an odd number of $1$ and leaving $0$ as it is.

• Regular expression: $\ \,1\quad\to\quad 1(11)^{\ast}$

• Generating function: $z\quad\to\quad z+z^3+z^5+\cdots=z(1+z^2+z^4+\cdots)=\frac{z}{1-z^2}$ if $z$ represents $1$.

We obtain from (2) by replacing $z$ representing $1$ with $\frac{z}{1-z^2}$ the generating function \begin{align*} &\left(1+\frac{z}{1-z^2}\right)\cdot\frac{1}{1-\left(z\cdot\frac{z}{1-z^2}+z^2\cdot\frac{z}{1-z^2}\right)}\cdot\frac{1}{1-z}\\ &\qquad=\frac{1+z-z^2}{1-z^2}\cdot\frac{1-z^2}{1-2z^2-z^3}\cdot\frac{1}{1-z}\\ &\qquad\,\,\color{blue}{=\frac{1+z-z^2}{1-z-2z^2+z^3+z^4}}\tag{3}\\ &\qquad=1+2z+3z^2+6z^3+9z^4+16z^5+25z^6+42z^7+\cdots\tag{4} \end{align*}

The expansion (4) was done with some help of WolframAlpha. We see the coefficient of $z^6$ is $25$ and the corresponding valid strings of are \begin{align*} 000000\qquad010000\qquad011100\qquad100101\qquad101110\\ 001000\qquad010010\qquad011101\qquad100111\qquad111000\\ 001001\qquad010100\qquad011111\qquad101000\qquad111001\\ 001010\qquad010101\qquad100000\qquad101001\qquad111010\\ 001110\qquad010111\qquad100100\qquad101010\qquad111110\\ \end{align*}

Answer 2

Let $a_n$ be the number of strings that start with $0$, and let $b_n$ be the number of strings that start with $1$. Then $a_0=a_1=b_0=1$ and, by conditioning on the length $k$ of the current run, we see that \begin{align} a_n &= \sum_{k=1}^2 b_{n-k} + [n \ge 3] &&\text{for $n \ge 2$}\\ b_n &= \sum_{\substack{k=1\\\text{$k$ odd}}}^n a_{n-k} &&\text{for $n \ge 1$}. \end{align} Let $A(z)=\sum_{n=0}^\infty a_n z^n$ and $B(z)=\sum_{n=0}^\infty b_n z^n$. Then the recurrence relations imply \begin{align} A(z)-a_0-a_1 z &=(z + z^2) B(z) - z + \frac{z^3}{1-z} \\ B(z)-b_0 &=\frac{z}{1-z^2} A(z) \end{align} Solving for $A(z)$ and $B(z)$ yields \begin{align} A(z) &= \frac{1}{1-z-z^2}\\ B(z) &= 1+\frac{z}{(1-z^2)(1-z-z^2)} \end{align} So the desired generating function (subtracting the $1z^0=1$ term for the empty string that is otherwise counted twice) is $$A(z)+B(z)-1=\frac{1+z-z^2}{(1-z)(1+z)(1-z-z^2)},$$ which is OEIS A062114 except for $n=0$.