0
$\begingroup$

I need to solve following question:

"An alphabet consists out of 4 letters $a,b,c,d$ and 3 numbers $1,2,3$. Find the recurrence relation for the number of words of length $n$ where no two numbers are allowed to be adjacent."

This is what I came up with:

If the first character of the word is a letter, we have 4 possible choices and leaves us with $n-1$ characters left. If the first character is a number, we know the second one is not allowed to be a number as well, so we're left with 4 choices and $n-2$ left to divide.

Which gives me $a_n = 4 a_{n-1} + 4 a_{n-2}$

Not sure if this gives me the correct answer.

$\endgroup$
1
$\begingroup$

Your reasoning is on the right track, but your recurrence relation does't make sense. As you pointed out, if the first character is a letter ($4$ ways this can happen), then we can have any valid word of length $n-1$ to complete the word. That gives us $4a_{n-1}$ words of this type. Now, if the first character is a number ($3$ ways this can happen,) then the next character must be a letter ($4$ ways this can happen), and the remaining $n-2$ characters can be filled with any valid word of length $n-2$. That gives us $12a_{n-2}$ words of this type. There are no other ways to make a valid word of length $n,$ so $$a_n=4a_{n-1}+12a_{n-2}.$$

$\endgroup$
0
$\begingroup$

A sure win in these situations is to consider separately the number $L_n$ of words of length $n$ ending with a letter and the number $N_n$ of words of length $n$ ending with a number, so that one is after the total number $W_n=L_n+N_n$ of words of length $n$.

Then $L_1=4$, $N_1=3$, and considering the ways to complete words of length $n$ of each type to get words of length $n+1$ of each type, one sees that $L_{n+1}=7L_n+7N_n$ and $N_{n+1}=7L_n+4N_n$.

Can you take on from here?

$\endgroup$
1
  • $\begingroup$ Yes that should do the trick, thanks! $\endgroup$ – RazorAlliance192 Aug 21 '13 at 16:54

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.