Recent questions and answers in Discrete Mathematics - GATE Overflow

+5 votes

5 answers

1

GATE2019-38
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II

answered 17 hours ago in Graph Theory by V0id (15 points) | 3k views

+54 votes

9 answers

2

GATE2015-1-39
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

answered 1 day ago in Set Theory & Algebra by Kuldeep Pal Active (1.5k points) | 7.6k views

+23 votes

7 answers

3

GATE2006-28
A logical binary relation $\odot$ ... $(\sim A\odot B)$ $\sim(A \odot \sim B)$ $\sim(\sim A\odot\sim B)$ $\sim(\sim A\odot B)$

answered 1 day ago in Set Theory & Algebra by haralk10 (23 points) | 1.5k views

+6 votes

3 answers

4

ISRO2007-29
The set of all Equivalence Classes of a set A of Cardinality C is of cardinality $2^c$ have the same cardinality as A forms a partition of A is of cardinality $C^2$

answered 2 days ago in Set Theory & Algebra by JashanArora Active (1.8k points) | 2.4k views

+8 votes

5 answers

5

TIFR2018-A-6
What is the minimum number of students needed in a class to guarantee that there are at least $6$ students whose birthdays fall in the same month ? $6$ $23$ $61$ $72$ $91$

answered 3 days ago in Combinatory by `JEET Boss (13.1k points) | 419 views

+1 vote

2 answers

6

#set theory #groups
Consider the set H of all 3 × 3 matrices of the type: $\begin{bmatrix} a&f&e\\ 0&b&d\\ 0&0&c\\ \end{bmatrix}$ where a, b, c, d, e and f are real numbers and $abc ≠ 0$. Under the matrix multiplication operation, the set H is: (a) a group (b) a monoid but not a group (c) a semigroup but not a monoid (d) neither a group nor a semigroup

answered 3 days ago in Set Theory & Algebra by smsubham Loyal (9.7k points) | 75 views

+34 votes

9 answers

7

GATE1994-1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$

answered 3 days ago in Graph Theory by JashanArora Active (1.8k points) | 9.7k views

+24 votes

13 answers

8

GATE2018-46
The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______

answered 4 days ago in Combinatory by Praveenk99 (49 points) | 8.4k views

+37 votes

11 answers

9

GATE2016-1-26
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.

answered 4 days ago in Combinatory by pritishc Junior (669 points) | 9k views

+28 votes

5 answers

10

GATE2000-6
Let $S$ be a set of $n$ elements $\left\{1, 2,....., n\right\}$ and $G$ a graph with 2$^{n}$ vertices, each vertex corresponding to a distinct subset of $S$. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly $2$ ... $G$ has the same degree. What is the degree of a vertex in $G$? How many connected components does $G$ have?

answered 4 days ago in Set Theory & Algebra by Vimal Patel (137 points) | 1.8k views

+1 vote

3 answers

11

GATE2001-4
Consider the function $h: N \times N \rightarrow N$ so that $h(a,b) = (2a +1)2^b - 1$, where $N=\{0,1,2,3,\dots\}$ is the set of natural numbers. Prove that the function $h$ is an injection (one-one). Prove that it is also a Surjection (onto)

answered 4 days ago in Set Theory & Algebra by Verma Ashish Boss (11.8k points) | 455 views

+1 vote

1 answer

12

TIFR2019-A-6
A function $f: \mathbb{R} \rightarrow \mathbb{R}$ is said to be $\textit{convex}$ if for all $x,y \in \mathbb{R}$ and $\lambda$ such that $0 \leq \lambda \leq1,$ $f(\lambda x+ (1-\lambda)y) \leq \lambda f (x) + (1-\lambda) f(y)$. Let $f:$\mathbb{R}$ $→$ $\mathbb ... $p,q$ and $r$ must be convex? Only $p$ Only $q$ Only $r$ Only $p$ and $r$ Only $q$ and $r$

answered 5 days ago in Set Theory & Algebra by Satbir Boss (21.5k points) | 344 views

+7 votes

7 answers

13

GATE2019-35
Consider the first order predicate formula $\varphi$: $\forall x [ ( \forall z \: z \mid x \Rightarrow (( z=x) \vee (z=1))) \rightarrow \exists w ( w > x) \wedge (\forall z \: z \mid w \Rightarrow ((w=z) \vee (z=1)))]$ Here $a \mid b$ ... Set of all positive integers $S3:$ Set of all integers Which of the above sets satisfy $\varphi$? S1 and S2 S1 and S3 S2 and S3 S1, S2 and S3

answered 5 days ago in Mathematical Logic by JashanArora Active (1.8k points) | 5.1k views

+5 votes

9 answers

14

GATE2019-12
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!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$

answered 6 days ago in Graph Theory by JashanArora Active (1.8k points) | 3.3k views

0 votes

2 answers

15

self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??

answered Nov 30 in Graph Theory by Muneendra1337 (11 points) | 60 views

0 votes

1 answer

16

group
if (G,*) is a cyclic group of order 97 , then number of generator of G is equal to ___

answered Nov 29 in Set Theory & Algebra by GoalSet1 (203 points) | 123 views

+1 vote

2 answers

17

ISI2014-DCG-71
Five letters $A, B, C, D$ and $E$ are arranged so that $A$ and $C$ are always adjacent to each other and $B$ and $E$ are never adjacent to each other. The total number of such arrangements is $24$ $16$ $12$ $32$

answered Nov 28 in Combinatory by noob_coder Junior (657 points) | 26 views

+2 votes

1 answer

18

Kenneth Rosen Edition 6th Exercise 6.4 Question 13 (Page No. 440)
Use Generating function to determine,the number of different ways $10$ identical balloons can be given to four children if each child receives atleast $2$ ballons? Ans given $(x^{2}+x^{3}+.........................)^{4}$ But as there is a upper ... Which one is correct? plz confirm

answered Nov 26 in Combinatory by Kushagra गुप्ता Active (1.9k points) | 198 views

+36 votes

7 answers

19

GATE2008-IT-21
Which of the following first order formulae is logically valid? Here $\alpha(x)$ is a first order formula with $x$ as a free variable, and $\beta$ ... $[(\forall x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$

answered Nov 26 in Mathematical Logic by JashanArora Active (1.8k points) | 4.2k views

+28 votes

3 answers

20

GATE2002-1.25, ISRO2008-30, ISRO2016-6
The maximum number of edges in a n-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$

answered Nov 23 in Graph Theory by Shailendra_ Junior (555 points) | 5.5k views

+1 vote

2 answers

21

ISI2016-PCB-A-3
A bit string is called legitimate if it contains no consecutive zeros $, e.g., 0101110$ is legitimate, where as $10100111$ is not. Let $a_n$ denote the number of legitimate bit strings of length $n$. Define $a_0=1$. Derive a recurrence relation for $a_n ( i.e.,$ express $a_n$ in terms of the preceding $a_i's).$

answered Nov 22 in Combinatory by chirudeepnamini Active (3.1k points) | 29 views

+2 votes

3 answers

22

ISI2014-DCG-18
$^nC_0+2^nC_1+3^nC_2+\cdots+(n+1)^nC_n$ equals $2^n+n2^{n-1}$ $2^n-n2^{n-1}$ $2^n$ none of these

answered Nov 20 in Combinatory by chirudeepnamini Active (3.1k points) | 43 views

+1 vote

1 answer

23

ISI2018-DCG-14
In a room there are $8$ men, numbered $1,2, \dots ,8$. These men have to be divided into $4$ teams in such a way that every team has exactly $2$ ... of such $4$-team combinations is $\frac{8!}{2^4}$ $\frac{8!}{2^4(4!)}$ $\frac{8!}{4!}$ $\frac{8!}{(4!)^2}$

answered Nov 19 in Combinatory by Yash4444 Junior (731 points) | 17 views

+1 vote

1 answer

24

ISI2016-DCG-21
The value of the term independent of $x$ in the expansion of $(1-x)^{2}(x+\frac{1}{x})^{7}$ is $-70$ $70$ $35$ None of these

answered Nov 18 in Combinatory by Verma Ashish Boss (11.8k points) | 18 views

+15 votes

9 answers

25

GATE2018-30
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 i-j \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II

answered Nov 17 in Graph Theory by Shailendra_ Junior (555 points) | 5.5k views

+3 votes

1 answer

26

Mock DFS Q
Consider DFS over undirected graph with 4 vertices <A;B;C;D>. The discovery and finishing times of them in the order A to D are given. Select the option from following showing more than one connected components: 1) <(1,6), (2,5), (3,4), (8,10)> 2) <(6,7), (2,5), (3,4), (8,9)> 3) <(4,5), (2,8), (1,7), (3,6)> 4) <(7,8), (1,2), (5,6), (3,4)>

answered Nov 15 in Set Theory & Algebra by vk82942349 (11 points) | 135 views

+1 vote

1 answer

27

Difference between DAG and Multi-stage graph
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?

answered Nov 15 in Graph Theory by mohithjagalmohanan (19 points) | 75 views

+6 votes

3 answers

28

GATE2019-5
Let $U = \{1, 2, \dots , n\}$ Let $A=\{(x, X) \mid x \in X, X \subseteq U \}$. Consider the following two statements on $\mid A \mid$. $\mid A \mid = n2^{n-1}$ $\mid A \mid = \Sigma_{k=1}^{n} k \begin{pmatrix} n \\ k \end{pmatrix}$ Which of the above statements is/are TRUE? Only I Only II Both I and II Neither I nor II

answered Nov 14 in Combinatory by Optimus Prime Junior (543 points) | 2.7k views

+1 vote

2 answers

29

ISI2018-DCG-7
You are given three sets $A,B,C$ in such a way that the set $B \cap C$ consists of $8$ elements, the set $A\cap B$ consists of $7$ elements, and the set $C\cap A$ consists of $7$ elements. The minimum number of elements in the set $A\cup B\cup C$ is $8$ $14$ $15$ $22$

answered Nov 14 in Set Theory & Algebra by chirudeepnamini Active (3.1k points) | 34 views

+2 votes

2 answers

30

CMI2018-A-4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$

answered Nov 12 in Graph Theory by SPodder (11 points) | 25 views

+32 votes

7 answers

31

GATE2002-1.8
"If $X$ then $Y$ unless $Z$" is represented by which of the following formulas in prepositional logic? ("$\neg$" is negation, "$\land$" is conjunction, and "$\rightarrow$" is implication) $(X\land \neg Z) \rightarrow Y$ $(X \land Y) \rightarrow \neg Z$ $X \rightarrow(Y\land \neg Z)$ $(X \rightarrow Y)\land \neg Z$

answered Nov 11 in Mathematical Logic by Navneet Singh Tomar Junior (621 points) | 4.4k views

0 votes

2 answers

32

MadeEasy Full Length Test 2019: Combinatory - Permutations And Combinations
The number of ways 5 letter be put in 3 letter boxes A,B,C. If letter box A must contain at least 2 letters.

answered Nov 11 in Combinatory by SaurabhKatkar (151 points) | 207 views

0 votes

2 answers

33

solution of rosen
can anyone has the soft copy of kenneth h rosen solutions?

answered Nov 11 in Mathematical Logic by Ram Swaroop Active (4.6k points) | 402 views

+2 votes

2 answers

34

Discrete Mathematics Thegatebook
how many positive integers between 50 and 100, (a) divisible by 7 (b) divisible by 11 (c) divisible by 7 and 11?

answered Nov 10 in Combinatory by Ram Swaroop Active (4.6k points) | 303 views

+2 votes

3 answers

35

Rosen chapter 5.5 question 50
How many ways are there to distribute 5 distinguishable objects into three indistinguishable boxes?

answered Nov 9 in Mathematical Logic by SaurabhKatkar (151 points) | 242 views

0 votes

2 answers

36

Rosen 7e Exercise-8.1 Question no-10 Page no-511
Find a recurrence relation for the number of bit strings of length n that contain the string 01.

answered Nov 9 in Combinatory by Sandeep shahu (71 points) | 59 views

+1 vote

1 answer

37

CMI2018-A-5
How many paths are there in the plane from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N},$ if the possible steps from $(i,j)$ are either $(i+1,j)$ or $(i,j+1)?$ $\binom{2m}{n}$ $\binom{m}{n}$ $\binom{m+n}{n}$ $m^{n}$

answered Nov 9 in Combinatory by `JEET Boss (13.1k points) | 37 views

