The GATE Grind

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

Count the complement: strings of length 5 over $\{a,b,c\}$ with **no** two equal adjacent symbols.

Strings with no equal neighbours $=3\cdot2^4=48$. All strings $=3^5=243$.

Strings containing at least one of `aa`, `bb`, `cc` $=243-48=\mathbf{195}$.

More Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions

All Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions →