Simple String of 6-digits

Question

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 :)

Answer 1

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.

Answer 2

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