Combinatorics · Discrete Mathematics · GATE CSE
Marks 1
1
The number of arrangements of six identical balls in three identical bins is ___________.
GATE CSE 2022
2
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 CSE 2021 Set 1
3
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____________.
GATE CSE 2015 Set 3
4
The recurrence relation capturing the optional execution time of the Towers of Hanoi problem with $$n$$ discs is
GATE CSE 2012
5
In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 student have taken Computer Organization coures; 50 students have taken both Programming Language and Data Structures, 35 students have taken both Programming Languages and Computer Organization; 30 students have taken both Data Structures and Computer Organization; 15 students have taken all the three course.
How many students have not taken any of the three courses?
GATE CSE 2004
6
$$m$$ identical balls are to be placed in $$n$$ distinct bags. You are given that $$m \ge kn$$, where $$k$$ is a natural number $$ \ge 1$$. In how many ways can the balls be placed in the bags if each bag must contain at least $$k$$ balls?
GATE CSE 2003
7
$$n$$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is
GATE CSE 2003
8
Let $$A$$ be a sequence of $$8$$ distinct integers sorted in ascending order. How many distinct pairs of sequence, $$B$$ and $$C$$ are there such that
i) Each is sorted in ascending order.
ii) $$B$$ has $$5$$ and $$C$$ has $$3$$ elements, and
iii) The result of merging $$B$$ $$C$$ gives $$A$$?
i) Each is sorted in ascending order.
ii) $$B$$ has $$5$$ and $$C$$ has $$3$$ elements, and
iii) The result of merging $$B$$ $$C$$ gives $$A$$?
GATE CSE 2003
9
The minimum number of colors required to color the vertices of a cycle with $$n$$ nodes in such a way that no two adjacent nodes have the same colour is:
GATE CSE 2002
10
The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from same suit is
GATE CSE 2000
11
The solution to the recurrence equation
$$T\left( {{2^k}} \right)$$ $$ = 3T\left( {{2^{k - 1}}} \right) + 1$$,
$$T\left( 1 \right) = 1$$ is:
$$T\left( {{2^k}} \right)$$ $$ = 3T\left( {{2^{k - 1}}} \right) + 1$$,
$$T\left( 1 \right) = 1$$ is:
GATE CSE 2000
12
The number of binary strings of $$n$$ zeros and $$k$$ ones such that no two ones are adjacent is:
GATE CSE 1999
Marks 2
1
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 \cap B = \phi $$. 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.
- 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 CSE 2023
2
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 CSE 2020
3
The coefficient of $${x^{12}}$$ in $${\left( {{x^3} + {x^4} + {x^5} + {x^6} + ...} \right)^3}\,\,\,\,\,\,$$ is _____________.
GATE CSE 2016 Set 1
4
The number of distinct positive integral factors of 2014 is _______ .
GATE CSE 2014 Set 2
5
There are 5 bags labeled 1 to 5. All the coins in given bag have the same weight. Some bags have coins of weight 10 gm, other have coins of weight 11 gm. $${\rm I}$$ pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coin is _______ .
GATE CSE 2014 Set 1
6
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 possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)} and the set of all 3-pennants is {(2,1),(1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10-pennants is _________.
GATE CSE 2014 Set 1
7
Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contains no consecutive $$0s$$.
Which of the following recurrences does $${x_n}$$ satisfy?
GATE CSE 2008
8
When $$n = {2^{2k}}$$ for some $$k \ge 0$$, the recurrence relation
$$$T\left( n \right) = \sqrt 2 T\left( {n/2} \right) + \sqrt n ,\,\,T\left( 1 \right) = 1$$$
evaluates to
evaluates to
GATE CSE 2008
9
In how many ways can $$b$$ blue balls and $$r$$ red balls be distributed in $$n$$ distinct boxes?
GATE CSE 2008
10
The exponent of $$11$$ in the prime factorization of $$300!$$ is
GATE CSE 2008
11
Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contain no consecutive $$0s$$.
The value of $${x_5}$$ is
GATE CSE 2008
12
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $$(i, j)$$ then it can move to either $$(i+1, j)$$ or $$(i, j+1)$$
How many distinct path are there for the robot to reach the point $$(10, 10)$$ starting from the initial position $$(0, 0)$$?
GATE CSE 2007
13
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $$(i, j)$$ then it can move to either $$(i+1, j)$$ or $$(i, j+1)$$
Suppose that the robot is not allowed to traverse the line segment from $$(4, 4)$$ to $$(5,4)$$. With this constraint, how many distinct path are there for the robot to reach $$(10, 10)$$ starting from $$(0,0)$$?
GATE CSE 2007
14
Consider the polynomial $$P\left( x \right) = {a_0} + {a_1}x + {a_2}{x^2} + {a_3}{x^3},$$ where $${a_i} \ne 0,\forall i$$. The minimum number of multiplications needed to evaluate $$p$$ on an input $$x$$ is
GATE CSE 2006
15
For each elements in a set of size $$2n$$, an unbiased coin in tossed. The $$2n$$ coin tosses are independent. An element is chhoosen if the corresponding coin toss were head.The probability that exactly $$n$$ elements are chosen is
GATE CSE 2006
16
What is the cardinality of the set of integers $$X$$ defined below?
$$X = $$ {$$n\left| {1 \le n \le 123,\,\,\,\,\,n} \right.$$ is not divisible by either $$2, 3$$ or $$5$$ }
$$X = $$ {$$n\left| {1 \le n \le 123,\,\,\,\,\,n} \right.$$ is not divisible by either $$2, 3$$ or $$5$$ }
GATE CSE 2006
17
What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs $$(a, b)$$ and $$(c, d)$$ in the chosen set such that $$a \equiv c$$ mod $$3$$ and $$b \equiv d$$ mode $$5$$
GATE CSE 2005
18
Let $$G\left( x \right) = 1/\left( {1 - x} \right)2 = \sum\limits_{i = 0}^\infty {g\left( i \right)\,{x^1}} \,\,\,,$$
where $$\left| x \right| < 1$$ What is $$g(i)$$?
where $$\left| x \right| < 1$$ What is $$g(i)$$?
GATE CSE 2005
19
Let $$n = {p^2}q,$$ where $$p$$ and $$q$$ are distinct prime numbers. How many numbers $$m$$ satisfy $$1 \le m \le n$$ and $$gcd\left( {m.n} \right) = 1?$$ Note that $$gcd(m,n)$$ is the greatest common divisor of $$m$$ and $$n$$.
GATE CSE 2005
20
In how many ways can we distribute 5 distinct balls, $${B_1},{B_2},......,{B_5}$$ in 5 distinct cells, $${C_1},{C_2},.....,{C_5}$$ such that Ball $${B_i}$$ is not in cell $${C_i}$$, $$\forall i = 1,2,....,5$$ and each cell contains exactly one ball?
GATE CSE 2004
21
The recurrence equation
$$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$
$$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \right) + n,\,n \ge 2$$
evaluates to
$$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$
$$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \right) + n,\,n \ge 2$$
evaluates to
GATE CSE 2004
22
Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of $$k$$ colours, such that the colour-pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of $$k$$ that satisfies this requirement?
GATE CSE 2004
23
How many 4 digit even numbers have all 4 digits distinct?
GATE CSE 2001
24
Two girls have picked 10 roses, 15 sunflowers and 14 daffodils. What is the number of ways they can divide the flowers among themselves?
GATE CSE 1999
25
Solve the following recurrence relation
$$\,\,\,\,\,\,\,{x_n} = 2{x_{n - 1}} - 1\,\,n > 1$$
$$\,\,\,\,\,\,\,{x_1} = 2$$
GATE CSE 1998
26
In a room containing 28 people, there are 18 people who speak English, 15 people who speak Hindi and 22 people who speak Kannada, 9 persons speak both English and Hindi, 11 persons speak both Hindi and Kannada where as 13 persons speak both Kannada and English. How many people speak all three languages?
GATE CSE 1998
27
The recurrence relation $$\,\,\,\,\,$$ $$T\left( 1 \right) = 2$$
$$T\left( n \right) = 3T\left( {{n \over 4}} \right) + n$$ has the solution $$T(n)$$ equal to
$$T\left( n \right) = 3T\left( {{n \over 4}} \right) + n$$ has the solution $$T(n)$$ equal to
GATE CSE 1996
28
The number of substrings (of all length inclusive) that can be formed from a character string of length $$n$$ is
GATE CSE 1994
29
How many sub strings can be formed from a character string of length $$n$$?
GATE CSE 1989
30
Solve the recurrence equations:
$$\,\,\,\,\,\,\,\,\,\,T\left( n \right) = \left( {{n \over 2}} \right) + 1$$
$$\,\,\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1$$
$$\,\,\,\,\,\,\,\,\,\,T\left( n \right) = \left( {{n \over 2}} \right) + 1$$
$$\,\,\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1$$
GATE CSE 1988
31
(a) Solve the recurrence equations
$$\,\,\,\,\,\,\,\,\,T\left( n \right) = T\left( {n - 1} \right) + n$$
$$\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1T$$
(b) What is the generating function?
$$\,\,\,\,\,\,\,\,\,G\left( z \right)$$ for the sequence of Fibonacci numbers?
$$\,\,\,\,\,\,\,\,\,T\left( n \right) = T\left( {n - 1} \right) + n$$
$$\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1T$$
(b) What is the generating function?
$$\,\,\,\,\,\,\,\,\,G\left( z \right)$$ for the sequence of Fibonacci numbers?
GATE CSE 1987