Recent questions and answers in Discrete Mathematics

+18 votes

5 answers

1

GATE2002-2.17
The binary relation $S= \phi \text{(empty set)}$ on a set $A = \left \{ 1,2,3 \right \}$ is Neither reflexive nor symmetric Symmetric and reflexive Transitive and reflexive Transitive and symmetric

answered 16 hours ago in Set Theory & Algebra by pritishc (57 points) | 2.6k views

+1 vote

1 answer

2

Graph Coloring
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ? There is a condition that adjacent vertices should not be of the same color I am getting $1680$. Is it correct?

answered 2 days ago in Graph Theory by Satbir Boss (13.2k points) | 257 views

0 votes

1 answer

3

Planar Graph
Can minimum degree of a planar graph be $5$? Give some example

answered 3 days ago in Graph Theory by Satbir Boss (13.2k points) | 219 views

+20 votes

12 answers

4

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

answered 5 days ago in Combinatory by Kuldeep Pal Active (1.3k points) | 7.3k views

+37 votes

11 answers

5

GATE2015-3-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 ________.

answered 5 days ago in Combinatory by Kuldeep Pal Active (1.3k points) | 3.8k views

+23 votes

7 answers

6

GATE2004-IT-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$

answered 5 days ago in Combinatory by Kuldeep Pal Active (1.3k points) | 2.5k views

+9 votes

3 answers

7

GATE1998-2.4
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 whereas $13$ persons speak both Kannada and English. How many speak all three languages? $9$ $8$ $7$ $6$

answered 5 days ago in Set Theory & Algebra by Nithin2698 (25 points) | 1.1k views

+1 vote

2 answers

8

Model Question IISc CDS CS Written Test Sample question
Anand is preparing a pizza with 8 slices, and he has 10 toppings to put on the pizza. He can put only one topping on each slice but can use the same topping on zero or more slices. In how many unique ways can he prepare the slices so that the same topping is not used in adjacent slices?

answered 5 days ago in Combinatory by Satbir Boss (13.2k points) | 205 views

+10 votes

4 answers

9

GATE1989-1-iv
The transitive closure of the relation $\left\{(1, 2), (2, 3), (3, 4), (5, 4)\right\}$ on the set $\left\{1, 2, 3, 4, 5\right\}$ is ___________.

answered 6 days ago in Set Theory & Algebra by mohan123 (135 points) | 679 views

+19 votes

3 answers

10

TIFR2014-A-5
The rules for the University of Bombay five-a-side cricket competition specify that the members of each team must have birthdays in the same month. What is the minimum number of mathematics students needed to be enrolled in the department to guarantee that they can raise a team of students? $23$ $91$ $60$ $49$ None of the above.

answered Jun 17 in Combinatory by Kuldeep Pal Active (1.3k points) | 821 views

+34 votes

7 answers

11

GATE2017-2-47
If the ordinary generating function of a sequence $\left \{a_n\right \}_{n=0}^\infty$ is $\large \frac{1+z}{(1-z)^3}$, then $a_3-a_0$ is equal to ___________ .

answered Jun 17 in Combinatory by mohan123 (135 points) | 5.4k views

+13 votes

8 answers

12

GATE2018-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}$

answered Jun 17 in Combinatory by Kuldeep Pal Active (1.3k points) | 5.7k views

+2 votes

1 answer

13

GATE1999-4
Let $G$ be a finite group and $H$ be a subgroup of $G$. For $a \in G$, define $aH=\left\{ah \mid h \in H\right\}$. Show that $|aH| = |bH|.$ Show that for every pair of elements $a, b \in G$, either $aH = bH$ or $aH$ and $bH$ are disjoint. Use the above to argue that the order of $H$ must divide the order of $G.$

answered Jun 16 in Set Theory & Algebra by Satbir Boss (13.2k points) | 476 views

+8 votes

3 answers

14

TIFR2011-B-23
Suppose $(S_{1}, S_{2},\ldots,S_{m})$ is a finite collection of non-empty subsets of a universe $U.$ Note that the sets in this collection need not be distinct. Consider the following basic step to be performed on this sequence. While there exist sets $S_{i}$ and ... of a finite universe $U$ and a choice of $S_{i}$ and $S_{j}$ in each step such that the process does not terminate.

