Let \(S\) be the set of all ternary strings defined over the alphabet \(\{a, b, c\}\). Consider all strings in \(S\) that contain at least one occurrence of two consecutive symbols, that is, “aa”, “bb” or “cc”. The number of such strings of length 5 that are possible is _______. (Answer in integer)
Answer
195
Explanation
Count the complement first: length-5 strings in which no two neighbouring symbols are the same. The first symbol has 3 choices and each of the next four has 2 (anything except the symbol just before it), so there are \(3 \times 2^{4} = 48\) such strings.
There are \(3^{5} = 243\) strings in all, so the number with at least one “aa”, “bb” or “cc” is \(243 - 48 = 195\).
Answer: 195