Recent questions and answers in Discrete Mathematics - GATE Overflow

+6 votes

8 answers

1

TIFR2018-B-1
What is the remainder when $4444^{4444}$ is divided by $9?$ $1$ $2$ $5$ $7$ $8$

answered 2 days ago in Combinatory by Lakshman Patel RJIT Veteran (58.7k points) | 558 views

+50 votes

6 answers

2

GATE2006-25
Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$ then $ \sum_{i=1}^{m} f(i)$ is: $3m$ $3n$ $2m+1$ $2n+1$

answered 2 days ago in Set Theory & Algebra by Madhab Loyal (5.7k points) | 3k views

+33 votes

6 answers

3

GATE2016-2-26
A binary relation $R$ on $\mathbb{N} \times \mathbb{N}$ is defined as follows: $(a, b) R(c, d)$ if $a \leq c$ or $b \leq d$. Consider the following propositions: $P:$ $R$ is reflexive. $Q:$ $R$ is transitive. Which one of the following statements is TRUE? Both $P$ and $Q$ are true. $P$ is true and $Q$ is false. $P$ is false and $Q$ is true. Both $P$ and $Q$ are false.

answered 2 days ago in Set Theory & Algebra by arjuno (275 points) | 4.8k views

+31 votes

8 answers

4

GATE2005-IT-36
Let $P(x)$ and $Q(x)$ ...

answered 3 days ago in Mathematical Logic by Madhab Loyal (5.7k points) | 4.5k views

+1 vote

1 answer

5

Made Easy Test Series 2019: Combinatory - Permutations And Combinations
in how many ways 6 letters can be placed in 6 envelopes such that at least 4 letters go into their corresponding envelopes ?

answered 4 days ago in Combinatory by suvradip das (149 points) | 199 views

+37 votes

2 answers

6

GATE1991-16,a
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's.$

answered 4 days ago in Combinatory by Rishiryanemo (19 points) | 1.6k views

0 votes

1 answer

7

ugc net 2018 july-79

answered 6 days ago in Mathematical Logic by mishrapankajs (11 points) | 249 views

+26 votes

4 answers

8

GATE2001-2.1
How many $4$-digit even numbers have all $4$ digits distinct $2240$ $2296$ $2620$ $4536$

answered 6 days ago in Combinatory by Kushagra गुप्ता Active (4k points) | 3.8k views

+39 votes

7 answers

9

GATE2005-44
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 \mod 5$ $4$ $6$ $16$ $24$

answered 6 days ago in Combinatory by Kushagra गुप्ता Active (4k points) | 4.7k views

+1 vote

1 answer

10

ISRO2020-76
If $A=\{x,y,z\}$ and $B=\{u,v,w,x\}, $ and the universe is $\{s,t,u,v,w,x,y,z\}$ Then $(A \cup B’) \cap (A \cap B)$ is equal to $\{u,v,w,x\}$ $\{ \ \}$ $\{u,v,w,x,y,z\}$ $\{u,v,w\}$

answered Jan 13 in Set Theory & Algebra by habedo007 Active (2.8k points) | 116 views

+1 vote

1 answer

11

ISRO2020-73
Given that $B(a)$ means “$a$ is a bear” $F(a)$ means “$a$ is a fish” and $E(a,b)$ means “$a $ eats $b$” Then what is the best meaning of $\forall x [F(x) \to \forall y(E(y,x)\rightarrow b(y))]$ Every fish is eaten by some bear Bears eat only fish Every bear eats fish Only bears eat fish

answered Jan 13 in Mathematical Logic by chirudeepnamini Active (4.3k points) | 152 views

+2 votes

1 answer

12

GO2019-FLT1-11
Which one of the following best expresses the generating function sequence $\{a_n\}$, for the given closed form representation? $F(x) = \frac{1}{1-x-x^2}$ $a_n=a_{n-1}+3, n>0, a_0=1$ $a_n=a_{n-1}+a_{n-2}, n>1, a_0=1, a_1=1$ $a_n=2n+3, n>1$ $a_n=2a_{n-1}+3, n>1, a_0=1$

answered Jan 12 in Set Theory & Algebra by blackcloud (469 points) | 306 views

+15 votes

7 answers

13

GATE2005-50
Let $G(x) = \frac{1}{(1-x)^2} = \sum\limits_{i=0}^\infty g(i)x^i$, where $|x| < 1$. What is $g(i)$? $i$ $i+1$ $2i$ $2^i$

answered Jan 9 in Combinatory by arjuno (275 points) | 1.9k views

