What is the number of series $(x_1,x_2,x_3,x_4,x_5,x_6,x_7) \in \{0,1,2\}^7$ that do not contain the sequence $010$ in any three consecutive places?

Question

What is the number of series $(x_1,x_2,x_3,x_4,x_5,x_6,x_7) \in \{0,1,2\}^7$ that do not contain the sequence $010$ in any three consecutive places?

Hello! I have the following question in my assignment. I managed to solve it using inclusion- exclusion principle, but it was a very tedious process.

Is there any elegant way to solve this?

if not, for practice I would like to solve it with generating functions as well, but I was not sure how, so a hint on how to look at this question in a generating function approach would be highly appreciated!

Thanks!

Answer 1

Hint: A technique to solve such problems is the Goulden-Jackson Cluster Method.

We consider the set words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1,2\}$$ and the set $B=\{010\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^n$ being the number of searched words of length $n$.

A proof providing the solution $\color{blue}{1\,817}$ valid words of length $7$ which do not contain $010$ is given here. We can take the proof as it is, simply replacing every occurrence of the bad word $121$ with $010$ there.