# Recurrence relation to find ternary strings of length $n$ that do not contain $3$ consecutive $0$'s or $2$ consecutive $1$'s

OK my idea is that the total number of possible ternary strings of length $n$ is $3^n$, of which I must subtract the strings containing $000$s plus the strings containing $11$s, excluding the number of duplicates (strings containing both $000$s and $11$s).

Sequence for strings containing 000s: $$f(n)=3\times f(n-1)+2\times(3^{n-4}-f(n-4))$$ Sequence for strings containing 11s: $$f(n)=3\times f(n-1)+2\times(3^{n-3}-f(n-3))$$

Now for the strings containing both sequences: For $n=5$ we get $2$ ($00011$ and $11000$).

For $n=6$ we get $12$ and for $n=7$ we get $73$ (just by producing the permutations).

For $n>5$, I understand we must consider two different cases, the first (or last) $5$ digits forming a "good" sequence (i.e. containing both sequences), in which case, the remaining $n-5$ can be anything (thus giving us $3^{n-5}$ more combinations, or $f(n-1)$ being "bad".

In this case, how do we distinct whether it contains only $000$s or $11$s or none of the two?

In short, how do we find the recurrence relation for the strings to contain both?

Let $f(n)$ be the number of strings starting with 0, $g(n)$ the number starting with 1, $h(n)$ the number starting with 2.

We have $f(n+1)=g(n)+h(n)+g(n-1)+h(n-1)$ (nos. starting 01,02,001,002 resp).

$g(n+1)=f(n)+h(n)$ (nos. starting 10,12 resp).

$h(n+1)=f(n)+g(n)+h(n)$ (nos. starting 20, 21, 22 resp).

Subs 2nd equ in other two we get:

$f(n+1)=f(n-1)+h(n-1)+h(n)+f(n-2)+h(n-2)+h(n-1)=f(n-1)+f(n-2)+h(n)+2h(n-1)+h(n-2)$ (*) and

$h(n+1)=f(n)+f(n-1)+h(n-1)+h(n)$ and hence $h(n)=f(n-1)+f(n-2)+h(n-1)+h(n-2)$ (**)

Subs (**) in (*) we get: $f(n+1)=2h(n)+h(n-1)$. Subs that in the equ for $h(n+1)$ gives $h(n+1)=2h(n-1)+h(n-2)+2h(n-2)+h(n-3)+h(n-1)+h(n)$ or

$h(n+1)=h(n)+3h(n-1)+3h(n-2)+h(n-3)$.

Note that $h(n+1)$ is also the total number of strings of length $n$ - because it is $f(n)+g(n)+h(n)$.

So writing $t(n)$ for the total number of strings of length $n$ we have:

$t(n+1)=t(n)+3t(n-1)+3t(n-2)+t(n-3)$. It is easy to list the possible strings for small $n$ to get $t(1)=3, t(2)=8, t(3)=21, t(4)=55$.

• Why can't the second digit be 2? – Samuel Apr 12 '16 at 17:49
• @Samuel. That was careless of me. Now fixed, I hope. – almagest Apr 12 '16 at 19:35
• Can you explain the first equation? – Samuel Apr 12 '16 at 20:26
• $f(n+1)=g(n)+h(n)+...$. Here $g(n)$ counts the number of strings length $n+1$ that start 01... , $h(n)$ counts the number of strings length $n+1$ that start 02 etc. Any string length $n+1$ starting with 0 must be one of 01..., 02... , 001... and 002... (because it cannot be 000...). – almagest Apr 12 '16 at 20:29
• Perfect :) Thanks a lot!! – Samuel Apr 12 '16 at 22:02