+21 votes

6 answers

14

GATE2005-IT-34
Let $n =$ $p^{2}q$, where $p$ and $q$ are distinct prime numbers. How many numbers m satisfy $1 ≤ m ≤ n$ and $gcd$ $(m, n) = 1?$ Note that $gcd$ $(m, n)$ is the greatest common divisor of $m$ and $n$. $p(q - 1)$ $pq$ $\left ( p^{2}-1 \right ) (q - 1)$ $p(p - 1) (q - 1)$

answered Jan 9 in Set Theory & Algebra by arjuno (275 points) | 2k views

+28 votes

2 answers

15

GATE2003-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\)

answered Jan 9 in Combinatory by arjuno (275 points) | 2.6k views

+16 votes

10 answers

16

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 Jan 6 in Combinatory by Çșȇ ʛấẗẻ Active (1.9k points) | 6.9k views

+47 votes

5 answers

17

GATE2007-IT-25
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$

answered Jan 6 in Graph Theory by endurance1 (13 points) | 5.4k views

+1 vote

3 answers

18

ISI2019-MMA-27
A general election is to be scheduled on $5$ days in May such that it is not scheduled on two consecutive days. In how many ways can the $5$ days be chosen to hold the election? $\begin{pmatrix} 26 \\ 5 \end{pmatrix}$ $\begin{pmatrix} 27 \\ 5 \end{pmatrix}$ $\begin{pmatrix} 30 \\ 5 \end{pmatrix}$ $\begin{pmatrix} 31 \\ 5 \end{pmatrix}$

answered Jan 6 in Combinatory by Navneet Singh Tomar Junior (735 points) | 2.8k views

0 votes

1 answer

19

Kenneth Rosen Edition 7th Exercise 1.7 Question 7 (Page No. 91)
Use a direct proof to show that every odd integer is the difference of two squares.

answered Jan 5 in Mathematical Logic by vedantbonde19 (29 points) | 23 views

0 votes

1 answer

20

Kenneth Rosen Edition 7th Exercise 1.7 Question 15 (Page No. 91)
Use a proof by contraposition to show that if $x+y≥2$,where $x$ and $y$ are real numbers, then $x≥1$ or $y≥1$.

answered Jan 5 in Mathematical Logic by vedantbonde19 (29 points) | 13 views

+1 vote

1 answer

21

Kenneth Rosen Edition 7th Exercise 1.7 Question 11 (Page No. 91)
Prove or disprove that the product of two irrational numbers is irrational.

answered Jan 5 in Mathematical Logic by vedantbonde19 (29 points) | 20 views

+1 vote

1 answer

22

Kenneth Rosen Edition 7th Exercise 1.7 Question 10 (Page No. 91)
Use a direct proof to show that the product of two rational numbers is rational.

answered Jan 5 in Mathematical Logic by vedantbonde19 (29 points) | 9 views

+29 votes

4 answers

23

GATE2015-2-54
Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$. Let $f$ be randomly chosen from $F$. The probability of $f$ being one-to-one is ______.

answered Jan 4 in Set Theory & Algebra by shivam001 Junior (963 points) | 2.7k views

+24 votes

3 answers

24

GATE1996-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 ]$

answered Jan 4 in Set Theory & Algebra by shivam001 Junior (963 points) | 2.6k views

+70 votes

8 answers

25

GATE2012-38
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$

answered Jan 3 in Graph Theory by JashanArora Loyal (6.2k points) | 11.3k views

+46 votes

4 answers

26

