How many 20 digits numbers can be written by using $1,2,3$, which doesn't include $11$,$23$ sequence? I mean that for example, $13131313131313131313$ is a right construction, but $13131313131313131311$ is a wrong answer, because it includes $11$ in the end. Should I compute maybe all the wrong cases, or in which way can I solve it? I'm thinking about that I should maybe find a graph and find an adjacency matrix, but I don't know how to find this matrix.
 A: Here is a way to solve it, but I hope that someone comes up with a better answer.
Let $E_i$ denote the set of constructions where $1$ is on spot $i$ and $i+1$  and let $F_i$ denote the set of constructions where $2$ is on spot $i$ and $3$ is on spot $i+1$.
With inclusion/exclusion and symmetry we find an expression for: $$|E_1\cup\cdots\cup E_{19}\cup F_1\cup\cdots\cup F_{19}|$$
To get the answer this must be subtracted from $20^3$. 
You could make a table like:
$$\begin{array}{ccccc}
+ & \text{all} & 1 & 3^{20} & +3^{20}\\
- & |E_{1}| & 19 & 3^{18} & -19\times3^{18}\\
- & |F_{1}| & 19 & 3^{18} & -19\times3^{18}\\
+ & |E_{1}\cap E_{2}| & 18 & 3^{17} & +18\times3^{17}\\
+ & |E_{1}\cap E_{3}| & 17 & 3^{16} & +17\times3^{16}\\
+ & |E_{1}\cap E_{4}| & \binom{17}{2} & 3^{16} & +\binom{17}{2}\times3^{16}\\
+ & |E_{1}\cap F_{3}| & 2\binom{18}{2} & 3^{16} & +2\binom{18}{2}\times3^{16}\\
+ & |F_{1}\cap F_{3}| & \binom{18}{2} & 3^{16} & +\binom{18}{2}\times3^{16}\\
- & |E_{1}\cap E_{2}\cap E_{3}| & 17 & 3^{16} & +17\times3^{16}\\
- & \dots & \dots & \dots & \dots\\
\hline  &  &  &  & \text{answer}
\end{array}$$
A: Hint: we count words which do contain $11$ or $23$. 
Consider an automaton with four states $O,A,B,C$. 
It starts from $O$ and reads symbols of the word consecutively from left to right. If it is in $O$ and the next letter is $3$, it stays in $O$; if the next symbol is $1$, it goes to $A$; if $2$, to $B$. 
From $A$, it goes to $B$ if the next symbol is $2$, to $O$ if the next symbol is $3$, and to $C$, an absorbing state, if the next symbol is $1$. 
From $B$, it goes to $A$ if the next symbol is $1$, to $C$, if it is $3$, and it stays in $B$ if the next symbol is $2$. 
$C$, as I already wrote, is an absorbing state.
Now you are interested in counting ($n$-letter) words which lead you from $O$ to $C$. There are several ways to do this. First, you can regard the automaton as a Markov chain with probabilities of all letters equal to $1/3$. Then the number of words is $3^n$ times the probability to reach $C$ from $O$ in $n$ steps, which is computed in a standard manner. 
Alternatively, you can denote the language of words which lead you to $C$ from   $x$ by $\mathcal L_x$, and then write relations between the languages using your transition rules: $\mathcal L_C$ = all words, $$\mathcal L_B = 1\mathcal L_A  + 3\mathcal L_C + 2\mathcal L_B,\\ \mathcal L_A = 2\mathcal L_B  + 3\mathcal L_O + 1\mathcal  L_C,\\ \mathcal L_O = 3\mathcal L_O + 1\mathcal L_A  + 2\mathcal L_B.$$
Replacing $1,2,3$ by some variable, say, $x$, and solving for $L_O(x)$ (use that $L_C(x) = \frac1{1-3x}$), you will get a generating function for the words containing $11$ or $23$.

 You should get the answer 3471561067

A: Let's say a string is acceptable if it does not include either of the substrings $11$ or $23$.  Let $a_n$ be the number of acceptable strings of length $n$  ending in $1$, $b_n$ be the number of acceptable strings of length $n$ ending in $2$, and $c_n$ be the number of acceptable strings of length $n$ ending in $3$.  Then $a_1 = b_1 = c_1 =1$, and
$$\begin{align}
a_n &= b_{n-1} + c_{n-1}\\
b_n &= a_{n-1} + b_{n-1} + c_{n-1}\\
c_n &= a_{n-1} + c_{n-1}
\end{align}$$ for $n>1$.
From these relations you can calculate as many values of $a_n$, $b_n$ and $c_n$ as you like.  The number of acceptable strings of length $20$ is $a_{20}+b_{20}+c_{20}$.
