[Math] 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

Question

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 \cdot n + (n – 1) \cdot (n – 1) + (n + 1)$ as an answer, but I do not understand how it was derived.

Answer 1

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.