# GATE Questions & Answers of Discrete Mathematics Computer Science and Information Technology

#### Discrete Mathematics 4 Question(s)

Let $U=\{1,2,\;...\;,\;n\}.$ Let $A=\{(x,\;X)\;\vert x\in X,\;X\subseteq U\}.$ Consider the following two statements on |A|.

I.  $\vert A\vert=n2^{n-1}$

II. $\vert A\vert={\textstyle\sum_{k=1}^n}k\begin{pmatrix}n\\k\end{pmatrix}$

Which of the above statements is/are TRUE?

Let $G$ be an arbitrary group. Consider the following relations on $G$:

$R_1:\forall a,\;b\in G,\;a\;R_1b$ if and only if $\exists g\in G$ such that $a=g^{-1}bg$

$R_2:\forall a,\;b\in G,\;a\;R_2b$ if and only if $a=b^{-1}$

Which of the above is/are equivalence relation/relations?

Consider the first order predicate formula $\varphi$:

$\forall x\lbrack(\forall z\;z\vert x\Rightarrow((z=x)\vee(z=1)))\Rightarrow\exists w\;(w>x)\wedge(\forall z\;z\vert w\Rightarrow((w=z)\vee(z=1)))\rbrack$ Here $'a\vert b'$ denotes that ‘$a$ divides $b$’, where $a$ and $b$ are integers. Consider the following sets:

S1.   {1,2,3, … , 100}

S2.   Set of all positive integers

S3.   Set of all integers

Which of the above sets satisfy $\varphi$?

Which one of the following is a closed form expression for the generating function of the sequence $\style{font-family:'Times New Roman'}{\left\{a_n\right\}\;,}$ where $\style{font-family:'Times New Roman'}{a_n=2n+3}$ for all $\style{font-family:'Times New Roman'}{n=0,1,2,.....?}$