How many 20 digits numbers can be written by using $1,2,3$, which doesn't include $11$,$23$ sequence?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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