GATE CS 2025 Set 1 Q.30: Combinatorics, Counting, Recurrence Relations and Generating Functions

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)

Your answer

Official answer and solution

Official answer: 195
From: Official GATE 2025 answer key

Solution

Subtract the number of length-5 ternary strings with no two adjacent identical characters from the total number of length-5 ternary strings.

Total ternary strings of length 5: Since each of the $5$ positions has $3$ choices ( $a, b,$ or $c$ ), there are $3^5 = 243$ strings in total.
Strings with NO two consecutive identical symbols:
- Position 1 can be any of the $3$ symbols.
- Each of positions 2, 3, 4, and 5 can be any of the $2$ symbols different from the immediately preceding symbol.
- Count $= 3 \times 2^4 = 3 \times 16 = 48$ .
Strings with at least one occurrence of aa, bb, or cc:

243 - 48 = 195

Final answer

195

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 30 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source