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:


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.

  • $\begingroup$ is ccc valid?${}$ $\endgroup$ – Jorge Fernández Hidalgo Sep 4 '16 at 1:21
  • $\begingroup$ No, ccc is not valid because it has three consecutive cs $\endgroup$ – Max Sep 4 '16 at 1:21
  • $\begingroup$ oh ok, but ccacc is valid? $\endgroup$ – Jorge Fernández Hidalgo Sep 4 '16 at 1:24
  • $\begingroup$ Yea, I believe it is. $\endgroup$ – 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.


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.