GATE 2025 CS (CS1) – Question 30

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 1 mark · Numerical answer

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)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 195

Explanation

Total strings are 3^5 = 243. Strings with no equal adjacent symbols number 3·2^4 = 48. So 243 - 48 = 195.