Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I know this problem is familiar to "the number of binary strings of length $n$ with no consecutive zeros" but still it is a way different problem. But in that question the alphabet is set to $\{0,1\}$ and here:
Q:
Let $A=\{0,1,2\}$ be an alphabet, what is the the number of possible strings of length $n$ with no consecutive zeros in it?
This is a general way that you can apply to this kind of problems (I'll call the strings with no consecutive $0$'s, good strings.):
Let's denote the number of good strings of length $n$ with $a_n$, and let's define $b_n$ and $c_n$ to be the number of good strings starting with $0$ and starting with something other than $0$, respectively. So $a_n=b_n+c_n$.
Now, if a good string of length $n+1$ starts with $0$, then the string obtained by omiting the $0$, must start with something other than $0$, since no two consecutive $0$'s are allowed. Conversly, if you add a $0$ to the beginning of a good string of length $n$, starting with $1$ or $2$, then you get a good string of length $n+1$. So we have $b_{n+1}=c_n$.
Also, if a good string of length $n+1$ start with $1$ or $2$, by dropping the first element, we get a good string of length $n$. Conversly, adding $1$ or $2$ to the beginning of an arbitary good string of length $n$, results in a good string of length $n+1$. So we have $c_{n+1}=2a_n=2b_n+2c_n$.
Now combining the derived equations, we get (Note that we have those equations for any natural number $n$, so we can change the indices to any natural number we want.): $$b_{n+2}=2b_{n+1}+2b_n$$ $$c_{n+2}=2c_{n+1}+2c_n$$ Summing up: $$a_{n+2}=2a_{n+1}+2a_n$$ Now, you can use this recurrence relation for $a_n$.
It's easy to see that similar to this way, you can solve the problems in which you want to find the number of strings in any finite language, that contain no instances of some finite patterns (like $102$, $11$ or so). Just define $b_n$, $c_n$, $\dots$ in a way that fits your problem, find the relations between them and combine them to find a recurrence relation for $a_n$.
A different approach, while not generic as @Mohsen Shahriari 's.
Lets break up by the number of zero's contained in the sequence of length $n$. Suppose there are $k$ (max of $\frac{n}{2}$ when $n$ is even, $\frac{n + 1}{2}$ when $n$ is odd) zeroes. Using balls and sticks argument: We need to have some element between two $0$'s. There are $k-1$ gaps. After filling those gaps, we are left with $n - k - (k-1)$ of $1$'s and $2$'s to be filled in $k+1$ available places. This can be done in $\binom{n-2k+1 + k}{k}$ ways and $2^{n-k}$ ways to assign $1$'s and $2$'s.
Summing up, $$\sum_{k = 0}^{v}\binom{n-k+1}{k} \cdot 2^{n-k}$$ where $v=\frac{n}{2}$ (when $n$ is even) and $v=\frac{n + 1}{2}$ (when $n$ is odd)
