1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
-3
$\begingroup$

$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.

$\endgroup$
8
  • $\begingroup$ reason ?????????? $\endgroup$ – Abr001am Feb 10 '16 at 8:28
  • $\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$ – Nizar Feb 10 '16 at 9:02
  • $\begingroup$ @Nizar ll clarify my intervention with examples hold on, i thought it can be understood at first look $\endgroup$ – Abr001am Feb 10 '16 at 9:06
  • $\begingroup$ vtd + 2dvts because reviewers are failing to understand my approach, too bad, deplorably bad $\endgroup$ – Abr001am Feb 10 '16 at 11:35
  • $\begingroup$ I agree, the answer is indeed deplorably bad. $\endgroup$ – Tobias Kildetoft Feb 10 '16 at 12:27

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.