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

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,.....?} $

Subjects of Engineering Mathematics