6
$\begingroup$

Find a recurrence relation for the number of ternary strings of length ݊ 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:

Find a recurrence relation for the number of ternary strings of length ݊ 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 or. Please help me to find out where did i go wrong?

$\endgroup$
  • $\begingroup$ Why can't it start with 1102 for example? The condition only says that you cannot have both 11 and 00 in the same string, having one of them is allowed. $\endgroup$ – Raziman T V Feb 4 '17 at 14:44
  • $\begingroup$ @RazimanTV isn't it also included in $f_{n} = f_{n-1}+2f_{n-2}+2f_{n-3}+2f_{n-4}+...+2$? $\endgroup$ – IAmBlake Feb 4 '17 at 14:47
  • $\begingroup$ I don't see it. Perhaps you could expand on the steps a bit more. I do have an alternative solution but that is based on inclusion exclusion. $\endgroup$ – Raziman T V Feb 4 '17 at 14:50
  • $\begingroup$ @RazimanTV oh you can add it , i really appreciate it, but all i need is a recurrence relation to express my result $\endgroup$ – IAmBlake Feb 4 '17 at 14:53
  • $\begingroup$ I think the relation you found itself is incorrect which is why your recurrence is wrong. If you write down a couple more terms of a_i (say a_{n-4} to a_{n-7}) perhaps I can debug it. $\endgroup$ – Raziman T V Feb 4 '17 at 15:07
5
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Interesting.The OEIS search for $1,3,9,27,79$ finds several sequences. Successively adding terms narrows the search - often the next term is off just by $2$. Eventually this one isn't there - submit it? oeis.org/… $\endgroup$ – Ethan Bolker Feb 4 '17 at 19:30
  • 1
    $\begingroup$ Submitted: oeis.org/A282087 $\endgroup$ – Daniel Martin Feb 6 '17 at 14:53
  • $\begingroup$ @DanielMartin: Very nice derivation and instructive presentation! (+1) $\endgroup$ – Markus Scheuer Feb 6 '17 at 15:34
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ @DanielMartin: I've added an answer which might please you. $\endgroup$ – Markus Scheuer Feb 11 '17 at 10:03
  • $\begingroup$ There is another way to prove that there is no recurrence relation with fewer terms (that is, that you must reach back to $a_{n-4}$): form the 4x4 matrix of {{$a_0$, $a_1$, $a_2$, $a_3$}, {$a_1$, $a_2$, $a_3$, $a_4$}, {$a_2$, $a_3$, $a_4$, $a_5$}, {$a_3$, $a_4$, $a_5$, $a_6$}}. Now calculate the determinant, and see that it is not 0. If you do the same to make a 5x5 matrix, that has a 0 determinant. This shows that any linear recurrence relation must have a $a_{n-4}$ term. $\endgroup$ – Daniel Martin Feb 13 '17 at 22:26

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.