The GATE Grind

GATE Engineering Mathematics: Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) – Previous Year Questions

31 GATE previous year questions on Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) (Engineering Mathematics, Computer Science) with answers and explanations, from every paper.

31 questions worth 53 marks in all (9 1-mark, 22 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q84 (2 marks, Multiple choice) – A robot starts on the Cartesian plane. At each step (i, j) it moves either to(i+1, j) or(i, j+1). How many paths reach(10, 10) from(0, 0)?
  2. GATE 2007 CS Q85 (2 marks, Multiple choice) – A robot starts on the Cartesian plane. At each step (i, j) it moves either to(i+1, j) or(i, j+1). It may not traverse the segment(4, 4)→(5, 4). How…
  3. GATE 2008 CS Q24 (2 marks, Multiple choice) – Let P= 1 i2k,\ i oddi and Q= 1 i2k,\ i eveni, where k is a positive integer. Then
  4. GATE 2008 CS Q78 (2 marks, Multiple choice) – Let xₙ count n-bit binary strings with no consecutive0s. Which recurrence holds?
  5. GATE 2008 CS Q79 (2 marks, MTA) – Let xₙ count n-bit binary strings containing no consecutive0s, using the recurrence in Q78. What is x₅?
  6. GATE 2021 CS (CS2) Q60 (2 marks, Numerical answer) – S has ten elements. How many ordered tuples (A,B) of subsets of S satisfy A⊆B?
  7. GATE 2015 CS (CS3) Q25 (1 mark, Numerical answer) – How many four-digit numbers using only 1,2,3 have digits in nondecreasing order from left to right?
  8. GATE 2015 CS (CS2) Q14 (1 mark, Numerical answer) – How many positive divisors does 2100 have?
  9. GATE 2015 CS (CS2) Q58 (2 marks, Numerical answer) – How many onto functions map X=1,2,3,4 to Y=a,b,c?
  10. GATE 2010 CS Q37 (2 marks, Multiple choice) – A divisor of 1099 is chosen uniformly at random. What is the probability that it is a multiple of 1096?
  11. GATE 2012 CS Q47 (2 marks, Multiple choice) – How many surjections exist from an n-element set (n≥2) to a two-element set?
  12. GATE 2017 CS (CS2) Q57 (2 marks, Numerical answer) – The ordinary generating function of aₙ is (1+z)/(1-z)3. Find a₃−a₀.
  13. GATE 2016 CS (CS2) Q39 (2 marks, Numerical answer) – Evaluate 1399 17 as an integer from 0 through 16.
  14. GATE 2014 CS (CS2) Q59 (2 marks, Numerical answer) – Find the number of distinct positive integer factors of 2014.
  15. GATE 2014 CS (CS1) Q47 (2 marks, Numerical answer) – Five bags labelled 1–5 each contain equal-weight coins within the bag; some bags have 10 g coins and others 11 g coins. Taking 1,2,4,8,16 coins…
  16. GATE 2014 CS (CS1) Q59 (2 marks, Numerical answer) – A pennant is an ordered sequence of 1s and 2s; an n-pennant has sum n. For example (1,1,2) is a 4-pennant. The 1-pennants are (1), 2-pennants…
  17. GATE 2017 CS (CS1) Q57 (2 marks, Numerical answer) – The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is .
  18. GATE 2016 CS (CS1) Q12 (1 mark, Multiple choice) – Let a n 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 n?
  19. GATE 2016 CS (CS1) Q36 (2 marks, Numerical answer) – The coefficient of x12 in (x3 + x4 + x5 + x6 + )3 is .
  20. GATE 2016 CS (CS1) Q37 (2 marks, Numerical answer) – Consider the recurrence relation a 1 = 8, a n = 6n2 + 2n + a n-1. Let a 99 = K 104. The value of K is .
  21. GATE 2015 CS (CS1) Q45 (2 marks, Multiple choice) – Let a n represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a n?
  22. GATE 2018 CS Q11 (1 mark, Multiple choice) – Which one of the following is a closed form expression for the generating function of the sequence \a n\, where a n=2n+3 for all n=0,1,2,?
  23. GATE 2019 CS Q15 (1 mark, Multiple choice) – Let U=\1,2,,n\. Let A=\(x,X) x X,\ X U\. Consider the following two statements on A . I. A =n2n-1 II. A = k=1nk nk Which of the above statements…
  24. GATE 2026 CS (CS1) Q57 (2 marks, Numerical answer) – Let G be an undirected graph, which is a path on 8 vertices. The number of matchings in G is . (answer in integer)
  25. GATE 2025 CS (CS1) Q30 (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…
  26. GATE 2023 CS Q15 (1 mark, Multiple choice) – The Lucas sequence L n is defined by the recurrence relation: L n = L n-1 + L n-2, for n 3, with L 1 = 1 and L 2 = 3. Which one of the options given…
  27. GATE 2023 CS Q48 (2 marks, Multiple choice) – 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 =…
  28. GATE 2022 CS Q32 (1 mark, Numerical answer) – The number of arrangements of six identical balls in three identical bins is .
  29. GATE 2022 CS Q36 (2 marks, Multiple choice) – Which one of the following is the closed form for the generating function of the sequence \a n\ n0 defined below? a n=casesn+1, & n is odd\\ 1, &…
  30. GATE 2021 CS (CS1) Q29 (1 mark, Numerical answer) – 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…
  31. GATE 2020 CS Q52 (2 marks, Numerical answer) – 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…