Simple String of 6-digits This is the problem:

A string of 6 digits, each taken from the set $[0, 1, 2]$ is to be formed. The string should not contain any of the substrings $012$, $120$, and $201$. How many such 6-digit strings can be formed?


I really have trouble in using PIE in here. I'm badly needing some clear explanation in the PIE part because it's not what I usually deal with.
I have also a question: 'Does avoiding $000$, $111$, and $222$ instead will still gain the same result?'.
Thanks for all the help in advance :)
 A: Given a string that avoids $000,111,222$ add $i$ modulo $3$ to the $i$'th digit to obtain a string that avoids $012,120,201$.  This is clearly a bijection.
Lets consider all legitimate strings of length $3$ (e.g. those that avoid $000,111,222$):
$011, 022, 100,122,200,211$
and
$001,010,020,002,12,021,101,110,120,102,112,121,201,210,220,202,212,221$.
Notice I have written them in two lists: the first $6$ end $aa$, whilst the other $18$ end $ab$.  In my notation $a_3=18, b_3=6$.  Here $a_n$ is the number of legitimate strings which end $ab$ and $b_n$ is the number of legitimate strings which end $aa$.
Consider a string which ends $aa$ such as $011$.  What can I add to the end, so that it is still legitimate?  I cannot add $1$, but if I add $0$ or $2$ I get a string of length $4$ and ending $ab$: $0110, 0112$.
What about a string ending $ab$?  Consider $001$.  If I add $0$ or $2$ then I get a string of length $4$ ending $ab$: $0010,0012$.  On the other hand if I add a $1$ I get $0011$ which ends $aa$.
This is summed up in the diagram:

So for each string of length $n$ ending $ab$, we can get $2$ strings of length $n+1$ of type $ab$ by adding a number at the end, whilst for each string of length $n$ ending $aa$ we can get two strings of length $n+1$ ending $ab$, by adding a number at the end.  Thus for $n\geq 3$ we have: $$a_{n+1}=2a_n+2b_n.$$
Similarly, for each string of length $n$ ending $ab$ we get one string of length $n+1$ ending $aa$.  You cannot add any number to a string of length $n$ ending $aa$, to get a string of length $n+1$ ending $aa$ (as $aaa$ not allowed).  Thus for $n\geq 3$ we have: $$b_{n+1}=a_n$$
Combining the two equations, for $n\geq4$ we get:$$a_{n+1}=2a_n+2a_{n-1}$$
The total number of legitimate strings of length $n$ is $$a_n+b_n=a_n+a_{n-1}.$$
We know $a_2=6,a_3=18$. From the recursion we have $a_4=48, a_5=132, a_6=360$.
Thus there are $132+360=492$ legitimate strings.
A: You want to avoid 12 properties:
\begin{matrix}
000xxx & x000xx & xx000x & xxx000 \\
111xxx & x111xx & xx111x & xxx111 \\
222xxx & x222xx & xx222x & xxx222 \\
\end{matrix}
The inclusion-exclusion formula is $$\sum_{k=0}^{12} (-1)^k N_k,$$
where $N_k$ is an overcount of the number of $6$-strings that satisfy $k$ properties.  Clearly, $N_k=0$ for $k>4$.
We have
\begin{align}
N_0 &= \binom{12}{0} 3^6 = 729 \\
N_1 &= \binom{12}{1} 3^{6-3} = 324 \\
N_2 &= 2 \binom{3}{2} 3^{6-6} + 3 \left(3 \cdot 3^{6-4} + 2 \cdot 3^{6-5} + 1 \cdot 3^{6-6}\right) = 108 \\
N_3 &= 3 \left(2 \cdot 3^{6-5} + 2 \cdot 3^{6-6}\right) = 24 \\
N_4 &= 3 \left(1 \cdot 3^{6-6}\right) \\
\end{align}
Putting it all together, we obtain
$$729 - 324 + 108 - 24 + 3 = 492$$
