3
$\begingroup$

Let $a_n$ denote " the number of ternary strings of length n that do not contain three consecutive 1s"

Ternary string contains only 0, 1, 2 and has length n. The way I approached it was to make a tree of length n:

enter image description here

Besides from my obvious lack of artistic skills, I find it very hard to believe that the recurrence relation is $ a_n = 26(a_{n-3}) $ . If anybody could tell me what I did wrong and help me out, that would be greatly appreciated.

Note: I realized that there are some possible duplicates on the site, which I have went through and either 1) do not apply to three consecutive (insert digit here)s or 2) I don't fully understand.

$\endgroup$
  • $\begingroup$ Note that $26 = 3^3 - 1$. Does this make it easier to believe? $\endgroup$ – TonyK Dec 2 '15 at 0:58
  • $\begingroup$ Makes it easier than drawing out every single possible solution at least :) $\endgroup$ – bankey Dec 2 '15 at 0:59
5
$\begingroup$

Let $T_n$ be the number of such strings, call them "good", of length $n$. The goal is to get a recursion for $T_n$. To do it, we'll distinguish between the various ways a "good" string might end. Specifically (reading from left to right):

Let $a_n$ denote the number of good strings that end in $01$

Let $b_n$ denote the number of good strings that end in $011$

Let $c_n$ denote the number of good strings that end in $21$

Let $d_n$ denote the number of good strings that end in $211$

Let $e_n$ denote the number of good strings that end in $0$

Let $f_n$ denote the number of good strings that end in $2$.

Clearly $$T_n=a_n+b_n+c_n+d_n+e_n+f_n$$

It is easy to read off that: $$T_1=3\;\;\;\;T_2=9\;\;\;\;T_3=26$$

Recursively, we pass from strings of length $n-1$ to those of length $n$ by appending one of the three digits. Visibly,

$$a_n=e_{n-1}\;\;\;\;b_n=a_{n-1}\;\;\;\;c_n=f_{n-1}\;\;\;\;d_n=c_{n-1}\;\;\;\;e_n=T_{n-1}=f_n$$

It follows at once that $$a_n=T_{n-2}=c_n\;\;\;b_n=T_{n-3}=d_n$$

Whence

$$T_n=2(T_{n-2}+T_{n-3}+T_{n-1})$$

And we are done.

$\endgroup$
  • $\begingroup$ How are you getting those endings? For example, why is 01 a different ending than 0? $\endgroup$ – bankey Dec 2 '15 at 0:37
  • $\begingroup$ I am reading from left to right. If you want to read from right to left, change "ending" to "beginning" and "append" to "prepend". $\endgroup$ – lulu Dec 2 '15 at 0:39
  • $\begingroup$ Also: sorry for changing your notation. I worked it out with my own notation and neglected to convert. If it's confusing, I can convert it now...otherwise I'll just leave it. $\endgroup$ – lulu Dec 2 '15 at 0:43
  • $\begingroup$ I was taught recurrence with just using $a_{n-x}$ but I am fine with the notation. Maybe I should have rephrased my first comment: If you are reading left to right, with right being $a_n, b_n, c_n$ etc etc. How did you get so many endings? I don't see a difference between 0 and 01 , but I am reading the strings starting from the left and ending in right.... EDIT: I think I just figured it out, your answer is absolutely correct but I was just doing it backwards from the way you explained it, much thanks $\endgroup$ – bankey Dec 2 '15 at 0:47
  • $\begingroup$ The string $0220112122201$ "ends" in $01$ because those are the two right most entries. The string $22222122220$ "ends" in $0$. It is necessary to distinguish so many endings because you have to take care not to append a $1$ to a good sequence that "ends" in $011$ or $211$. $\endgroup$ – lulu Dec 2 '15 at 0:53
3
$\begingroup$

Generating Function

