The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Most answered questions in Discrete Mathematics
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
+20
votes
10
answers
1
GATE201846
The number of possible minheaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
asked
Feb 14, 2018
in
Combinatory
by
gatecse
Boss
(
18.5k
points)

7.2k
views
gate2018
permutationsandcombinations
numericalanswers
+34
votes
10
answers
2
GATE2016126
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

8.4k
views
gate20161
permutationsandcombinations
generatingfunctions
normal
numericalanswers
+36
votes
10
answers
3
GATE201535
The number of $4$ digit numbers having their digits in nondecreasing order (from left to right) constructed by using the digits belonging to the set $\{1, 2, 3\}$ is ________.
asked
Feb 14, 2015
in
Combinatory
by
jothee
Veteran
(
116k
points)

3.7k
views
gate20153
permutationsandcombinations
normal
numericalanswers
+20
votes
10
answers
4
GATE2014353
The CORRECT formula for the sentence, "not all Rainy days are Cold" is $\forall d (\text{Rainy}(d) \wedge \text{~Cold}(d))$ $\forall d ( \text{~Rainy}(d) \to \text{Cold}(d))$ $\exists d(\text{~Rainy}(d) \to \text{Cold}(d))$ $\exists d(\text{Rainy}(d) \wedge \text{~Cold}(d))$
asked
Sep 28, 2014
in
Mathematical Logic
by
jothee
Veteran
(
116k
points)

1.6k
views
gate20143
mathematicallogic
easy
firstorderlogic
+31
votes
10
answers
5
GATE2014149
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 ... $(1,2)$ is not the same as the pennant $(2,1)$. The number of $10$pennants is________
asked
Sep 28, 2014
in
Combinatory
by
jothee
Veteran
(
116k
points)

2.6k
views
gate20141
permutationsandcombinations
numericalanswers
normal
+9
votes
9
answers
6
ISRO201722
Which one of the following Boolean expressions is NOT a tautology? $((a \rightarrow b) \wedge (b \rightarrow c)) \rightarrow (a \rightarrow c)$ $(a \leftrightarrow c) \rightarrow (\sim b\rightarrow (a\wedge c))$ $(a\wedge b \wedge c)\rightarrow (c \vee a)$ $a\rightarrow (b\rightarrow a)$
asked
May 7, 2017
in
Mathematical Logic
by
sh!va
Boss
(
35.5k
points)

2.8k
views
isro2017
booleanexpressions
mathematicallogic
+28
votes
9
answers
7
GATE2015240
The number of onto functions (surjective functions) from set $X = \{1, 2, 3, 4\}$ to set $Y=\{a,b,c\}$ is ______.
asked
Feb 13, 2015
in
Set Theory & Algebra
by
jothee
Veteran
(
116k
points)

7.3k
views
gate20152
settheory&algebra
functions
normal
numericalanswers
+12
votes
8
answers
8
GATE201830
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between ... then $\mid ij \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
asked
Feb 14, 2018
in
Graph Theory
by
gatecse
Boss
(
18.5k
points)

4.7k
views
gate2018
graphtheory
graphsearch
normal
+21
votes
8
answers
9
GATE2017223
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
asked
Feb 14, 2017
in
Graph Theory
by
Madhav
Active
(
1.7k
points)

4.3k
views
gate20172
graphtheory
numericalanswers
degreeofgraph
+11
votes
8
answers
10
GATE2017147
The number of integers between $1$ and $500$ (both inclusive) that are divisible by $3$ or $5$ or $7$ is ____________ .
asked
Feb 14, 2017
in
Set Theory & Algebra
by
Arjun
Veteran
(
400k
points)

3.4k
views
gate20171
settheory&algebra
normal
numericalanswers
sets
+35
votes
8
answers
11
GATE2016127
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

6.9k
views
gate20161
permutationsandcombinations
recurrence
normal
numericalanswers
+6
votes
8
answers
12
ISRO201473
How many different trees are there with four nodes $A, B, C$ and $D$? 30 60 90 120
asked
Sep 23, 2015
in
Combinatory
by
ajit
Active
(
3.3k
points)

