1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Why can't the second digit be 2? $\endgroup$ – Samuel Apr 12 '16 at 17:49
  • $\begingroup$ @Samuel. That was careless of me. Now fixed, I hope. $\endgroup$ – almagest Apr 12 '16 at 19:35
  • $\begingroup$ Can you explain the first equation? $\endgroup$ – Samuel Apr 12 '16 at 20:26
  • $\begingroup$ $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...). $\endgroup$ – almagest Apr 12 '16 at 20:29
  • $\begingroup$ Perfect :) Thanks a lot!! $\endgroup$ – Samuel Apr 12 '16 at 22:02

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.