1

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.

DKal
  • 1,310
Freelancer
  • 187

2 Answers2

1

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

mrmowji
  • 155
  • 4
0

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

Samrat Mukhopadhyay
  • 16,277