# Devise recurrence formula for restricted strings over alphabet $\left\{0,1,2\right\}$.

Let $A_n$ denote set of strings over characters $\left\{0,1,2\right\}$ of length $n$ which do not contain substring $22$. Moreover let $B_n$ denote set of strings which both do not contain substrings $21$, $22$ and do not end with $2$.

1. Find out how many of $2$ characters at most could strings from $A_n$ and $B_n$ contain. Then combinatoricaly devise nonrecurrent formulae for cardinalities $a_n = \lvert A_n \rvert$ and $b_n = \lvert B_n \rvert$.
2. Devise recurrent formulae for $a_n$ and $b_n$. For these two linear equations with constant coefficients figure out initial conditions and solve them.

I see that most dense $A_n$ strings follow $2␣2␣2…$ pattern, so there will be $\left \lceil{\frac{n}{2}}\right \rceil$ $2$’s in string of length $n$. $B_n$ strings looks like $202020…$, so there will be $\left \lfloor{\frac{n}{2}}\right \rfloor$ $2$’s in string of length $n$.

But how do I make formulae out of this observation?

As you know $$A_0 = \left\{ε\right\}$$ $$A_1 = \{0, 1, 2\}$$ initially then we can define the recurrence relation for A like this:

$$A_n = \{x.y\ |\ x\in A_{n-1}, y \in \{0,1\}\} \cup \{x.y.\{2\} | x \in A_{n-2}, y\in\{0,1\}\}$$ where .(dot) is concatenation operator

lets think why;
a string in $A_n$ must end with a $0$, $1$ or $2$ so we can add $0$ and $1$ directly without violating the rule for $A_n$ but we can add $2$ only after adding one of $\{0,1\}$

so

$$a_n = 2a_{n-1} + 2a_{n-2}$$ and if you solve that relation:

$$x^2 = 2x + 2$$ $$x = 1\mp\sqrt{3}$$

so you get: $$a_n = c_1*(1+\sqrt{3})^n + c_2*(1-\sqrt3)^n$$ and we know that $a_0=1, a_1=3$ you can solve this equation to get values for $c_1$ and $c_2$

you can solve the $B$ part of the problem by the same logic if you run into any trouble ask again :)

• Thank you very much for such a concise reply. Looking at your solution it seems to be natural, yet I have to admit I struggle big time trying to apply the same steps on the second case. I see there are blocks of "0", "1" and "20" which has to be arranged to form a string of given length, but rest is slipping through my hands when I am trying to formalize it. – Mr. Tao Dec 12 '13 at 5:46