String numbers with $\{0,1,2\}$ My answer here is $405$... but Im wondering if my answer is correct or not. Any idea?
QUESTION: how many string composed of 6 numbers can be formed from $\{0,1,2\}$ without having $(0,1,2), (1,0,2)$ and $(2,0,1)$ in any part of the string
 A: Denote by $x_{ik}(n)$ the number of admissible strings of length $n\geq2$ having $ik$ as last two figures, and collect these numbers in the vector
$$x(n)=\bigl(x_{00}(n),x_{01}(n),x_{02}(n),x_{10}(n),x_{11}(n),x_{12}(n),x_{20}(n),x_{21}(n),x_{22}(n)\bigr)\ .$$
Then $x(2)=(1,1,\ldots,1)$. Considering $x(n)$ as a row vector we have the recursion
$$x(n+1)=x(n)\>A\qquad(n\geq2)$$
where $A$ is a $9\times9$ matrix encoding the forbidden and the allowed transitions from one pair $ik$ to some other pair $kl$. Since all transitions $ik\to kl$, except $01\to12$, $10\to 02$, $20\to01$, are allowed this matrix looks as follows:
$$A=\left[\matrix{
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\cr
0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\cr
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\cr
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0\cr
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\cr
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\cr
0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0\cr
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\cr
}\right]\ .$$
Using Mathematica we then find
$$x(6)=x(2)\>A^4=(64, 45, 43, 57, 57, 40, 50, 50, 50)\ .$$
The sum of the $x_{ik}(6)$ is $456$, as obtained by @diracdeltafunc.
