0
$\begingroup$

Let $A = {a,b,c}$ be the alphabet to use for the words. Number words of length n which contain the sequence $(aa)$ at least once.

$n = 0$ and $n = 1$ yield no words, because they do not contain $(aa)$. So we can start with $n = 2$

There are $n-1$ possibilities for the position of the $aa$. We have $n-2$ remaining letters, for which each has three possibilities for a letter.

I come to the conclusion that the formula must be $(n-1) \cdot 3^{n-2}$

I'm not sure about this and I wonder if there is a cleaner approach, maybe a recurvive approach?

$\endgroup$
4
  • $\begingroup$ The $3(n-2)$ part should be $3^{n-2}$ $\endgroup$ – turkeyhundt Jan 19 '15 at 9:05
  • $\begingroup$ Your approach would count $aabaa$ twice, and $aaaaa$ four times, and therefore give you the wrong answer for $n=5$. $\endgroup$ – Arthur Jan 19 '15 at 9:15
  • $\begingroup$ But I don't think it's as simple as that formula because it would count, say, $aaa$ multiple times. $\endgroup$ – turkeyhundt Jan 19 '15 at 9:15
  • $\begingroup$ thank you for your comments, I've altered the formula :) $\endgroup$ – warg Jan 19 '15 at 10:08
2
$\begingroup$

Hint:

Denote the number of words of length $n$ that do not contain sequence $aa$ by $p_{n}$ and split up:$$p_{n}=q_{n}+r_{n}$$ Here $q_{n}$ stands for words of length $n$ that do not contain $aa$ and have $a$ as first letter and $r_{n}$ stands for words of length $n$ that do not contain $aa$ and do not have $a$ as first letter.

Then we have the recursion relations: $$r_{n+1}=2p_{n}\text{ and }q_{n+1}=r_{n}$$ There are $3^{n}$ words of length $n$ so you are actually looking for $3^{n}-p_{n}$.

$\endgroup$
2
  • $\begingroup$ thanks, this helped a ton. $\endgroup$ – warg Jan 19 '15 at 10:08
  • $\begingroup$ Glad I could help. You are very welcome. $\endgroup$ – drhab Jan 19 '15 at 10:14

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.