GATE2004-79
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k\\$ $^{\left(\frac{n^2-n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$

answered Jan 3 in Graph Theory by JashanArora Loyal (6.2k points) | 4.8k views

+1 vote

1 answer

27

ME FLT
Consider the following statements with respect to POSETs. I. Every non empty, finite POSET has at least one maximal and at least one minimal element. II. Every POSET has at most one greatest element and at most one least element. Which of the above statement(s) is/are true?

answered Jan 1 in Mathematical Logic by Veenit Active (1.6k points) | 44 views

+24 votes

4 answers

28

GATE1998-1.5
What is the converse of the following assertion? I stay only if you go I stay if you go If I stay then you go If you do not go then I do not stay If I do not stay then you go

answered Dec 31, 2019 in Mathematical Logic by JashanArora Loyal (6.2k points) | 3.5k views

+2 votes

1 answer

29

ISI 2004 MIII
Let $X$ be a nonempty set and let $\mathcal{P}(X)$ denote the collection of all subsets of $X.$ Define $\textit{f}:\textit{X$\times$ $\mathcal{P}$(X)}\rightarrow \mathbb{R}$ by $f(x,A) = \begin{cases} 1 \text{ if } x \in A & \\ 0 \text{ if } x \notin A & \end{cases}$ ... $f(x,A)+f(x,B) - f(x,A) \cdot f(x,B)$ $f(x,A)+ \mid f(x,A) - f(x,B) \mid$

answered Dec 31, 2019 in Set Theory & Algebra by ankitgupta.1729 Boss (17k points) | 150 views

0 votes

1 answer

30

$\textbf{NTA NET DEC 2019 (group)}$
Consider the following statements: $\mathbf{S_1:}\;\;$If a group $\mathbf{(G,*)}$ is of order $\mathbf n$ and $\mathrm {a \in G}$ is such that $\mathrm {a^n=e}$ for some integer $\mathrm {m \le n}$ then $\mathbf m$ must divide $\mathbf n$ ... $(3)\;\;\;\text{Niether}\; \mathrm{S_1}\;\text{nor}\;\mathrm{S_2}$

answered Dec 30, 2019 in Set Theory & Algebra by `JEET Boss (18.9k points) | 95 views

+2 votes

1 answer

31

GATE1987-9f
Give the composition tables (Cayley Tables) of the two non isomorphic groups of order 4 with elements $e, a, b, c$ where $c$ is the identity element. Use the order $e, a, b, c$ for the rows and columns.

answered Dec 30, 2019 in Set Theory & Algebra by ankitgupta.1729 Boss (17k points) | 216 views

+58 votes

10 answers

32

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 Dec 29, 2019 in Set Theory & Algebra by pranshu27 (21 points) | 8.2k views

0 votes

3 answers

33

Express the statement in logical expression
Express the statement "Everyone has exactly one best friend" as a logical expression involving predicates,quantifiers with a domain consisting of all people,and logical connectives without using uniqueness quantifier. I am confused pleased explain it

answered Dec 28, 2019 in Mathematical Logic by rohithk (11 points) | 470 views

0 votes

2 answers

34

ISI2016-MMA-13
Which one of the following statements is correct regarding the elements and subsets of the set $\{1, 2, \{1, 2, 3\}\}$? $\{1, 2\} \in \{1, 2, \{1, 2, 3\} \}$ $\{1, 2\} \subseteq \{1, 2, \{1, 2, 3\} \}$ $\{1, 2, 3\} \subseteq \{1, 2, \{1, 2, 3\} \}$ $3 \in \{1, 2, \{1, 2, 3\} \}$

answered Dec 26, 2019 in Set Theory & Algebra by smsubham Boss (11.5k points) | 23 views

0 votes

2 answers

35

Hasse Doubt
what is the least upper bound of {a, b, c}?

answered Dec 26, 2019 in Set Theory & Algebra by spike500 (41 points) | 131 views

+1 vote

1 answer

36

NTA NET DEC2019( shortest distance)
Consider a weighted directed graph. The current shortest distance from sources S to node x is represented by d[v] = 29 . d[u] = 15 , w[u,v] = 12. What is the updated value of d[v]based on current information? 1) 29 2) 27 3) 25 4) 17

answered Dec 26, 2019 in Graph Theory by `JEET Boss (18.9k points) | 67 views

+1 vote

3 answers

37

PGEE 2018
let 5,8,11,14,17,20.. be series then 320 will be which term of this series A) 104 B) 106 C) 962 D) 87

answered Dec 26, 2019 in Set Theory & Algebra by Yash4444 Junior (833 points) | 331 views

+18 votes

4 answers

38

GATE2015-1-54
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.

answered Dec 24, 2019 in Graph Theory by scholaraniket (479 points) | 5.6k views

+2 votes

2 answers

39

Euler Path
Which of the following Graph has Euler Path but is not an Euler Graph? A. K1,1 B.K2,10 C.K2,11 D.K10,11.

answered Dec 24, 2019 in Graph Theory by Nirmal Gaur Active (2.3k points) | 430 views

+1 vote

1 answer

40

ISI2017-DCG-11
The coefficient of $x^6y^3$ in the expression $(x+2y)^9$ is $84$ $672$ $8$ none of these

answered Dec 24, 2019 in Combinatory by swatiraoo45# (21 points) | 20 views

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

Recent questions and answers in Discrete Mathematics

50,737 questions

57,271 answers

198,137 comments

104,779 users