Home › Previous year questions › GATE 2025 CS (CS1) › Question 30GATE 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.
First symbol: 3 choices. Each later symbol must differ from the previous one: 2 choices each, 4 more positions. 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 GATE 2023 CS Q15 – The Lucas sequence L n is defined by the recurrence relation: L n = L n-1 + L n-2, for n… GATE 2023 CS Q48 – Let U = \1, 2, , n\, where n is a large positive integer greater than 1000. Let k be a… GATE 2022 CS Q32 – The number of arrangements of six identical balls in three identical bins is . GATE 2022 CS Q36 – Which one of the following is the closed form for the generating function of the sequence… GATE 2021 CS (CS1) Q29 – There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing… GATE 2020 CS Q52 – The number of permutations of the characters in LILAC so that no character appears in its… All Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions →