# Counting strings: Determine the number of valid strings of length n

Question: Consider strings consisting of characters, where each character is an element of {a; b; c; d}. Such a string is called valid, if it does not contain aa, it does not contain bb, it does not contain cc, and it does not contain dd. For any integer n >= 2, what is the number of valid strings of length n?

Answer: 4 * 3^(n-1)

Attempt: I took n=4 for a string for the word "baad". Since, a valid string does not have "aa" I counted the possible ways to write "baad" without haveing 2 consecutive a's.

I did this by: 2!*(3C2) and got 6. My answer is way off. I'm assuming my logic doesn't make sense. Can someone please explain to me how to logically approach this.

• Hint: the first letter can be anything. After that, you have three choices each time. – lulu Nov 25 '18 at 19:15
• @lulu I still don't get it. If the first letter is 4C1 and the 2nd letter is 3C2 because of the "aa" string, and the last letter is 1C1 that gives me 12. If I substitute n=4 to the answer equation I get 108. Do I take 5!-12 =108? This logic doesn't apply if n=6 for say the word "beldda". I dont know if I'm over thinking this or what – Toby Nov 25 '18 at 19:51
• I don't understand what you mean by "the $aa$ string". Say the string has length $2$. Then there are four candidates for the first letter and, having chosen the first letter, there are three candidates for the second. Hence the answer is $4\times 3=12$. – lulu Nov 25 '18 at 19:53
• I don't understand any of your calculations...they don't appear to be connected to the problem. Look at my calculation for length $2$. Now do it for length $3$. You should see that you again have three choices for the third character. Continue in this way. – lulu Nov 25 '18 at 19:54
• You have four choices for the first slot, then three for the second (since you can't match the first), then three for the third (since you can't match the second). Hence $4\times 3^2$. – lulu Nov 25 '18 at 20:11