GATE CS 2025 Set 1 Q20 — Combinatorics: Counting, Recurrence Relations, Generating Functions

To find the number of ternary strings of length $5$ over the alphabet $\{a, b, c\}$ that contain at least one occurrence of consecutive identical symbols (i.e., "aa", "bb", or "cc"), we can use the principle of complementation.

Step 1: Calculate the total number of ternary strings of length 5

Since each position in a string of length $5$ can be filled by any of the $3$ symbols $\{a, b, c\}$, the total number of ternary strings is: $$\text{Total} = 3^5 = 243$$

Step 2: Calculate the number of strings with no consecutive identical symbols

Let us construct a string of length $5$ where no two adjacent symbols are the same:

• The $1^{\text{st}}$ character can be any of the $3$ symbols: $3$ choices.
• The $2^{\text{nd}}$ character must be different from the $1^{\text{st}}$ character: $2$ choices.
• The $3^{\text{rd}}$ character must be different from the $2^{\text{nd}}$ character: $2$ choices.
• The $4^{\text{th}}$ character must be different from the $3^{\text{rd}}$ character: $2$ choices.
• The $5^{\text{th}}$ character must be different from the $4^{\text{th}}$ character: $2$ choices.

Step 3: Calculate the required number of strings

Subtracting the complement from the total number of strings: $$\text{Required Strings} = \text{Total} - \text{Complement} = 243 - 48 = 195$$