Find the number of four-letter words that use letters from {A, B, C} in which no three consecutive letters are the same.

combinatoricsdiscrete mathematics

Case 1: (3)(3)(2)(3)=54. In the first two spots the letters can be any of A,B, or C. The third spot is where we risk having a third consecutive letter, so there are only 2 choices. Now the fourth spot can be either of the three letters.

Case 2: (3)(2)(3)(3)=54. Similar to case 1, this is the only other way to prevent three consecutive letters from occurring.
So there are 54+54=108 different words. Please check if my reasoning makes sense.

Best Answer

A better approach is to discard cases that do not work from the total. There are a total of $3^4 = 81$ four-letter words with letters $A, B, C$. From these,

  • $3$ words have only $1$ letter: $AAAA$, $BBBB$ and $CCCC$.
  • Words with $3$ consecutive letters equal and one different: $3 \cdot 2 \cdot 2 = 12$; here, we first choose the letter that appears $3$ times, then a different letter to be the other one, and finally notice that either the group of $3$ starts or ends the word.

So, your answer should be: $81 - 3 - 12 = 66$.

Related Question