Find the number of strings that only contains $0,1,2$ of length $n$ that do not contain $102$ as a substring

combinatoricsrecurrence-relations

I'm confused with the problem: using the recursive formula, find the number of strings that only contains $0,1,2$ of length $n$ that do not contain $102$ as a substring

There is my attempt:
Suppose $h_n$ is the number of legal strings. I look at this string from the end of it. Suppose the string ends with $1$ or $0$, then as long as the first $n-1$ string doesn't contain $102$, then after I add $1$ or $0$ at the end, the string still doesn't have $102$. Thus we have $$\begin{align*}
2 h_{n-1}
\end{align*}$$ strings now.

Then I consider if I add $2$ to the end of the string. If the string looks like $$\begin{align*}
\cdots |1,-
\end{align*}$$ where I use $-$ denote the empty position.
Then as long as $\cdots$ parts don't contain $102$, I can put $2$ at the end. There's $h_{n-2}$ strings.
However, when I have a string that looks like $$\begin{align*}
\cdots |2- \\ \cdots |0-
\end{align*}$$ I can assume the first $n-2$ string is a legal string, but I can't say I will have $h_{n-2}$ strings since the case can be $$\begin{align*}
\cdots 10|2- \\ \cdots 1|0-
\end{align*}$$ These 2 cases both ensure that the first $n-2$ strings don't contain $102$, but the first one is already illegal, and the second one will be illegal after I put $2$ at the end.

Any help on this? Thanks

Best Answer

Couldn't really follow from $

Let $a_n$ denote the number of strings of length $n$ that end with a $10$. (This is important since after concatenating $2$, we get an illegal string). For $h_{n-1}-a_{n-1}$ strings (of length $n-1$), we can concatenate $0,1$ or $2$ to get strings of length $n$. For $a_{n-1}$ strings, we can contenate $0,1$. This gives: $$h_n = 3(h_{n-1}-a_{n-1})+2a_{n-1} = 3h_{n-1} - a_{n-1}$$

Now, we need a formula for $a_n$. In a string that ends with a $10$, if we remove the last two terms, we must get a legal string of length $n-2$. Thus, $a_n = h_{n-2}$. Applying this, we get:

$$\boxed{h_n = 3h_{n-1}-h_{n-3},\ h_0 = 1,\ h_1 = 3,\ h_2 = 9}$$ where $h_0 = 1$ comes in order to get $h_3 = 26$.

The first $10$ values of $h_n$ (from $1$ till $10$) are $3,9,26,75,216,622,1791,5157,14849,42756$, verified using this python code:

n = int(input("Enter n\n"))
a = [""]*(3**n)
b = 0
r = 0
s = ""
for i in range(1,3**n):
    c = i
    while(c>0):
        r = c%3
        s = str(int(r))+s
        c = (c-r)/3
    a[i] = s
    s = ""
for j in range(0, len(a)):
    if "102" in a[j]:
        b =b
    else:
        b = b+1
print(b)
Related Question