3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ I think there are $7$ such strings of length four, namely $0000$, $0001$, $0011$, $1000$, $1001$, $1100$, $1111$. Your first generating function suggests $2$ while your second suggests $3$ $\endgroup$ – Henry Jan 27 at 22:38
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I notice that this answer was unaccepted, but no other was accepted. Is there something that is unclear? $\endgroup$ – robjohn Jan 29 at 22:22
2
$\begingroup$

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

  1. $c_n=a_{n-1}$ from (3) and (1) and so $c_{n-2}=a_{n-3}$
  2. $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}$
  3. $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

$\endgroup$
2
$\begingroup$

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}.$$

$\endgroup$

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.