Recursion problem - ternary words not containing 121
Let's do it recursively, for all lengths $n$.
We let $T_n$ be the number of "good" words of length $n$.
Let $A_n$ be the number that of good words of length $n$ that end in $12$.
Let $B_n$ be the number that of good words of length $n$ that end in $1$.
Let $C_n$ be the number that of good words of length $n$ that end in anything other than $1$ or $12$.
Of course $$T_n=A_n+B_n+ C_n$$
We note that $$A_n=B_{n-1}\quad B_n=B_{n-1}+C_{n-1}\quad C_n=2A_{n-1}+B_{n-1}+2C_{n- 1}=2T_{n-1}-B_{n-1}$$ As we clearly have $$A_1=0\quad B_1=1\quad C_1=2$$ this is easy to implement . Barring error the first few $T_n$ are $$\{3,9,26,75,217,628,1817,5257,15210,\cdots\}$$ In particular $T_7=\fbox {1817}$
Sanity check: let's compute $T_4$ by hand. The bad words are $121*$ and $*121$ hence there are $6$ bad words, so $T_4=81-6=75$ as predicted. Similarly to compute $T_5$ we eliminate $9$ words of the form $121**$, $9$ words of the type $*121*$ and $9$ of the type $**121$, noting that we have eliminated $12121$ twice. Hence $T_5=3^5-27+1=243-26=217$ as desired.
I think these cases cover the complement set:
- Words containing $121$ exactly once
- Words containing $121$ twice without overlap, but not $1212121$
- Words containing $12121$, but not $1212121$
- Words containing $1212121$ (this one's easy)
Can you take it from here?
Partition strings into 4 types:
- (A) Strings containing a 121
- (B) Else, strings ending in 12
- (C) Else, strings ending in 1
- (D) All other strings
Let $M_{i, j}$ be the number of ways a string in state $i$ can transtion into state $j$ by appending a single character. Example, $M_{B, D}=2$, because xxxx12 can become a (D) type string in two ways: by appending a 2 (xxxx122) or appending a 3 (xxxx123), but not by appending a 1 because xxxx121 is an (A) type string.
Those transitions can be recorded in a matrix:
$$M = \left[ \begin{array} {r|cccc} & A & B & C & D \\ \hline A & 3 & 0 & 0 & 0 \\ B & 1 & 0 & 0 & 2 \\ C & 0 & 1 & 1 & 1 \\ D & 0 & 0 & 1 & 2 \\ \end{array} \right]$$
The number of transitions over 7 characters is $M^7$:
$$M^7 = \left[ \begin{array} {r|cccc} & A & B & C & D \\ \hline A & 2187 & 0 & 0 & 0 \\ B & 931 & 134 & 388 & 732 \\ C & 564 & 173 & 501 & 949 \\ D & 370 & 194 & 561 & 1062 \\ \end{array} \right]$$
The number of strings containing 121 is $M^7{}_{D, A} = 370$; so the number of strings not containing it is $3^7 - 370 = M^7{}_{D, B} + M^7{}_{D, C} + M^7{}_{D, D} = 194 + 561 + 1062 = 1817$.