# Recent questions and answers in Discrete Mathematics

1
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2}$
2
Consider the following well-formed formulae: $\neg \forall x(P(x))$ $\neg \exists x(P(x))$ $\neg \exists x(\neg P(x))$ $\exists x(\neg P(x))$ Which of the above are equivalent? I and III I and IV II and III II and IV
1 vote
3
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$
4
Let $G$ be an arbitrary group. Consider the following relations on $G$: $R_1: \forall a , b \in G, \: a R_1 b \text{ if and only if } \exists g \in G \text{ such that } a = g^{-1}bg$ $R_2: \forall a , b \in G, \: a R_2 b \text{ if and only if } a= b^{-1}$ Which of the above is/are equivalence relation/relations? $R_1$ and $R_2$ $R_1$ only $R_2$ only Neither $R_1$ nor $R_2$
5
What is logically equivalent to "If Kareena and Parineeti go to the shopping mall then it is raining": If Kareena and Parineeti do not go to the shopping mall then it is not raining. If Kareena and Parineeti do not go to the shopping mall then it is raining. If it ... go to the shopping mall. If it is not raining then Kareena and Parineeti do not go to the shopping mall. None of the above.
6
A line $L$ in a circuit is said to have a $stuck-at-0$ fault if the line permanently has a logic value $0$. Similarly a line $L$ in a circuit is said to have a $stuck-at-1$ fault if the line permanently has a logic value $1$. A circuit is said to have a multiple $stuck-at$ ... total number of distinct multiple $stuck-at$ faults possible in a circuit with $N$ lines is $3^N$ $3^N - 1$ $2^N - 1$ $2$
7
$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$
8
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$
9
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
10
The number of binary strings of $n$ zeros and $k$ ones in which no two ones are adjacent is $^{n-1}C_k$ $^nC_k$ $^nC_{k+1}$ None of the above
11
How many sub strings of different lengths (non-zero) can be formed from a character string of length $n$? $n$ $n^2$ $2^n$ $\frac{n(n+1)}{2}$
12
The number of substrings (of all lengths inclusive) that can be formed from a character string of length $n$ is $n$ $n^2$ $\frac{n(n-1)}{2}$ $\frac{n(n+1)}{2}$
13
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of ... 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex? (A) 3 (B) 0 (C) 5 (D) 4
14
15
16
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins? $3^{35}$ $3^{50}-2^{50}$ $\binom{35}{2}$ $\binom{50}{15} \cdot 3^{35}$ $\binom{37}{2}$
17
1 vote
18
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... $x$ and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________
19
Which of the above lattice is distributve? a) both iii and iv) b) only iv)
20
Answer given is option C , But vertex 10 do not have compliment then how it can be a Boolean algebra ? Also please explain , as no element has compliment greater than 1 , it may or may not be distributive then is there any feasible way to differentiate between option a and d ? Thank you ! P.S : Without using distributive law check, i think its not feasible for more number of vertices.
21
For the composition table of a cyclic group shown below: ... $a,b$ are generators $b,c$ are generators $c,d$ are generators $d,a$ are generators
22
1 vote
23
24
Let the number of non-isomorphic groups of order 10 be X and number of non-isomorphic groups of order 24 be Y then the value of X and Y a) 3,2 b)2,7 c)1,7 d)4,5
25
Consider the following first order logic statement $I)\forall x\forall yP\left ( x,y \right )$ $II)\forall x\exists yP\left ( x,y \right )$ $III)\exists x\exists yP\left ( x,y \right )$ $III)\exists x\forall yP\left ( x,y \right )$ ... $II)$ is true , then $III),IV)$ is true $B)$ If $IV)$ is true , then $II),III)$ is true $C)$ None of these
26
Provide short answers to the following questions: How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.
27
The formula for the number of positive integers m which are less than p^k and relatively prime to p^k, where p is a prime number and k is a positive integer is__________- A)p^k(p-1) B)(p^(k-2))(p-1) C)p^k(p-2) D)(p^(k-1))(p-1)
28
Three candidates, Amar, Birendra and Chanchal stand for the local election. Opinion polls are conducted and show that fraction $a$ of the voters prefer Amar to Birendra, fraction $b$ prefer Birendra to Chanchal and fraction $c$ ... $(a, b, c) = (0.49, 0.49, 0.49);$ None of the above.
29
Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 \subset S_2$ or $S_2\subset S_1$. What is the maximum cardinality of C? $n$ $n+1$ $2^{n-1} + 1$ $n!$
30
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$
31
Let $A$ and $B$ be sets and let $A^c$ and $B^c$ denote the complements of the sets $A$ and $B$. The set $(A-B) \cup (B-A) \cup (A \cap B)$ is equal to $A \cup B$ $A^c \cup B^c$ $A \cap B$ $A^c \cap B^c$
32
The number of elements in the power set $P(S)$ of the set $S=\{\{\emptyset\}, 1, \{2, 3\}\}$ is: $2$ $4$ $8$ None of the above
33
Which of the following graphs is/are planner?
34
Write the adjacency matrix representation of the graph given in below figure.
35
Hello can anyone suggest good video/book to learn generating functions from?..i tried the nptel lecture..it has some audio lag. and i could not make much out of it..I am well versed in combinatorics but my calculus is weak.. Please suggest some resource that teaches generating functions from scratch
36
37
How many ways are there to assign colours from range $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4} - 4r^{3}$ $r^{4}-5r^{3}+8r^{2}-4r$ $r^{4}-4r^{3}+9r^{2}-3r$ $r^{4}-5r^{3}+10r^{2}-15r$
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows: ... $(b * x) + (c * y) = c$ The number of solution(s) (i.e., pair(s) $(x, y)$ that satisfy the equations) is $0$ $1$ $2$ $3$
Which one is the correct translation of the following statement into mathematical logic? “None of my friends are perfect.” $\neg\:\exists\:x(p(x)\land q(x))$ $\exists\:x(\neg\:p(x)\land q(x))$ $\exists\:x(\neg\:p(x)\land\neg\:q(x))$ $\exists\:x(p(x)\land\neg\:q(x))$