Combinatorics, Counting, Recurrence Relations and Generating Functions: GATE CS previous year questions (Engineering Mathematics)

Hide the 2 questions not in the current syllabus

GATE CS 2026 Set 1MCQ1 markMedium (estimate)
GATE CS 2026 Set 1, Q.12
Consider $4 \times 4$ matrices with their elements from ${0, 1}$ . The number of such matrices with even number of $1$ s in every row and every column is
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2026 Set 1NAT2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.57
Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is ______. (answer in integer)
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2025 Set 1NAT1 markEasy (estimate)
GATE CS 2025 Set 1, Q.30
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, t...
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2025 Set 2MCQ1 markEasy (estimate)
GATE CS 2025 Set 2, Q.15
Let $P (x)$ be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
Propositional and First-Order Logic · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2025 Set 2NAT2 marksMedium (estimate)
GATE CS 2025 Set 2, Q.64
A quadratic polynomial $(x - α) (x - β)$ over complex numbers is said to be square invariant if $(x - α) (x - β) = (x - α^{2}) (x - β^{2})$ . Suppose from the...
Probability and Statistics · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2024 Set 1MCQ1 markEasy (estimate)
GATE CS 2024 Set 1, Q.14
Consider a permutation sampled uniformly at random from the set of all permutations of ${1, 2, 3, \dots, n}$ for some $n \geq 4$ . Let $X$ be the event that $1$ occurs before…
Probability and Statistics · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2024 Set 2MCQ1 markEasy (estimate)
GATE CS 2024 Set 2, Q.2
Two wizards try to create a spell using all the four elements, water, air, fire, and earth. For this, they decide to mix all these elements in all possible orders. They also dec...
Quantitative Aptitude · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2024 Set 2MCQ1 markMedium (estimate)
GATE CS 2024 Set 2, Q.15
Let $T (n)$ be the recurrence relation defined as follows: $T (0) = 1$ , $T (1) = 2$ , and $T (n) = 5 T (n - 1) - 6 T (n - 2)$ for $n \geq 2$ Which one of the following statements is TRUE?
Asymptotic Analysis and Time/Space Complexity · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2024 Set 2MCQ1 markEasy (estimate)
GATE CS 2024 Set 2, Q.18
When six unbiased dice are rolled simultaneously, the probability of getting all distinct numbers (i.e., 1, 2, 3, 4, 5, and 6) is
Probability and Statistics · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2024 Set 2NAT1 markEasy (estimate)
GATE CS 2024 Set 2, Q.34
Let $P$ be the partial order defined on the set ${1, 2, 3, 4}$ as follows $P = {(x, x) ∣ x \in {1, 2, 3, 4}} \cup {(1, 2), (3, 2), (3, 4)}$ The number of total orders on…
Sets, Relations, Functions, Partial Orders and Lattices · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2024 Set 2NAT2 marksMedium (estimate)
GATE CS 2024 Set 2, Q.56
A functional dependency $F : X \to Y$ is termed as a useful functional dependency if and only if it satisfies all the following three conditions: - $X$ is not the empty s...
Functional Dependencies and Normalization · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2024 Set 2NAT2 marksEasy (estimate)
GATE CS 2024 Set 2, Q.62
Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*} (a b^{*} a b^{*})^{*}$ and $L_{2} = {w \in (a + b)^{*} ∣ ∣ w ∣ \leq 4}$ , where $∣ w ∣$ denotes the length of string…
Regular Expressions, Finite Automata and Regular Languages · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2023MCQ1 markEasy (estimate)
GATE CS 2023, Q.15
The Lucas sequence $L_{n}$ is defined by the recurrence relation: $L_{n} = L_{n - 1} + L_{n - 2}, for n \geq 3,$ with $L_{1} = 1$ and $L_{2} = 3$ . Which one of the options gi...
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2023MCQ2 marksMedium (estimate)
GATE CS 2023, Q.48
Let $U = {1, 2, \dots, 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…
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2022NAT1 markEasy (estimate)
GATE CS 2022, Q.32
The number of arrangements of six identical balls in three identical bins is______.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2022MCQ2 marksMedium (estimate)
GATE CS 2022, Q.36
Which one of the following is the closed form for the generating function of the sequence ${a_{n}}_{n \geq 0}$ defined below?…
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2022MSQ2 marksMedium (estimate)
GATE CS 2022, Q.51
Consider the following recurrence: $f (1) = 1;$ $f (2 n) = 2 f (n) - 1, for n \geq 1;$ $f (2 n + 1) = 2 f (n) + 1, for n \geq 1.$ Then, which of the follo...
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2021 Set 1NAT1 markMedium (estimate)
GATE CS 2021 Set 1, Q.29 (CS Q.19)
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...
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2021 Set 2NAT2 marksEasy (estimate)
GATE CS 2021 Set 2, Q.60 (CS Q.50)
Let $S$ be a set consisting of 10 elements. The number of tuples of the form $(A, B)$ such that $A$ and $B$ are subsets of $S$ , and $A \subseteq B$ is ______.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2020NAT2 marksMedium (estimate)
GATE CS 2020, Q.52 (CS Q.42)
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 _______.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2019MCQ1 markMedium (estimate)
GATE CS 2019, Q.15 (CS Q.5)
Let $U = {1, 2, \dots, n}$ . Let $A = {(x, X) ∣ x \in X, X \subseteq U}$ . Consider the following two statements on $∣ A ∣$ . I. $∣ A ∣ = n 2^{n - 1}$ II.…
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2018MCQ1 markEasy (estimate)
GATE CS 2018, Q.11 (CS Q.1)
Which one of the following is a closed form expression for the generating function of the sequence ${a_{n}}$ , where $a_{n} = 2 n + 3$ for all $n = 0, 1, 2, \dots$ ?
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2017 Set 1NAT2 marksEasy (estimate)
GATE CS 2017 Set 1, Q.47 (CS Q.47)
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2017 Set 2NAT2 marksMedium (estimate)
GATE CS 2017 Set 2, Q.47 (CS Q.47)
If the ordinary generating function of a sequence ${a_{n}}_{n = 0}^{\infty}$ is $\frac{1 + z}{( 1 - z ) ^{3}}$ , then $a_{3} - a_{0}$ is equal to
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2016 Set 1MCQ1 markEasy (estimate)
GATE CS 2016 Set 1, Q.12 (CS Q.2)
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}$ ?
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2016 Set 1NAT2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.36 (CS Q.26)
The coefficient of $x^{12}$ in $(x^{3} + x^{4} + x^{5} + x^{6} + \dots)^{3}$ is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2016 Set 1NAT2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.37 (CS Q.27)
Consider the recurrence relation $a_{1} = 8$ , $a_{n} = 6 n^{2} + 2 n + a_{n - 1}$ . Let $a_{99} = K \times 1 0^{4}$ . The value of $K$ is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2016 Set 2NAT2 marksEasy (estimate)
GATE CS 2016 Set 2, Q.39 (CS Q.29)
The value of the expression $1 3^{99} (mod 17)$ , in the range 0 to 16, is ________.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2015 Set 1MCQ2 marksMedium (estimate)
GATE CS 2015 Set 1, Q.59 (CS Q.49)
Let $a_{n}$ represent the number of bit strings of length $n$ containing two consecutive 1s. What is the recurrence relation for $a_{n}$ ?
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2015 Set 2NAT1 markEasy (estimate)
GATE CS 2015 Set 2, Q.19 (CS Q.9)
The number of divisors of 2100 is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2015 Set 2MCQ1 markEasy (estimate)Not in current syllabus
GATE CS 2015 Set 2, Q.22 (CS Q.12)
Consider the basic COCOMO model where $E$ is the effort applied in person-months, $D$ is the development time in chronological months, KLOC is the estimated number of delivered...
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2015 Set 2NAT2 marksMedium (estimate)
GATE CS 2015 Set 2, Q.50 (CS Q.40)
The number of onto functions (surjective functions) from set $X = {1, 2, 3, 4}$ to set $Y = {a, b, c}$ is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2015 Set 3NAT1 markMedium (estimate)
GATE CS 2015 Set 3, Q.15 (CS Q.5)
The number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set ${1, 2, 3}$ is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2015 Set 3NAT1 markMedium (estimate)Not in current syllabus
GATE CS 2015 Set 3, Q.31 (CS Q.21)
Consider a software project with the following information domain characteristics for calculation of function point metric.…
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2015 Set 3NAT2 marksEasy (estimate)
GATE CS 2015 Set 3, Q.59 (CS Q.49)
Suppose $c = (c [0], \dots, c [k - 1])$ is an array of length $k$ , where all the entries are from the set ${0, 1}$ . For any positive integers $a$ and $n$ , consider the following...
Combinatorics, Counting, Recurrence Relations and Generating Functions · Asymptotic Analysis and Time/Space Complexity
GATE CS 2014 Set 1NAT2 marksEasy (estimate)
GATE CS 2014 Set 1, Q.47 (CS Q.37)
There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 1...
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2014 Set 1NAT2 marksMedium (estimate)
GATE CS 2014 Set 1, Q.59 (CS Q.49)
A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all poss...
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2014 Set 2NAT2 marksEasy (estimate)
GATE CS 2014 Set 2, Q.59 (CS Q.49)
The number of distinct positive integral factors of 2014 is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2012MCQ2 marksEasy (estimate)
GATE CS 2012, Q.37 (CS Q.37)
How many onto (or surjective) functions are there from an $n$ -element ( $n \geq 2$ ) set to a 2-element set?
Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2012MCQ2 marksMedium (estimate)
GATE CS 2012, Q.38 (CS Q.38)
Let $G$ be a complete undirected graph on 6 vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length 4 in $G$ is equal to
Graph Theory · Combinatorics, Counting, Recurrence Relations and Generating Functions

Questions

Other topics of Engineering Mathematics