1

Derive a recurrence relation for the number of length $n$ sequences of the English Alphabet (upper-case) not containing the words $DOG$.

How would I do this using both methods (one where it directly tackles the problem,and the other being finding the total subtracted by words containing $DOG$)?
The second method seems harder actually, since if I start the sequence with $D$, I need to find the number of $n-1$ sequences which contain the word $"OG"$ i think...

Natash1
  • 1,379

1 Answers1

2

Let $a_n$ be the number of length $n$ sequences of the English Alphabet that don't contain the word $DOG$. Now, adding any letter except $D$ to the beginning of an $n-1$ length sequence that doesn't containg $DOG$, will not contain the word $DOG$. The tricky case is when you add a $D$.

So how many $n-1$ length sequences are there that don't contain $DOG$, and don't start with $OG$? Let's say $b$ is the number of $n-1$ length sequences that do start with $OG$ and don't contain $DOG$. Then our answer is $a_{n-1}-b$.

But what is $b$? $b$ is precisely $a_{n-3}$ because the first two letters are already determined, and we just need to know how many $n-3$ length sequences don't contain $DOG$, to fill up the remaining letters.

In total, we have that $$a_n=25a_{n-1} + (a_{n-1}-a_{n-3})=26a_{n-1}-a_{n-3}$$

and $$a_0=1,$$ $$a_1=26,$$ $$a_2=26^2.$$ The base values are easy because none of the words are long enough to contain $DOG.$

miracle173
  • 11,049
Riley
  • 2,747
  • Ahh that makes a lot of sense.
    A small thing: when you say "So how many $n-1$ length sequences are there that don't contain $DOG$ and don't start with $OG$?"
    Wouldn't another way to think of it be: $25 \times 26 \times a_{n-3}$?
    Since consider the string of $n-1$ letters. There's $25$ choices for first letter not being $O$, and second letter being anything ($26$ choices), then there are $n-3$ letters remaining, where we don't want $DOG$ to appear, so $a_{n-3}$.     – Natash1 Oct 15 '17 at 04:36
  • 1
    I don't think that reasoning is entirely valid. Consider this: One of your $25$ choices other than $O$ is $D$. And one of your $26$ choices for the second letter is $O$. Then let's say the rest of the string is just $n-3$ $G$'s in a row. Well you are counting this as a sequence that doesn't contain $DOG$. But it does contain $DOG$ in the beginning. – Riley Oct 15 '17 at 04:40
  • Ah I see it now. If I attempted to go down this way, there would be a point where I'd form more recurrence relations right? Since I always have to check the case when first letter is $D$ or not, 2nd letter is $O$ or not etc – Natash1 Oct 15 '17 at 04:43
  • what are the start values for this recurrence? – miracle173 Oct 15 '17 at 04:45
  • @miracle173 $a_0=1$, $a_1=26$, $a_2=26^2$ The base values are easy because none of the sequences are long enough to contain $DOG$ – Riley Oct 15 '17 at 04:47