3
$\begingroup$

I'm a bit stuck with this problem and I'm sorry if this sounds newbie, I havent had much practice with recurrence relations. My approach was to split the problem into two cases, we let $a_n$ denote all legal binary strings of length $n$

  1. Appending $1$ to the front of a string, this case is simple because no illegal strings can be made by appending $1$ in front of a legal string, so by appending $1$ to all legal strings of length $n-1$ we get $a_{n-1}$ legal strings.
  2. Appending $0$ to the front of a string, this is where I get stuck.

My idea was to split the second case into even further cases so that each case would deal with the following prefixes: $00$, $01$, $10$ and $11$

The problem is that I can not find any good way to determine how many of each prefix occurs in the set of legal strings of length $n-1$. Any advice on this problem (or this subject in general) would be greatly appreciated since there is clearly something that I'm misunderstanding.

$\endgroup$
3
$\begingroup$

Let $a_n$ be the number of n-length sequences ending with $1$, $b_n$ the number of n-length sequences ending with $0$, but not with $00$ and $c_n$ the number of n-length sequences ending with $00$, but not with $000$. Obviously the wanted number is $a_n+b_n+c_n$.

Now we can take any of the sequence of the valid sequences of length $n$ and add $1$ to it and it will be a valid sequence of length $(n+1)$. Hence:

$$a_{n+1} = a_n + b_n + c_n$$

Now the only way to "construct" a sequence ending in a single zero is to take any of the $a_n$ sequences and append $0$ to it. Similarly the only way to "construct" a sequence ending in two zeroes is to take any of the $b_n$ sequences and append $0$ to it. Hence:

$$b_{n+1} = a_n; \quad \quad c_{n+1} = b_n = a_{n-1}$$

Therefore finally we have that:

$$a_{n+1} = a_n + a_{n-1} + a_{n-2}$$

Solving this recurrence relation for $a_1 = 1, a_2 = 2, a_3=4$ we can easily find the wanted answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for a very good explanation :) $\endgroup$ – Kristallll Nov 20 '16 at 21:14
  • 1
    $\begingroup$ Minor point: I think you meant $(a_1, a_2, a_3) = (1, 2, 4)$. For instance, there is only a single length-$1$ sequence ending in a $1$. $\endgroup$ – mathmandan Nov 21 '16 at 5:04
  • $\begingroup$ @mathmandan Yeah, you're right. I was counting all sequences instead of counting only those who end with 1. $\endgroup$ – Stefan4024 Nov 21 '16 at 9:41
5
$\begingroup$

The so-called Goulden-Jackson Cluster Method is a convenient technique to derive a generating function for problems of this kind.

We consider the set of binary words of length $n\geq 0$ and the set $B=\{000\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a function $f(s)$ with the coefficient of $s^n$ being the number of wanted words of length $n$.

According to the paper (p.7) from Goulden and Jackson the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=2$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[000]) \end{align*} We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[000])&=-\frac{s^3}{1+s+s^2}=-\frac{s^3(1-s)}{1-s^3} \end{align*}

We obtain the generating function $f(s)$ for the binary words which do not contain the substring $000$ as \begin{align*} f(s)&=\frac{1}{1-2s+\frac{s^3(1-s)}{1-s^3}}\\ &=\frac{1-s^3}{1-2s+s^4}\tag{2}\\ &=1+2s+4s^2+7s^3+13s^4+24s^5+44s^6+81s^7+\cdots \end{align*}

Note: The entries in the sequence $(1,2,4,7,13,24,44,81,149,274,\ldots)$ are the so-called Tribonacci numbers stored as A000073 in OEIS.

An explicit formula for the Tribonacci numbers is

\begin{align*} [s^n]f(s)&=\sum_{{k=0}\atop{k\equiv n(\bmod 3)}}^{2}\binom{k}{\frac{n-k}{3}}(-1)^{\frac{n-k}{3}}2^{k-\frac{n-k}{3}}\\ &\qquad+\sum_{{k=3}\atop{k\equiv n(\bmod 3)}}^{n-3} \left(\binom{k}{\frac{n-k}{3}}-\frac{1}{8}\binom{k-3}{\frac{n-k}{3}}\right)(-1)^{\frac{n-k}{3}}2^{k-\frac{n-k}{3}}\\ \end{align*}

A calculation can be found in this answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @MarkoRiedel: Many thanks for your nice comment! :-) (+1) $\endgroup$ – Markus Scheuer Nov 20 '16 at 22:12
3
$\begingroup$

The DFA method including a Maple implementation was presented at the following MSE link. In the present case we obtain the following session.

> GFNC([[0,0,0]], 2, true);
                               [[0, 0, 0]]

                              Q[], 0, Q[0]

                               Q[], 1, Q[]

                            Q[0], 0, Q[0, 0]

                              Q[0], 1, Q[]

                         Q[0, 0], 0, Q[0, 0, 0]

                             Q[0, 0], 1, Q[]

                        Q[0, 0, 0], 0, Q[0, 0, 0]

                        Q[0, 0, 0], 1, Q[0, 0, 0]

                                 2
                                z  + z + 1
                            - ---------------
                               3    2
                              z  + z  + z - 1

This is the same as what Markus Scheuer obtained with a common factor of $s-1$ being canceled.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Let $u_n$ be the number of legal sequences of length $n$ beginning with 1. Then the number beginning with 01 and 00 is $u_{n-1}$ and $u_{n-2}$ respectively. Hence the total number of length $n$ is $t_n = u_n + u_{n-1} + u_{n-2}$. But clearly $u_{n+1} = t_n$. Hence $u_n$, and therefore $t_n$, satisfies the "Tribonnaci" recurrence. Similarly we get the "Tetranacci" recurrence if 0000 is forbidden, and so on.

| cite | improve this answer | |
$\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.