Find a recurrence relation for the number of ternary strings of length ݊ that do not contain two consecutive 0s and two consecutive 1s.

Question

This question is published in multiple textbooks and already has an answer elsewhere on math.SE:

Find a recurrence relation for the number of ternary strings of length $n$ that do not contain two consecutive 0s or two consecutive 1s.

This question above has a recurrence relation $f_{n}=2f_{n-1}+f_{n-2}$.

But the same problem replacing or to and seems to be much more difficult:

Find a recurrence relation for the number of ternary strings of length $n$ that do not contain two consecutive 0s and two consecutive 1s.

I tried to solve it in the way below:

i) starts with 2 -> $a_{n-1}$

ii) starts with 12 or 02 -> $a_{n-2}$

iii) starts with 012 or 102 -> $a_{n-3}$

and so on .

So the relation :$$f_{n}=f_{n-1}+2f_{n-2}+2f_{n-3}+....+f_{0}+2$$ that is $$f_{n}=2f_{n-1}+f_{n-2}$$ I got a same relation as with the original question using or. Please help me to find out where did I go wrong?

Answer 1

So the problem, as I see it, starts shortly after point (iii) above: what about strings that begin with 002? To find those cases, you must find strings of length $n-3$ that do not have 11 in them. This is some amount less than $a_{n-3}/2$, but how much I don't know. (the 112 case is similar)

So to solve this, I'd divide the problem into several classes, find a recurrence relation for each class, and then combine that to obtain a recurrence for the sum.

So then, let's define a few cases:

$a_n$ will be the original sequence, the number of trinary strings of length $n$ that do not contain both two consecutive 0s and two consecutive 1s
$b_n$ will be the number of trinary strings of length $n$ that do contain two consecutive 0s, but do not contain two consecutive 1s
$c_n$ will be the number of trinary strings of length $n$ that do contain two consecutive 1s, but do not contain two consecutive 0s
$d_n$ will be the number of trinary strings of length $n$ that do not contain either two consecutive 0s or two consecutive 1s

Note that $a_n = b_n + c_n + d_n$.

Now, for $i = 0, 1, 2$, let $a^i_n$ be those strings be those strings of the kind we're looking to count to make $a_n$ that begin with the digit $i$. So for example, we have: $$a_n = a^0_n + a^1_n + a^2_n$$ Similarly, define $b^i_n$, $c^i_n$, and $d^i_n$.

Now, consider finding a recurrence relation for $b_n$; it's easiest to break that up into recurrence relations for $b^0_n$, $b^1_n$, and $b^2_n$.

Straight from the definitions we get: \begin{align} b^0_n &= b_{n-1} + d^0_{n-1} \\ b^1_n &= b^0_{n-1} + b^2_{n-1} \\ b^2_n &= b_{n-1} \end{align} Remember, we're looking for strings that do contain 00 but do not contain 11. For such a string to begin with 0, that means that the rest of the string either already met our condition ($b_{n-1}$ cases) or was a string with no consecutive 0s or consecutive 1s that started with 0 ($d^0_{n-1}$ cases). For such a string to begin with 1, that means that the rest of the string already met our condition and began with a 0 or a 2 ($b^0_{n-1} + b^2_{n-1}$ cases). For such a string to begin with 2, it means only that the rest of the string matched our condition. ($b_{n-1}$ cases)

To reduce the number of different series we're dealing with, let's try to eliminate the series $b^i_n$ and leave ourselves with only $b^i_n$ and $d^0_n$ on the right hand sides:

\begin{align} b^0_n &= b_{n-1} + d^0_{n-1} \\ b^1_n &= b_{n-2} + d^0_{n-2} + b_{n-2} \\ b^2_n &= b_{n-1} \end{align}

Therefore: $$b_n = b^0_n + b^1_n + b^2_n = 2b_{n-1} + 2b_{n-2} + d^0_{n-1} + d^0_{n-2}$$ By similar logic, we can derive a formula for $c_n$: $$c_n = 2c_{n-1} + 2c_{n-2} + d^1_{n-1} + d^1_{n-2}$$

Note that we already have a a recurrence relation for $d_n$ from the original problem: $$d_n = 2d_{n-1} + d_{n-2}$$

Also note that $d^2_n = d_{n-1}$ and therefore $$d^0_n + d^1_n = d_n - d^2_n = d_n - d_{n-1}$$ This will come in useful later.

