Find all strings of length 4 over the alphabet {0, 1, 2} with the property that there are no 10, 21, or 20 substrings. What is the formula for doing this type of problems?
 A: Here we use PIE the inclusion-exclusion principle to count the number of valid $4$-letter words from the alphabet $\{0,1,2\}$ which do not contain the bad words $\{10,20,21\}$.

In order to do the job some kind of bookkeeping is helpful. We consider
  \begin{align*}
.\ .\ .\ . &-\left(10\ .\ .|20\ .\ .|21\ .\ .\right)\tag{1}\\
&+\left(10\ 10|10\ 20|10\ 21|20\ 20|20\ 21|210\ .|21\ 21\right)\tag{2}\\
\end{align*}

Comment:


*

*In (1) we count all $4$-letter words indicated by four dots which gives $3^4$. Then we subtract all words which contain at least one bad word.
Since $10$ consumes two characters and two are left for free assignment, we count $\binom{3}{1}3^2$ words of this kind and similarly in the other cases with the bad words $20$  and  $21$.

*In (2) we add words containing two bad words as compensation for those which we've subtracted twice in (1), noting that we also have to consider overlaps $21$ with $10$ giving $\color{blue}{210}$.

*No more cases are left to consider, since words containing three or more bad words have length $>4$.

We obtain according to (1) to (2):
  \begin{align*}
3^4&-\left(\binom{3}{1}3^2+\binom{3}{1}3^1+\binom{3}{1}3^1\right)\\
&\quad+\left(\binom{2}{2}3^0+2\binom{2}{2}3^0+2\binom{2}{2}3^0+\binom{2}{2}3^0+2\binom{2}{2}3^0+\binom{2}{1}3^1
+\binom{2}{2}3^0\right)\\
&=81-(27+27+27)+(1+2+2+1+2+6+1)\\
&=81-81+15\\
&\,\,\color{blue}{=15}
\end{align*}

A: Hint. The first letter is $0$, $1$ or $2$. Apart from the last letter, the letters should obey the following constraints: every $1$ is followed by $1$ or  $2$ and every $2$ is followed by $2$. Just draw by hand the corresponding graph (actually a forest) and you will find the answer: 15.