Let's build the generating function of the number of $n$ length bit strings that don't have $3$ ones in a row. We can do this by starting with $1+x+x^2$ representing $0$, $1$, or $2$ ones. Then we will have $0$ or more molecules consisting of $2$ atoms: an atom consisting of $1$ or more zeros and twos, and an atom consisting of $1$ or $2$ ones. There are $2^k$ atoms of zeros and twos that have length $k$. Thus, the generating function for $1$ or more would be $$ \sum_{k=1}^\infty(2x)^k=\frac{2x}{1-2x} $$ The generating function for the atom of $1$ or $2$ ones is $x+x^2$. Then there is a final atom of $0$ or more zeros and twos, giving a generating function of $$ \sum_{k=0}^\infty(2x)^k=\frac1{1-2x} $$ We can get any valid pattern in a unique way by summing $$ \begin{align} &\overbrace{\left(1+x+x^2\right)\vphantom{\left(\frac11\right)^k}}^{\text{initial ones}}\sum_{k=0}^\infty \overbrace{\left(\frac{2x}{1-2x}\left(x+x^2\right)\right)^k}^{\substack{\text{arbitrary number of}\\\text{zeros and twos followed by ones}}}\overbrace{\frac1{1-2x}\vphantom{\left(\frac11\right)^k}}^{\substack{\text{final}\\\text{zeros and twos}}}\\ &=\left(1+x+x^2\right)\frac1{1-\left(\frac{2x}{1-2x}\right)\left(x+x^2\right)}\frac1{1-2x}\\ &=\bbox[5px,border:2px solid #C0A000]{\frac{1+x+x^2}{1-2x-2x^2-2x^3}}\\[6pt] &=1+3x+9x^2+26x^3+76x^4+222x^5+\dots \end{align} $$ Thus, we get $a_0=1$, $a_1=3$, and $a_2=9$. For $n\gt2$ we can use the recursion indicated by the denominator: $$ \bbox[5px,border:2px solid #C0A000]{a_n=2a_{n-1}+2a_{n-2}+2a_{n-3}} $$ Representing A String By Atoms

The string "$\color{#C00000}{0220}11\color{#C00000}{2}1\color{#C00000}{2220}1$" is counted in the $k=3$ term: $$ \begin{align} &\small\overbrace{\left(1\color{#C0C0C0}{+x+x^2}\right)}^{\text{$0$ ones}}\overbrace{\overbrace{\left(\color{#C0C0C0}{2x+4x^2+8x^3+}16x^4\color{#C0C0C0}{+\dots}\right)}^{\text{$4$ zeros or twos}}\overbrace{\left(\color{#C0C0C0}{x+}x^2\right)}^{\text{$2$ ones}}}^{k=1} \overbrace{\overbrace{\left(2x\color{#C0C0C0}{+4x^2+8x^3+16x^4}\color{#C0C0C0}{+\dots}\right)}^{\text{$1$ zero or two}}\overbrace{\left(x\color{#C0C0C0}{+x^2}\right)}^{\text{$1$ one}}}^{k=2}\\ &\small\overbrace{\overbrace{\left(\color{#C0C0C0}{2x+4x^2+8x^3+}16x^4\color{#C0C0C0}{+\dots}\right)}^{\text{$4$ zeros or twos}}\overbrace{\left(x\color{#C0C0C0}{+x^2}\right)}^{\text{$1$ one}}}^{k=3}\overbrace{\left(1\color{#C0C0C0}{+2x+4x^2+8x^3+16x^4+\dots}\right)}^{\text{$0$ zeros or twos}}=512x^{13} \end{align} $$ Getting The Recursion From The Denominator

Suppose that $$ \sum_{k=0}^\infty a_kx^k=\frac{1+x+x^2}{1-2x-2x^2-2x^3} $$ Multiplying both sides by $1-2x-2x^2-2x^3$, gives $$ \left(1-2x-2x^2-2x^3\right)\sum_{k=0}^\infty a_kx^k=1+x+x^2 $$ Equating the coefficient of $x^n$ on both sides, for $n\gt2$, we get $$ a_n-2a_{n-1}-2a_{n-2}-2a_{n-3}=0 $$ which gives the recursion $$ a_n=2a_{n-1}+2a_{n-2}+2a_{n-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.