answered Jun 16 in Set Theory & Algebra by Arjun Veteran (408k points) | 349 views

+16 votes

3 answers

15

GATE1998-11
Suppose $A = \{a, b, c, d\}$ and $\Pi_1$ is the following partition of A $\Pi_1 = \left\{\left\{a, b, c\right\}\left\{d\right\}\right\}$ List the ordered pairs of the equivalence relations induced by $\Pi_1$. Draw the graph of the above equivalence relation ... $\left\langle\left\{\Pi_1, \Pi_2, \Pi_3, \Pi_4\right\}, \text{ refines } \right\rangle$.

answered Jun 15 in Set Theory & Algebra by Satbir Boss (13.2k points) | 1.6k views

+7 votes

1 answer

16

TIFR2018-B-10
For two $n$ bit strings $x,y \in\{0,1\}^{n},$ define $z=x\oplus y$ to be the bitwise XOR of the two strings (that is, if $x_{i},y_{i},z_{i}$ denote the $i^{th}$ bits of $x,y,z$ respectively, then $z_{i}=x_{i}+y_{i} \bmod 2$ ... The number of such linear functions for $n \geq 2$ is: $2^{n}$ $2^{n^{2}}$ $\large2^{\frac{n}{2}}$ $2^{4n}$ $2^{n^{2}+n}$

answered Jun 14 in Set Theory & Algebra by Arjun Veteran (408k points) | 224 views

+17 votes

3 answers

17

GATE1999-2.2
Two girls have picked $10$ roses, $15$ sunflowers and $15$ daffodils. What is the number of ways they can divide the flowers among themselves? $1638$ $2100$ $2640$ None of the above

answered Jun 14 in Combinatory by bruce-bayne (21 points) | 3.6k views

0 votes

1 answer

18

MadeEasy Test Series: Probability
How to get the idea that we have to use Binomial distribution or Hypergeometric Distribution. I know that if the probability is not changing(i.e with replacement) then we go Binomial otherwise Hypergeometric. But in question, it is not indicating ... So is there any by default approach that we have to use Binomial if nothing is a mention about a replacement.

answered Jun 13 in Mathematical Logic by vizzard110 (39 points) | 28 views

+1 vote

1 answer

19

Doubt
How many distinct unlabeled graphs are there with 4 vertices and 3 edges?

answered Jun 13 in Graph Theory by Gyanu Active (1.5k points) | 65 views

0 votes

1 answer

20

Zeal Test Series 2019: Graph Theory - Graph Connectivity

answered Jun 12 in Graph Theory by Gyanu Active (1.5k points) | 74 views

+2 votes

3 answers

21

Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? Vertex $n$ has degree $1$ Graph is connected There is a path from vertex $1$ to vertex $n$ Spanning tree will include edge connecting vertex $1$ and vertex $n$

answered Jun 12 in Graph Theory by Sainath Mandavilli (23 points) | 100 views

0 votes

2 answers

22

ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree-1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree-4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.

answered Jun 12 in Graph Theory by Akanksha Agrawal (33 points) | 62 views

0 votes

2 answers

23

Self Doubt-Combinatory
In how many ways we can put $n$ distinct balls in $k$ dintinct bins?? Will it be $n^{k}$ or $k^{n}$?? Taking example will be easy way to remove this doubt or some other ways possible??

answered Jun 9 in Combinatory by Koushik Sinha 2 (253 points) | 61 views

+3 votes

5 answers

24

TIFR2019-B-13
A row of $10$ houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a red or a blue house must be green. How many ways are there to paint the houses? $199$ $683$ $1365$ $3^{10}-2^{10}$ $3^{10}$

answered Jun 8 in Combinatory by shaktisingh (91 points) | 280 views

+1 vote

2 answers

25

GATE1990-17c
Show that the elements of the lattice $(N, \leq)$, where $N$ is the set of positive intergers and $a \leq b$ if and only if $a$ divides $b$, satisfy the distributive property.

answered Jun 8 in Set Theory & Algebra by Arjun Veteran (408k points) | 239 views

+3 votes

1 answer

26

TIFR2017-B-6
Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE? Partial orders cannot be axiomatized in FOL FOL has a complete proof system Natural numbers cannot be axiomatized in FOL Real numbers cannot be axiomatized in FOL Relational numbers cannot be axiomatized in FOL

answered Jun 8 in Mathematical Logic by Arjun Veteran (408k points) | 176 views

0 votes

1 answer

27

TIFR2019-B-12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every ... $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle

answered Jun 8 in Graph Theory by Arjun Veteran (408k points) | 240 views

0 votes

1 answer

28

UGCNET-July-2018-II-76
Consider the following statements: False $\models$ True If $\alpha \models (\beta \wedge \gamma \text{ then } \alpha \models \gamma$ Which of the following is correct with respect to above statements? Both statement a and statement b are false Statement a is true and statement b is false Statement a is false and statement b is true Both statement a and statement b are true

answered Jun 8 in Discrete Mathematics by Irfanshaan (11 points) | 416 views

+7 votes

1 answer

29

GATE1987-9e
How many true inclusion relations are there of the from $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?

answered Jun 7 in Set Theory & Algebra by Arjun Veteran (408k points) | 436 views

0 votes

1 answer

30

ISI2017-MMA-26
Let $n$ be the number of ways in which 5 men and 7 women can stand in a queue such that all the women stand consecutively. Let $m$ be the number of ways in which the same 12 persons can stand in a queue such that exactly 6 women stand consecutively. Then the value of $\frac{m}{n}$ is $5$ $7$ $5/7$ $7/5$

answered Jun 7 in Combinatory by venkatesh pagadala (495 points) | 27 views

0 votes

1 answer

31

GATE1988-14i
Consider the following well-formed formula: $\exists x \forall y [ \neg \: \exists z [ p (y, z) \wedge p (z, y) ] \equiv p(x,y)]$ Express the above well-formed formula in clausal form.

answered Jun 7 in Mathematical Logic by Arjun Veteran (408k points) | 145 views

0 votes

1 answer

32

GATE1995-25b
Determine the number of positive integers $(\leq 720)$ which are not divisible by any of $2,3$ or $5.$

answered Jun 6 in Set Theory & Algebra by Arjun Veteran (408k points) | 73 views

+1 vote

2 answers

33

UGCNET-Dec2015-II-6
Which of the following arguments are not valid ? "If Gora gets the job and works hard, then he will be promoted. if Gora gets promotion, then he will be happy. He will not be happy, therefore, either he will not get the job or he will not work hard." "Either Puneet is not ... $n^2 > 1$, then $n>1$. a and c b and c a,b, and c a and b

answered Jun 6 in Mathematical Logic by Satbir Boss (13.2k points) | 1.4k views

+2 votes

1 answer

34

GATE1987-9d
Specify an adjacency-lists representation of the undirected graph given above.

answered Jun 5 in Graph Theory by Satbir Boss (13.2k points) | 298 views

0 votes

0 answers

35

#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$

asked Jun 5 in Combinatory by `JEET Active (3.3k points) | 67 views

0 votes

1 answer

36

Mathematical Logic Ques:Self doubt
“Not every satisfiable logic is valid” Representation of it will be $1)\sim \left ( \forall S(x)\rightarrow V(x) \right )$ or $2)\sim \left ( \forall S(x)\vee V(x) \right )$ Among $1)$ and $2)$, which one is correct? and why?

answered Jun 4 in Mathematical Logic by Satbir Boss (13.2k points) | 72 views

0 votes

2 answers

37

#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 88 views

+1 vote

1 answer

38

#ACE_ACADEMY_DISCRETE_MATHS_BOOKLET.
Which of the following is not true? (a) Number of edge-disjoint Hamiltonian cycles in $K_7$ is $3$ (b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in ... simple graph with $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$ Please help me understand all the options.

answered Jun 4 in Graph Theory by chandan2teja (117 points) | 31 views

0 votes

1 answer

39

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

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 49 views

+2 votes

2 answers

40

GateForum Question Bank :Graph Theory
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 102 views

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 questions and answers in Discrete Mathematics

Recent Posts

Recent Blog Comments