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\}$


$$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 :)

  • $\begingroup$ 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. $\endgroup$ – Mr. Tao Dec 12 '13 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.