Now then, for $a_n$: \begin{align} a_n &= b_n + c_n + d_n \\ &= 2b_{n-1} + 2b_{n-2} + d^0_{n-1} + d^0_{n-2} \\ & \qquad + 2c_{n-1} + 2c_{n-2} + d^1_{n-1} + d^1_{n-2} \\ & \qquad + 2d_{n-1} + d_{n-2} \\ &= 2a_{n-1} + a_{n-2} + (a_{n-2} - d_{n-2}) + d_{n-1} - d_{n-2} + d_{n-2} - d_{n-3} \\ &= 2a_{n-1} + 2a_{n-2} + d_{n-1} - d_{n-2} - d_{n-3} \\ &= 2a_{n-1} + 2a_{n-2} + (2d_{n-2} + d_{n-3}) - d_{n-2} - d_{n-3} \\ &= 2a_{n-1} + 2a_{n-2} + d_{n-2} \end{align}

Almost there. We can now work to eliminate the $d_{n-2}$ terms, but first notice that this last equation can be rewritten as: $$d_{n-2} = a_n - 2a_{n-1} - 2a_{n-2}$$ And therefore these two equations follow: \begin{align} d_{n-3} &= a_{n-1} - 2a_{n-2} - 2a_{n-3} \\ d_{n-4} &= a_{n-2} - 2a_{n-3} - 2a_{n-4} \end{align} Now, applying the recurrence relation for $d_n$ again: \begin{align} a_n &= 2a_{n-1} + 2a_{n-2} + d_{n-2} \\ &= 2a_{n-1} + 2a_{n-2} + 2d_{n-3} + d_{n-4} \\ &= 2a_{n-1} + 2a_{n-2} + 2a_{n-1} - 4a_{n-2} - 4a_{n-3} + a_{n-2} - 2a_{n-3} - 2a_{n-4} \\ &= 4a_{n-1} - a_{n-2} - 6a_{n-3} - 2a_{n-4} \end{align} So that's the final recurrence relation: $$a_n = 4a_{n-1} - a_{n-2} - 6a_{n-3} - 2a_{n-4}$$ This is something of a mess, but it checks out: \begin{align} a_0 &= 1 \\ a_1 &= 3 \\ a_2 &= 9 \\ a_3 &= 27 \\ a_4 &= 79 \\ a_5 &= 229 \\ a_6 &= 657 \\ a_7 &= 1871 \\ a_8 &= 5295 \end{align}

Those values were calculated with the recurrence relation and verified by the python program:

import itertools
def find_a_sub_n(n):
    c = 0
    for q in itertools.product(*([['0','1','2']]*n)):
        h = ''.join(q)
        if not (('11' in h) and ('00' in h)):
            c = c+1
    return c

Answer 2

Note: Inspired by the nice answer of @DanielMartin we provide a slightly different approach. Nevertheless it will also lead to the same linear recurrence relation. In fact there are some arguments which indicate that no simpler linear recurrence relation can be found.

In order to ease comparison I use the same notation as @DanielMartin.

We consider the following sets of words built from the ternary alphabet $V=\{0,1,2\}$.

• $a_n$: Counts the ternary words which do not contain both $00$ as well as $11$

• $d_n$: Counts the ternary words which do not contain either $00$ or $11$ or both.

• $e_n$: Counts the ternary words which do not contain $00$.

• $f_n$: Counts the ternary words which do not contain $11$.

The variables obey the following relation \begin{align*} a_n=e_n+f_n-d_n \end{align*}

Indeed, since $e_n$ counts the words without consecutive $0$'s and $f_n$ the words without consecutive $1$'s the number of words which do not contain any of them, neither $00$ nor $11$, given by $d_n$ is counted twice. This is compensated by subtracting $d_n$.

Note, the connection with $b_n$ and $c_n$ in the answer by @DanielMartin is given by \begin{align*} e_n&=c_n+d_n\\ f_n&=b_n+d_n\\ \end{align*}

Recurrence relation for $d_n$ and $e_n$:

Due to symmetry we see that $e_n=f_n$ and we obtain \begin{align*} a_n=2e_n-d_n\tag{1} \end{align*} Denoting with $e_n^i$ a word counted by $e_n$ which starts with $i\in\{0,1,2\}$. We obtain a recurrence relation for $e_n$ by \begin{align*} e_n^0&=e_{n-1}^1+e_{n-1}^2\tag{2}\\ e_n^1&=e_{n-1}\tag{3}\\ e_n^2&=e_{n-1}\\ \end{align*}

Comment:

• We obtain (2) since words of length $n$ with no consecutive $0$'s which start with $0$ are followed by words of length $n-1$ which have to start with either $1$ or $2$.
• In (3) we note that words of length $n$ with no consecutive $0$'s which start with $1$ are followed by any words of length $n-1$ with no consecutive $0$'s. The same holds due to symmetry also for $e_n^2$.

We obtain \begin{align*} e_n&=e_n^0+e_n^1+e_n^2\\ &=(e_{n-1}^1+e_{n-1}^2)+(e_{n-1})+(e_{n-1})\\ &=(e_{n-2}+e_{n-2})+2e_{n-1}\\ &=2e_{n-1}+2e_{n-2}\tag{4} \end{align*}

