Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Recent
Hot!
Most votes
Most answers
Most views
Previous GATE
Featured
Highest voted questions in Discrete Mathematics
44
votes
4
answers
101
GATE CSE 2003 | Question: 4
Let $A$ be a sequence of $8$ distinct integers sorted in ascending order. How many distinct pairs of sequences, $B$ and $C$ are there such that each is sorted in ascending order, $B$ has $5$ and $C$ has $3$ elements, and the result of merging $B$ and $C$ gives $A$ $2$ $30$ $56$ $256$
Let $A$ be a sequence of $8$ distinct integers sorted in ascending order. How many distinct pairs of sequences, $B$ and $C$ are there such thateach is sorted in ascending...
Kathleen
13.5k
views
Kathleen
asked
Sep 16, 2014
Combinatory
gatecse-2003
combinatory
normal
+
–
43
votes
2
answers
102
GATE CSE 1989 | Question: 1-v
The number of possible commutative binary operations that can be defined on a set of $n$ elements (for a given $n$) is ___________.
The number of possible commutative binary operations that can be defined on a set of $n$ elements (for a given $n$) is ___________.
makhdoom ghaya
6.6k
views
makhdoom ghaya
asked
Nov 27, 2016
Set Theory & Algebra
gate1989
descriptive
set-theory&algebra
binary-operation
+
–
43
votes
8
answers
103
GATE CSE 2006 | Question: 73
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding set...
go_editor
8.9k
views
go_editor
asked
Apr 24, 2016
Graph Theory
gatecse-2006
graph-theory
normal
graph-connectivity
+
–
43
votes
4
answers
104
GATE CSE 2016 Set 2 | Question: 03
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
Akash Kanase
15.6k
views
Akash Kanase
asked
Feb 12, 2016
Graph Theory
gatecse-2016-set2
graph-theory
graph-coloring
normal
numerical-answers
+
–
43
votes
7
answers
105
GATE CSE 2015 Set 3 | Question: 41
Let $R$ be a relation on the set of ordered pairs of positive integers such that $((p,q),(r,s)) \in R$ if and only if $p-s=q-r$. Which one of the following is true about $R$? Both reflexive and symmetric Reflexive but not symmetric Not reflexive but symmetric Neither reflexive nor symmetric
Let $R$ be a relation on the set of ordered pairs of positive integers such that $((p,q),(r,s)) \in R$ if and only if $p-s=q-r$. Which one of the following is true about ...
go_editor
13.0k
views
go_editor
asked
Feb 15, 2015
Set Theory & Algebra
gatecse-2015-set3
set-theory&algebra
relations
normal
+
–
43
votes
11
answers
106
GATE IT 2004 | Question: 35
In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,\ldots 5$ and each cell contains exactly one ball? $44$ $96$ $120$ $3125$
In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $...
Ishrat Jahan
11.6k
views
Ishrat Jahan
asked
Nov 2, 2014
Combinatory
gateit-2004
combinatory
normal
balls-in-bins
+
–
43
votes
5
answers
107
GATE IT 2007 | Question: 21
Which one of these first-order logic formulae is valid? $\forall x\left(P\left(x\right) \implies Q\left(x\right)\right) \implies \left(∀xP\left(x\right)\implies \forall xQ\left(x\right)\right)$ ... $\forall x \exists y P\left(x, y\right)\implies \exists y \forall x P\left(x, y\right)$
Which one of these first-order logic formulae is valid?$\forall x\left(P\left(x\right) \implies Q\left(x\right)\right) \implies \left(∀xP\left(x\right)\implies \forall ...
Ishrat Jahan
10.6k
views
Ishrat Jahan
asked
Oct 29, 2014
Mathematical Logic
gateit-2007
mathematical-logic
normal
first-order-logic
+
–
43
votes
6
answers
108
GATE IT 2008 | Question: 27
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph is sure to be regular complete Hamiltonian Euler
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph...
Ishrat Jahan
14.1k
views
Ishrat Jahan
asked
Oct 28, 2014
Graph Theory
gateit-2008
graph-theory
graph-connectivity
normal
+
–
43
votes
2
answers
109
GATE IT 2008 | Question: 22
Which of the following is the negation of $[∀ x, α → (∃y, β → (∀ u, ∃v, y))]$ $[∃ x, α → (∀y, β → (∃u, ∀ v, y))]$ $[∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))]$ $[∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))]$ $[∃ x, α \wedge (∀y, β \wedge (∃u, ∀ v, ¬y))]$
Which of the following is the negation of $[∀ x, α → (∃y, β → (∀ u, ∃v, y))]$$[∃ x, α → (∀y, β → (∃u, ∀ v, y))]$$[∃ x, α → (∀y, β → ...
Ishrat Jahan
7.9k
views
Ishrat Jahan
asked
Oct 27, 2014
Mathematical Logic
gateit-2008
mathematical-logic
normal
first-order-logic
+
–
43
votes
5
answers
110
GATE CSE 1996 | Question: 8
Let $F$ be the collection of all functions $f: \{1, 2, 3\} \to \{1, 2, 3\}$. If $f$ and $g \in F$, define an equivalence relation $\sim$ by $f\sim g$ if and only if $f(3) = g(3)$. Find the number of equivalence classes defined by $\sim$. Find the number of elements in each equivalence class.
Let $F$ be the collection of all functions $f: \{1, 2, 3\} \to \{1, 2, 3\}$. If $f$ and $g \in F$, define an equivalence relation $\sim$ by $f\sim g$ if and only if $f(3)...
Kathleen
6.1k
views
Kathleen
asked
Oct 9, 2014
Set Theory & Algebra
gate1996
set-theory&algebra
relations
functions
normal
descriptive
+
–
43
votes
9
answers
111
GATE CSE 1996 | Question: 2.1
Let $R$ denote the set of real numbers. Let $f:R\times R \rightarrow R \times R$ be a bijective function defined by $f(x,y) = (x+y, x-y)$. The inverse function of $f$ is given by $f^{-1} (x,y) = \left( \frac {1}{x+y}, \frac{1}{x-y}\right)$ ... $f^{-1}(x,y)=\left [ 2\left(x-y\right),2\left(x+y\right) \right ]$
Let $R$ denote the set of real numbers. Let $f:R\times R \rightarrow R \times R$ be a bijective function defined by $f(x,y) = (x+y, x-y)$. The inverse function of $f$ is ...
Kathleen
9.9k
views
Kathleen
asked
Oct 9, 2014
Set Theory & Algebra
gate1996
set-theory&algebra
functions
normal
+
–
43
votes
3
answers
112
GATE CSE 1994 | Question: 1.10
Some group $(G, o)$ is known to be abelian. Then, which one of the following is true for $G$? $g=g^{-1} \text{ for every } g \in G$ $g=g^2 \text{ for every }g \in G$ $(goh)^2 = g^2oh^2 \text{ for every } g, h \in G$ $G$ is of finite order
Some group $(G, o)$ is known to be abelian. Then, which one of the following is true for $G$?$g=g^{-1} \text{ for every } g \in G$$g=g^2 \text{ for every }g \in G$$(goh)...
Kathleen
10.7k
views
Kathleen
asked
Oct 4, 2014
Set Theory & Algebra
gate1994
set-theory&algebra
group-theory
normal
+
–
43
votes
8
answers
113
GATE CSE 2007 | Question: 22
Let $\text{ Graph}(x)$ be a predicate which denotes that $x$ is a graph. Let $\text{ Connected}(x)$ be a predicate which denotes that $x$ ... $\forall x \, \Bigl ( \text{ Graph}(x) \implies \lnot \text{ Connected}(x) \Bigr )$
Let $\text{ Graph}(x)$ be a predicate which denotes that $x$ is a graph. Let $\text{ Connected}(x)$ be a predicate which denotes that $x$ is connected. Which of the follo...
Kathleen
9.0k
views
Kathleen
asked
Sep 21, 2014
Mathematical Logic
gatecse-2007
mathematical-logic
easy
first-order-logic
+
–
43
votes
5
answers
114
GATE CSE 2003 | Question: 5
$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 \(^{2n}\mathrm{C}_n\times 2^n\) \(3^n\) \(\frac{(2n)!}{2^n}\) \(^{2n}\mathrm{C}_n\)
$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 nu...
Kathleen
10.6k
views
Kathleen
asked
Sep 16, 2014
Combinatory
gatecse-2003
combinatory
normal
+
–
43
votes
5
answers
115
GATE CSE 2006 | Question: 3
The set $\{1,2,3,5,7,8,9\}$ under multiplication modulo $10$ is not a group. Given below are four possible reasons. Which one of them is false? It is not closed $2$ does not have an inverse $3$ does not have an inverse $8$ does not have an inverse
The set $\{1,2,3,5,7,8,9\}$ under multiplication modulo $10$ is not a group. Given below are four possible reasons. Which one of them is false?It is not closed$2$ does no...
Rucha Shelke
10.0k
views
Rucha Shelke
asked
Sep 16, 2014
Set Theory & Algebra
gatecse-2006
set-theory&algebra
group-theory
normal
+
–
43
votes
4
answers
116
GATE CSE 1991 | Question: 02-iv
Match the pairs in the following questions by writing the corresponding letters only. ...
Match the pairs in the following questions by writing the corresponding letters only.$$\begin{array}{|c|l|c|l|} \hline A. & \text{The number of distinct binary tree} & P....
Kathleen
5.1k
views
Kathleen
asked
Sep 12, 2014
Combinatory
gate1991
combinatory
normal
match-the-following
+
–
42
votes
9
answers
117
GATE CSE 2020 | Question: 39
Which one of the following predicate formulae is NOT logically valid? Note that $W$ is a predicate formula without any free occurrence of $x$. $\forall x (p(x) \vee W) \equiv \forall x \: ( px) \vee W$ ... $\exists x(p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W$
Which one of the following predicate formulae is NOT logically valid?Note that $W$ is a predicate formula without any free occurrence of $x$.$\forall x (p(x) \vee W) \equ...
Arjun
17.4k
views
Arjun
asked
Feb 12, 2020
Mathematical Logic
gatecse-2020
first-order-logic
mathematical-logic
2-marks
+
–
42
votes
11
answers
118
GATE CSE 2018 | Question: 1
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}{(1-x)^2}$ $\frac{3x}{(1-x)^2}$ $\frac{2-x}{(1-x)^2}$ $\frac{3-x}{(1-x)^2}$
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...
gatecse
22.9k
views
gatecse
asked
Feb 14, 2018
Combinatory
gatecse-2018
generating-functions
normal
combinatory
1-mark
+
–
42
votes
4
answers
119
GATE CSE 1995 | Question: 2.19
If the proposition $\lnot p \to q$ is true, then the truth value of the proposition $\lnot p \lor \left ( p \to q \right )$, where $\lnot$ is negation, $\lor$ is inclusive OR and $\to$ is implication, is True Multiple Values False Cannot be determined
If the proposition $\lnot p \to q$ is true, then the truth value of the proposition $\lnot p \lor \left ( p \to q \right )$, where $\lnot$ is negation, $\lor$ is inclusiv...
Kathleen
8.7k
views
Kathleen
asked
Oct 8, 2014
Mathematical Logic
gate1995
mathematical-logic
normal
propositional-logic
+
–
42
votes
4
answers
120
GATE CSE 1993 | Question: 17
Out of a group of $21$ persons, $9$ eat vegetables, $10$ eat fish and $7$ eat eggs. $5$ persons eat all three. How many persons eat at least two out of the three dishes?
Out of a group of $21$ persons, $9$ eat vegetables, $10$ eat fish and $7$ eat eggs. $5$ persons eat all three. How many persons eat at least two out of the three dishes?
Kathleen
8.3k
views
Kathleen
asked
Sep 29, 2014
Set Theory & Algebra
gate1993
set-theory&algebra
easy
set-theory
descriptive
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
...
357
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register