6.1k
views
permutationsandcombinations
isro2014
+14
votes
8
answers
13
GATE19962.3
Which of the following is false? Read $\wedge$ as AND, $\vee$ as OR, $\neg$ as NOT, $\rightarrow$ as one way implication and $\leftrightarrow$ as two way implication $((x \rightarrow y) \wedge x) \rightarrow y$ $((\neg x \rightarrow y) \wedge (\neg x \rightarrow \neg y)) \rightarrow x$ $(x \rightarrow (x \vee y))$ $((x \vee y) \leftrightarrow (\neg x \rightarrow \neg y))$
asked
Oct 9, 2014
in
Mathematical Logic
by
Kathleen
Veteran
(
59.8k
points)

1.5k
views
gate1996
mathematicallogic
normal
propositionallogic
+23
votes
8
answers
14
GATE2014153
Which one of the following propositional logic formulas is TRUE when exactly two of $p,q$ and $r$ are TRUE? $(( p \leftrightarrow q) \wedge r) \vee (p \wedge q \wedge \sim r)$ $( \sim (p \leftrightarrow q) \wedge r)\vee (p \wedge q \wedge \sim r)$ $( (p \to q) \wedge r) \vee (p \wedge q \wedge \sim r)$ $(\sim (p \leftrightarrow q) \wedge r) \wedge (p \wedge q \wedge \sim r) $
asked
Sep 28, 2014
in
Mathematical Logic
by
jothee
Veteran
(
116k
points)

3k
views
gate20141
mathematicallogic
normal
propositionallogic
+27
votes
8
answers
15
GATE20092
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n1$ $n$
asked
Sep 15, 2014
in
Graph Theory
by
gatecse
Boss
(
18.5k
points)

3.1k
views
gate2009
graphtheory
graphcoloring
normal
+1
vote
7
answers
16
GATE201912
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n1)!$ $1$ $\frac{(n1)!}{2}$
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
400k
points)

2.7k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+12
votes
7
answers
17
GATE20181
Which one of the following is a closed form expression for the generating function of the sequence $\{a_n\}$, where $a_n = 2n +3 \text{ for all } n=0, 1, 2, \dots$? $\frac{3}{(1x)^2}$ $\frac{3x}{(1x)^2}$ $\frac{2x}{(1x)^2}$ $\frac{3x}{(1x)^2}$
asked
Feb 14, 2018
in
Combinatory
by
gatecse
Boss
(
18.5k
points)

5.5k
views
gate2018
generatingfunctions
normal
+19
votes
7
answers
18
GATE2017211
Let $p, q, r$ ... $(\neg p \wedge r) \vee (r \rightarrow (p \wedge q))$
asked
Feb 14, 2017
in
Mathematical Logic
by
khushtak
Loyal
(
7.7k
points)

3.4k
views
gate20172
mathematicallogic
propositionallogic
+2
votes
7
answers
19
is D36 distributive ?
In one text I read that , if n is square free it is DISTRIBUTIVE in other text I read that if n is square free it is BOOLEAN ALGEBRA . Which is most correct ? Here D36 is not square free then... what conclusion can I make ?
asked
Jun 24, 2016
in
Set Theory & Algebra
by
pC
Boss
(
22.6k
points)

1.1k
views
settheory&algebra
lattice
+16
votes
7
answers
20
TIFR2015B5
Suppose $\begin{pmatrix} 0&1 &0&0&0&1 \\ 1&0&1&0&0&0 \\ 0&1&0&1&0&1 \\ 0&0&1&0&1&0 \\ 0&0&0&1&0&1 \\ 1&0&1&0&1&0 \end{pmatrix}$ is the adjacency matrix of an ... below has the above adjacency matrix? Only $(i)$ Only $(ii)$ Only $(iii)$ Only $(iv)$ $(i)$ and $(ii)$
asked
Dec 7, 2015
in
Graph Theory
by
makhdoom ghaya
Boss
(
41.2k
points)

840
views
tifr2015
graphconnectivity
graphtheory
+8
votes
7
answers
21
Kenneth Rosen Edition 6 Question 45 (Page No. 346)
How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?
asked
Jul 13, 2015
in
Combinatory
by
Anu
Loyal
(
5.9k
points)

2k
views
permutationsandcombinations
counting
+38
votes
7
answers
22
GATE2015324
In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the ... The result is tail If the person is of Type 2, then the result is tail If the person is of Type 1, then the result is tail
asked
Feb 14, 2015
in
Mathematical Logic
by
jothee
Veteran
(
116k
points)

