Why it matters: The counting questions are the easiest marks in Discrete Maths: permutations with restrictions, distributions, pigeonhole, derangements and one recurrence or generating function per paper.
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Number of solutions / ways to distribute
Stars and bars after removing lower bounds; subtract cases that violate an upper bound by inclusion–exclusion.
★★★
Solve or evaluate a recurrence
Characteristic equation, or unroll a few terms and spot the pattern.
★★★
Pigeonhole: minimum number to guarantee something
Worst case: fill every box to m−1, then add one.
★★★
Derangements / inclusion–exclusion / φ(n)
Plug in the formula; known values D₄ = 9, D₅ = 44.
★★★
Counting with restrictions (words, seating, committees)
Glue items that must be together, count the gaps for items that must be apart.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
17 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
17 questions · 0 correct of 0 attempted · marks 0 / 26
Year:
GATE 2025 CS1 · Q30NAT1 mark
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 ______.
GATE 2024 CS2 · Q15MCQ1 mark
Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n−1) − 6T(n−2) for n ≥ 2. Which one of the following statements is TRUE?
GATE 2023 · Q15MCQ1 mark
The Lucas sequence Lₙ is defined by the recurrence relation: Lₙ = Lₙ₋₁ + Lₙ₋₂, for n ≥ 3, with L₁ = 1 and L₂ = 3. Which one of the options given is TRUE?
GATE 2023 · Q48MCQ2 marks
Let U = {1, 2, …, n}, where n is a large positive integer greater than 1000. Let k be a positive integer less than n. Let A, B be subsets of U with |A| = |B| = k and A ∩ B = ∅. We say that a permutation of U separates A from B if one of the following is true: all members of A appear in the permutation before any of the members of B; or all members of B appear in the permutation before any of the members of A. How many permutations of U separate A from B?
GATE 2022 · Q32NAT1 mark
The number of arrangements of six identical balls in three identical bins is ______.
GATE 2022 · Q36MCQ2 marks
Which one of the following is the closed form for the generating function of the sequence {aₙ}ₙ≥0 defined below? aₙ = n + 1 if n is odd, and aₙ = 1 otherwise.
GATE 2022 · Q51MSQ2 marks
Consider the following recurrence: f(1) = 1; f(2n) = 2f(n) − 1 for n ≥ 1; f(2n + 1) = 2f(n) + 1 for n ≥ 1. Then, which of the following statements is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q19NAT1 mark
There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: the fastest computer gets the toughest job and the slowest computer gets the easiest job; every computer gets at least one job. The number of ways in which this can be done is ______.
GATE 2020 · Q42NAT2 marks
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L's are indistinguishable, is ______.
GATE 2018 · Q1MCQ1 mark
Which one of the following is a closed form expression for the generating function of the sequence {aₙ}, where aₙ = 2n + 3 for all n = 0, 1, 2, …?
GATE 2017 Set 1 · Q47NAT2 marks
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.
GATE 2017 Set 2 · Q47NAT2 marks
If the ordinary generating function of a sequence {aₙ} (n ≥ 0) is (1 + z)/(1 − z)³, then a₃ − a₀ is equal to ______.
GATE 2016 Set 1 · Q2MCQ1 mark
Let aₙ be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for aₙ?
GATE 2016 Set 1 · Q26NAT2 marks
The coefficient of x¹² in (x³ + x⁴ + x⁵ + x⁶ + …)³ is ______.
GATE 2014 Set 2 · Q48NAT2 marks
The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______.
GATE 2014 Set 2 · Q49NAT2 marks
The number of distinct positive integral factors of 2014 is ______.
GATE 2012 Code A · Q16MCQ1 mark
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
Common traps
Order or not? A committee is C(n,r); a president, treasurer, secretary is P(n,r).
Circular arrangements divide by n (rotations are the same): (n−1)!, and for necklaces that can flip, (n−1)!/2.
Stars and bars needs identical objects. For distinct objects the count is kⁿ.
Pigeonhole gives a lower bound on the fullest box, found with the evenest spread.
"At least one" is usually total minus none: do not enumerate cases.