Similarly we get a recurrence relation for $d_n$ by \begin{align*} d_n&=d_n^0+d_n^1+d_n^2\\ &=(d_{n-1}^1+d_{n-1}^2)+(d_{n-1}^0+d_{n-1}^2)+d_{n-1}\\ &=2d_{n-1}+d_{n-1}^2\\ &=2d_{n-1}+d_{n-2}\tag{5} \end{align*}

$$ $$

Recurrence relation for $a_n$:

We now derive a recurrence relation for $a_n$. We obtain from (1) \begin{align*} a_n&=2e_n-d_n\\ a_{n-1}&=2e_{n-1}-d_{n-1}\\ a_{n-2}&=2e_{n-2}-d_{n-2}\\ \end{align*}

It follows with (4) and (5)

\begin{align*} a_n&=2e_n-d_n\tag{6}\\ &=4e_{n-1}-4e_{n-1}-d_n\\ &=2a_{n-1}+2d_{n-1}+2a_{n-2}+2d_{n-2}-d_n\\ &=2a_{n-1}+2a_{n-2}+d_{n-2} \tag{7} \end{align*}

Almost there - to use the words from @DanielMartin. This relation (7) was also found in his answer and he derived finally from it the relation \begin{align*} a_n = 4a_{n-1} - a_{n-2} - 6a_{n-3} - 2a_{n-4}\qquad\qquad n\geq 4\tag{8} \end{align*}

We now additionally take a look at generating functions for $e_n$ and $d_n$. This will provide another view to the recurrence relation. We start with a generating function for words of a three character alphabet which counts words with no equal consecutive characters at all. These words are called Smirnov or Carlitz words. See (example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for a more information.

The generating function $G(z)$ giving the number of Smirnov words over a three character alphabet is \begin{align*} G(z)=\left(1-\frac{3z}{1+z}\right)^{-1} \end{align*}

Generating functions for $e_n$ and $d_n$

To obtain a generating function $E(z)=\sum_{n\geq 0}e_nz^n$ for all three character words with no consecutive $0$'s we can take all Smirnov words and replace each occurrence of $1$ with one or more occurrences of $1$ and the same with $2$. This means in terms of generating functions replacing $z$ with $\frac{z}{1-z}$. We obtain according to the referred section \begin{align*} E(z)&=\left(1-\frac{z}{1+z}-\frac{\frac{2z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\ &=\left(1-\frac{z}{1+z}-2z\right)^{-1}\\ &=\frac{1+z}{1-2z-2z^2}\\ &=1+3z+8z^2+22z^3+60z^4+164z^5+\cdots \end{align*}

The sequence $e_n$ is archived in OEIS as A028859

Analogously we obtain the generating function $D(z)=\sum_{n\geq 0}d_nz^n$ for all three characters with no consective $0$'s as well as no consecutive $1$, we obtain \begin{align*} D(z)&=\left(1-\frac{2z}{1+z}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\ &=\left(1-\frac{2z}{1+z}-z\right)^{-1}\\ &=\frac{1+z}{1-2z-z^2}\\ &=1+3z+7z^2+17z^3+41z^4+99z^5+\cdots \end{align*}

The sequence $d_n$ is archived in OEIS as A078057

Generating functions for $a_n$

According to $$a_n=2e_n-d_n$$ stated as (6) we observe that $E(z)$ and $D(z)$ are building blocks for $A(z)=\sum_{n\geq 0}a_nz^n$ \begin{align*} A(z)&=2E(z)-D(z)\\ &=\frac{2(1+z)}{1-2z-2z^2}-\frac{1+z}{1-2z-z^2}\\ &=\frac{(1+z)(1-2z)}{1-4z+z^2+6z^3+2z^4}\tag{9}\\ &=1+3z+9z^2+27z^3+79z^4+229z^5+\\ &\qquad+657z^6+1871z^7+5295z^8+14909z^9+\cdots \end{align*}

The sequence $a_n$ is thanks to @DanielMartin archived in OEIS as A282087.

From (9) we see that \begin{align*} (1-4z+z^2+6z^3+2z^4)A(z)&=(1+z)(1-2z)\\ \end{align*} It follows for $n\geq 4$ with $[z^n]$ denoting the coefficient of $z^n$ \begin{align*} 0&=[z^n](1-4z+z^2+6z^3+2z^4)A(z)\\ &=[z^n]-4[z^{n-1}]+[z^{n-2}]+6[z^{n-3}]+2[z^{n-4}]\\ &=a_n-4a_{n-1}+a_{n-2}+6a_{n-3}+2a_{n-4} \end{align*} which corresponds with the recurrence relation (8).

Note: Since $A(z)=2E(z)-D(z)$ is built from expressions which can't be simplified, this also holds for the linear recurrence relation (8).