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.
- GATE 2007 CS Q84 – 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)?
- GATE 2007 CS Q85 – 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…
- GATE 2008 CS Q24 – Let P= 1 i2k,\ i oddi and Q= 1 i2k,\ i eveni, where k is a positive integer. Then
- GATE 2008 CS Q78 – Let xₙ count n-bit binary strings with no consecutive0s. Which recurrence holds?
- GATE 2008 CS Q79 – Let xₙ count n-bit binary strings containing no consecutive0s, using the recurrence in Q78. What is x₅?
- GATE 2021 CS (CS2) Q60 – S has ten elements. How many ordered tuples (A,B) of subsets of S satisfy A⊆B?
- GATE 2015 CS (CS3) Q25 – How many four-digit numbers using only 1,2,3 have digits in nondecreasing order from left to right?
- GATE 2015 CS (CS2) Q14 – How many positive divisors does 2100 have?
- GATE 2015 CS (CS2) Q58 – How many onto functions map X=1,2,3,4 to Y=a,b,c?
- GATE 2010 CS Q37 – A divisor of 1099 is chosen uniformly at random. What is the probability that it is a multiple of 1096?
- GATE 2012 CS Q47 – How many surjections exist from an n-element set (n≥2) to a two-element set?
- GATE 2017 CS (CS2) Q57 – The ordinary generating function of aₙ is (1+z)/(1-z)3. Find a₃−a₀.
- GATE 2016 CS (CS2) Q39 – Evaluate 1399 17 as an integer from 0 through 16.
- GATE 2014 CS (CS2) Q59 – Find the number of distinct positive integer factors of 2014.
- GATE 2014 CS (CS1) Q47 – 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…
- GATE 2014 CS (CS1) Q59 – 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…
- GATE 2017 CS (CS1) Q57 – The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is .
- GATE 2016 CS (CS1) Q12 – 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?
- GATE 2016 CS (CS1) Q36 – The coefficient of x12 in (x3 + x4 + x5 + x6 + )3 is .
- GATE 2016 CS (CS1) Q37 – Consider the recurrence relation a 1 = 8, a n = 6n2 + 2n + a n-1. Let a 99 = K 104. The value of K is .
- GATE 2015 CS (CS1) Q45 – Let a n represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a n?
- GATE 2018 CS Q11 – 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,?
- GATE 2019 CS Q15 – 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…
- GATE 2026 CS (CS1) Q57 – Let G be an undirected graph, which is a path on 8 vertices. The number of matchings in G is . (answer in integer)
- GATE 2025 CS (CS1) Q30 – 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…
- 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 3, with L 1 = 1 and L 2 = 3. Which one of the options given…
- GATE 2023 CS Q48 – 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 =…
- 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 \a n\ n0 defined below? a n=casesn+1, & n is odd\\ 1, &…
- GATE 2021 CS (CS1) Q29 – 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…
- GATE 2020 CS Q52 – 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…