# How many strings of length n can be constructed with 'a', 'b', and 'c', such that there is a maximum of one 'b' and two consecutive 'c's?

I was looking at this question:

Given a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's

For instance, given n = 3, the following are valid combinations:

aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb

Someone answering the question listed n * n + (n - 1) * (n - 1) + (n + 1) as an answer, but I do not understand how it was derived.

• is ccc valid?${}$ – Jorge Fernández Hidalgo Sep 4 '16 at 1:21
• No, ccc is not valid because it has three consecutive cs – Max Sep 4 '16 at 1:21
• oh ok, but ccacc is valid? – Jorge Fernández Hidalgo Sep 4 '16 at 1:24
• Yea, I believe it is. – Max Sep 4 '16 at 1:26

Don't worry, the answer $a(n):=n^2+(n-1)^2+n+1$ is simply wrong.
Your enumeration of $19$ valid words of length $3$ is correct, since there is a total of $3^3=27$ words of length $3$ built from an alphabet $\mathcal{V}=\{a,b,c\}$ and there are eight bad words \begin{align*} \{abb,bab,bba,bbb,bbc,bcb,cbb,ccc\} \end{align*} containing more than one $b$ or more than two consecutive $c$'s and none of them is in your list of valid words. On the other hand $a(3)=17$ which is not correct.