+1 vote

1 answer

38

CMI2016-A-9
ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is connected-there is a path from each city to every other city. The contract requires the network to remain ... $34$ $32$ $17$ $16$

answered Nov 9 in Graph Theory by `JEET Boss (13.1k points) | 54 views

+32 votes

5 answers

39

GATE2006-24
Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A⊆N and B⊆N, how many of the n! permutations $\pi$ from N to N satisfy min($\pi$(A)) = min($\pi$(B)), where min(S) is the smallest integer in the set of integers S, and $\pi$(S) is the set of integers obtained by applying ... $n! \frac{|A ∩ B|}{|A ∪ B|}$ $\dfrac{|A ∩ B|^2}{^n \mathrm{C}_{|A ∪ B|}}$

answered Nov 7 in Set Theory & Algebra by Sourajit25 Active (1.3k points) | 2.9k views

+1 vote

1 answer

40

#ACE ACADEMY BOOKLET QUESTION
The solution of $\sqrt{a_n} – 2\sqrt{a_{n-1}} + \sqrt{a_{n-2}} = 0$ where $a_0 = 1$ and $a_1 = 2$ is ${\Big[\frac{2^{n+1} + (-1)^n}{3}\Big]}^2$ $(n+1)^2$ $(n-1)^3$ $(n-1)^2$

answered Nov 5 in Combinatory by techbd123 Active (3.1k points) | 129 views

To see more, click for all the questions in this category.

Recent questions and answers in Discrete Mathematics

50,648 questions

56,441 answers

195,294 comments

100,084 users