Generating function of binary string with minimum lengths for 0s and 1s

Question

a) Show that the generating function by length for binary strings where every block of 0s has length at least 2, each block of ones has length at least 3 is:

$$\frac{(1-x+x^3)(1-x+x^2)}{1-2x+x^2-x^5}$$

b) Give a recurrence relation and enough initial conditions to determine coefficients of power series.

So for a), I came up with the block decomposition $((0^*00)^*(1^*111)^*)^*$ and found the generating function, using the fact that $0\leadsto x$, $1\leadsto x$, and $a^*\leadsto\frac{1}{1-a}$ where a is some binary string:

$$\frac{(1-x)^2}{(1-x-x^2)(1-x-x^3)}$$

which, clearly, does not equal the expected result. Could someone clear up for me where I went wrong?

Also, for b), how would you find a recurrence relation, since the degree of the numerator and denominator are the same, so there would be no general $a_n$ term.

Thanks in advance for any help!

Answer 1

Generating Function

We can piece together the generating function as follows $$ \overbrace{\vphantom{\left(\frac{x^2}1\right)}\ \ \frac1{1-x}\ \ }^{\substack{\text{any number}\\\text{of ones}}}\overbrace{\vphantom{\left(\frac{x^2}1\right)}\frac1{1-\underbrace{\quad\frac{x^2}{1-x}\quad}_{\substack{\text{two or more}\\\text{zeros}}}\underbrace{\quad\frac{x}{1-x}\quad}_{\substack{\text{one or more}\\\text{ones}}}}}^{\substack{\text{any number of blocks of zeros}\\\text{and ones}}}\overbrace{\left(1+\frac{x^2}{1-x}\right)}^{\substack{\text{zero or two or}\\\text{more zeros}}} $$ The block decomposition is $1^\ast\left(000^\ast11^\ast\right)^\ast\left(()+000^\ast\right)$

Thus, the generating function is $$ \bbox[5px,border:2px solid #C0A000]{\frac{1-x+x^2}{1-2x+x^2-x^3}} $$

---

Recurrence Relation

Note that $$ \begin{align} &1-x+x^2\\ &=\left(1-2x+x^2-x^3\right)\sum_{k=0}^\infty a_kx^k\\ &=\overbrace{\vphantom{()}\quad\ a_0\quad\ }^1+\overbrace{(a_1-2a_0)}^{-1}\,x+\overbrace{(a_2-2a_1+a_0)}^1\,x^2+\sum_{k=3}^\infty\overbrace{(a_k-2a_{k-1}+a_{k-2}-a_{k-3})}^0\,x^k \end{align} $$ Therefore, the recurrence relation is determined by the denominator: $a_0=1$, $a_1=1$, and $a_2=2$, then for $n\ge3$, use $$ \bbox[5px,border:2px solid #C0A000]{a_n=2a_{n-1}-a_{n-2}+a_{n-3}} $$

Answer 2

robjohn has given a generating function. Here is a recurrence based approach.

Suppose $b_n$ is the number of strings ending with $0$ and $c_n$ the number ending with $1$, and $a_n=b_n+c_n$ being what you want. It seems obvious that

1. $a_n=b_n+c_n$ by definition
2. $b_n=b_{n-1}+c_{n-2}$ by adding $0$ to an existing $0$ or $00$ to an existing $1$
3. $c_n=b_{n-1}+c_{n-1}$ by adding $1$ to an existing $0$ or $1$

so

4. $c_n=a_{n-1}$ from (3) and (1) and so $c_{n-2}=a_{n-3}$
5. $b_{n-1}=c_n-c_{n-1}=a_{n-1}-a_{n-2}$ from (3) and (4) and so $b_{n}=a_{n}-a_{n-1}$
6. $a_{n}-a_{n-1}=a_{n-1}-a_{n-2}+a_{n-3}$ from (2) and (5) and (4) giving $$a_{n}=2a_{n-1}-a_{n-2}+a_{n-3}$$

That will lead to a denominator in the generating function of $1-2x+x^2-x^3$

Since $b_1=0, b_2=1, c_1=1, c_2=1$, we can find $a_0=1, a_1=1, a_2=2, a_3=4, a_4=7$ etc. But $\frac{1}{1-2x+x^2-x^3}=1+2x+3x^2+5x^3+9x^4+\cdots$ so we need to subtract $\frac{x}{1-2x+x^2-x^3} = x+2x^2+3x^3+5x^4+\cdots$ and then add $\frac{x^2}{1-2x+x^2-x^3}= x^2+2x^3+3x^4+\cdots$ to match the coefficients, with a result of $$\frac{1-x+x^2}{1-2x+x^2-x^3}$$ as robjohn found more directly

Answer 3

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=b_0=1$, $a_1=0$, and, by conditioning on the length $k$ of the current run, we see that \begin{align} a_n &= \sum_{k=2}^n b_{n-k} &&\text{for $n \ge 2$}\\ b_n &= \sum_{k=1}^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_1z &=\frac{z^2}{1-z} B(z) \\ B(z)-b_0 &=\frac{z}{1-z} A(z) \end{align} Solving for $A(z)$ and $B(z)$ yields \begin{align} A(z) &= \frac{1-2z+2z^2-z^3}{1-2z+z^2-z^3}\\ B(z) &= \frac{1-z}{1-2z+z^2-z^3} \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-2z+z^2-z^3}.$$