4.5k
views
gate20153
mathematicallogic
difficult
logicalreasoning
+46
votes
7
answers
23
GATE2015139
Consider the operations $\textit{f (X, Y, Z) = X'YZ + XY' + Y'Z'}$ and $\textit{g (X, Y, Z) = X'YZ + X'YZ' + XY}$ Which one of the following is correct? Both $\left\{\textit{f} \right\}$ and $\left\{ \textit{g}\right\}$ are ... Only $\left\{ \textit{g}\right\}$ is functionally complete Neither $\left\{ \textit{f}\right\}$ nor $\left\{\textit{g}\right\}$ is functionally complete
asked
Feb 13, 2015
in
Set Theory & Algebra
by
makhdoom ghaya
Boss
(
41.2k
points)

6.9k
views
gate20151
settheory&algebra
functions
difficult
+28
votes
7
answers
24
GATE2005IT36
Let $P(x)$ and $Q(x)$ ...
asked
Nov 3, 2014
in
Mathematical Logic
by
Ishrat Jahan
Boss
(
19.1k
points)

3.8k
views
gate2005it
mathematicallogic
firstorderlogic
normal
+29
votes
7
answers
25
GATE19941.6, ISRO200829
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
asked
Oct 4, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.8k
points)

8.8k
views
gate1994
graphtheory
permutationsandcombinations
normal
isro2008
counting
+52
votes
7
answers
26
GATE2014151
Consider an undirected graph $G$ where selfloops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
asked
Sep 28, 2014
in
Graph Theory
by
jothee
Veteran
(
116k
points)

6.9k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
+24
votes
7
answers
27
GATE200473
The inclusion of which of the following sets into $S = \left\{ \left\{1, 2\right\}, \left\{1, 2, 3\right\}, \left\{1, 3, 5\right\}, \left\{1, 2, 4\right\}, \left\{1, 2, 3, 4, 5\right\} \right\} $ is necessary and sufficient to make $S$ a complete lattice under the partial order defined by set containment ... $\{1\}, \{1, 3\}$ $\{1\}, \{1, 3\}, \{1, 2, 3, 4\}, \{1, 2, 3, 5\}$
asked
Sep 19, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.8k
points)

2.4k
views
gate2004
settheory&algebra
partialorder
normal
+3
votes
6
answers
28
TIFR2019A1
Let $X$ be a set with $n$ elements.How many subsets of $X$ have odd cardinality? $n$ $2^n$ $2^{n/2}$ $2^{n1}$ Can not be determined without knowing whether $n$ is odd or even
asked
Dec 18, 2018
in
Set Theory & Algebra
by
Arjun
Veteran
(
400k
points)

449
views
tifr2019
engineeringmathematics
discretemathematics
settheory&algebra
+33
votes
6
answers
29
GATE2017102
Consider the firstorder logic sentence $F:\forall x(\exists yR(x,y))$. Assuming nonempty logical domains, which of the sentences below are implied by $F$? $\exists y(\exists xR(x,y))$ $\exists y(\forall xR(x,y))$ $\forall y(\exists xR(x,y))$ $¬\exists x(\forall y¬R(x,y))$ IV only I and IV only II only II and III only
asked
Feb 14, 2017
in
Mathematical Logic
by
khushtak
Loyal
(
7.7k
points)

5.1k
views
gate20171
mathematicallogic
firstorderlogic
+33
votes
6
answers
30
GATE2017247
If the ordinary generating function of a sequence $\big \{a_n\big \}_{n=0}^\infty$ is $\large \frac{1+z}{(1z)^3}$, then $a_3a_0$ is equal to ___________ .
asked
Feb 14, 2017
in
Combinatory
by
Arjun
Veteran
(
400k
points)

5.3k
views
gate20172
permutationsandcombinations
generatingfunctions
numericalanswers
normal
Page:
1
2
3
4
5
6
...
174
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has started
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
All categories
General Aptitude
1.7k
Engineering Mathematics
7.4k
Discrete Mathematics
5.2k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
898
Graph Theory
801
Probability
989
Linear Algebra
686
Calculus
497
Digital Logic
2.9k
Programming & DS
4.9k
Algorithms
4.3k
Theory of Computation
6k
Compiler Design
2k
Operating System
4.2k
Databases
4.1k
CO & Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.4k
Others
1.6k
Admissions
591
Exam Queries
643
Tier 1 Placement Questions
23
Job Queries
72
Projects
23
Follow @csegate
Recent Blog Comments
It was free when I gave them, maybe they made it...
The tests are there but it ain't free. Cost is...
They removed their tests recently, I think it'll...
how did you get Success gateway test series for...
49,781
questions
53,593
answers
185,825
comments
70,880
users