This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this recursive function? I have an exam on Thursday and I am struggling with the concept of finding the recursive definition for strings. Can someone explain how this works and give few examples to make it clear? Thank you.
2 Answers
Given a string of length $n-1$, you can add any of $0$, $1$, or $2$ to the end of it to get a string of length $n$, so you get $3 a(n-1)$ strings. However, if the last two elements of the original string were $01$, then adding $2$ is not allowed. How many such strings are there? Well, they are found by noting that after removing the $01$ you have an arbitrary string of length $n-3$. So you must subtract $a(n-3)$ to avoid counting these.
More visually, \begin{align*} \underbrace{...0}_{n-1} &\quad\Rightarrow\quad ...00,\ ...01,\ ...02 \\ \underbrace{...1}_{n-1} &\quad\Rightarrow\quad ...10,\ ...11,\ ...12 \\ \underbrace{...2}_{n-1} &\quad\Rightarrow\quad ...20,\ ...21,\ ...22 \end{align*} so that every length $n-1$ string gives nine length $n$ strings. If the original string didn't contain $012$, neither will the new one, except for the last entry on the second row. If that length $n-1$ string ended in $01$, then we will have created a $012$ in the new string. But if that string ended in $01$, then the other digits in the string (there are $n-3$ of them) are arbitrary. So there are $a(n-3)$ ways in which we could have erroneously added the $012$. We must subtract that to get the right answer.
So for example $a(3) = 3a(2) - a(0) = 26$, $a(4) = 3a(3) - a(1) = 75$.
$a_n=2a_{n-1}+b_{n-1}$
$b_n=b_{n-1}+c_{n-1}+a_{n-1}$
$c_n=a_{n-1}+b_{n-1}$
Explanation:
-First relation:
$2a_{n-1}$ indicates sequences starting by 1... or 2... while the relation $a$ is for unconstrained sequences
$b_{n-1}$ indicates 0... while $b$ is a sequence right-bounded by a $0$
-Second relation:
$c_{n-1}$ indicates 01... while $c$ is any sequence right-ended by $0...1$
$b_{n-1}$ indicates 00... while $a_{n-1}$ indicates 02...
-Third relation:
$a_{n-1}$ indicates 011... and $b_{n-1}$ points to 010...
Example:n=3 (xxx)
Naive enumeration says $S=3*3*3-1=26$ where the subtracted case is 210
Recursive enumeration:
$a_3=2a_2+b_2=2(2a_1+b_1)+b_2=2(2(2a_0+b_0)+b_1)+b_2=8a_0+4b_0+2b_1+b_2$
$b_1=b_0+c_0+a_0=3$
$b_2=b_1+c_1+a_1$
$c_1=a_0+b_0=2$
$a_1=3$
$b_2=3+2+3=8$
$a_3=8+4+8+6=26$
Example2:n=4 (xxxx)
-From informations above, $a_3=26,a_2=9,b_2=8,a_1=3,b_1=3$
$a_4=2a_3+b_3=2*26+b_3$
$b_3=b_2+c_2+a_2=8+c_2+9$
$c_2=b_1+a_1=3+3=6$
$b_3=23$
$a_4=52+23=75$ which matches previous results.
-
-
$\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$– NizarFeb 10, 2016 at 9:02
-
$\begingroup$ @Nizar ll clarify my intervention with examples hold on, i thought it can be understood at first look $\endgroup$– Abr001amFeb 10, 2016 at 9:06
-
$\begingroup$ vtd + 2dvts because reviewers are failing to understand my approach, too bad, deplorably bad $\endgroup$– Abr001amFeb 10, 2016 at 11:35
-
$\begingroup$ I agree, the answer is indeed deplorably bad. $\endgroup$ Feb 10, 2016 at 12:27