1
$\begingroup$

if $d(n)$ is the number of words created by the alphabet $\{a,b,c\}$ of length $n$ that do not contain $abc$ term then write a recursive relation for $d(n)$.

I have read the same questions but there is no detailed answer for me to learn how to write the recursive relations please give me detailed answer.

$\endgroup$
1
$\begingroup$

Construct these kind of words from start or end. Let's do this from the end.

  • If we place character a at the end of the word (n-th place), then we can place all the words of length $n-1$ from alphabet {a, b, c} that do not contain abc before this a to construct a word that we want. So in this case we have $d(n-1)$ ways to do this.

  • Same thing is true if we place character b at the end of our word. So again we have $d(n-1)$ ways to do this.

  • But if we place character c at the end of our word, we must make sure that we don't have ab before this c. We have $d(n-1)$ ways to construct words of length $n-1$ that don't contain abc but we must exclude words of length $n-1$ that end with ab. For calculating the number of words of length $n-1$ that end with ab and don't contain abc, we place ab at the end and construct the prefix with d(n-3) possible words. So we have $d(n-1) - d(n-3)$ possible words for this case.

For initial values we have $d(1)=3, d(2)=9, d(3)=3^3-1=26$.

So: $d(n) = 3d(n-1) - d(n-3)$ for $n\geq 4$.

$\endgroup$
0
$\begingroup$

Clearly, $d(1)=3, d(2)=9, d(3)=26$. Now, for $n\ge 4$, I think the following should work.

Let, $e(n)$ be the number of words among the words that has a number $d(n)$ that end with $ab$. Then, $$d(n)=2e(n-1)+3(d(n-1)-e(n-1))=3d(n-1)-e(n-1)$$. Now, $e(n-1)=d(n-3)$. So, $$d(n)=3d(n-1)-d(n-3),\quad n\ge 4$$

$\endgroup$

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.