GATE CSE 2019 | Question: 5

Question

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

1. $\mid A \mid = n2^{n-1}$
2. $\mid A \mid = \Sigma_{k=1}^{n} k \begin{pmatrix} n \\ k \end{pmatrix}$

Which of the above statements is/are TRUE?

• A. Only I
• B. Only II
• C. Both I and II
• D. Neither I nor II

Comments

This is one of the exercise problem of Kenneth Rosen.

---

Does phi belong to phi?

If phi belongs to phi, then the case of (x, X) can also be (phi, phi). This case will missed in the count of given options. Right?

---

$\color{red}{\text{Detailed Video Solution:}}$ Combinatorial STORY for GATE CSE 2019 Question (Click HERE)

After watching above lecture, Watch This: https://youtu.be/HcLsvVbQnrc?t=634  

Answer 1

Option C: Both are correct.

$\displaystyle | \{X \mid X \subset U\}  | = \begin{pmatrix} n \\ 0 \end{pmatrix} + \begin{pmatrix} n \\ 1 \end{pmatrix} + \begin{pmatrix} n \\ 2 \end{pmatrix} + \cdots + \begin{pmatrix} n \\ n \end{pmatrix} = 2^n$

Now $x$ can be any element of the individual subset $X$.

So $\mid A \mid  = \begin{pmatrix} n \\ 0 \end{pmatrix}  \times 0 + \begin{pmatrix} n \\ 1 \end{pmatrix} \times 1 + \begin{pmatrix} n \\ 2 \end{pmatrix} \times 2 + \cdots + \begin{pmatrix} n \\ n \end{pmatrix} \times n = n \cdot 2^{n-1}$

Note here that for the case when our chosen subset is empty $(X = \emptyset)$, we don't have any member $x \in X$, and hence the term $\begin{pmatrix} n \\ 0 \end{pmatrix} \times 0$ is correct.

---

Proof that $\bf{\sum_{k=1}^n k \times \begin{pmatrix} n \\ k \end{pmatrix} = n \cdot 2^{n-1}}$

We have the Binomial Expansion:

$(1+x)^n = \begin{pmatrix} n \\ 0 \end{pmatrix} x^0 + \begin{pmatrix} n \\ 1 \end{pmatrix} x^1 + \begin{pmatrix} n \\ 2 \end{pmatrix} x^2 + \cdots + \begin{pmatrix} n \\ n \end{pmatrix} x^n$

Differentiating both sides w.r.t $x$, we get,

$n (1+x)^{n-1} = \begin{pmatrix} n \\ 1 \end{pmatrix} + 2 \times \begin{pmatrix} n \\ 2 \end{pmatrix} x + \cdots + n \times \begin{pmatrix} n \\ n \end{pmatrix} x^{n-1}$

Put $x = 1$ to get

$n \times 2^{n-1} = \begin{pmatrix} n \\ 1 \end{pmatrix} + 2 \times \begin{pmatrix} n \\ 2 \end{pmatrix} + \cdots + n \times \begin{pmatrix} n \\ n \end{pmatrix}$

Q.E.D.

Comments

but phi cant be an element of the given set. so x belongd to X is never  satisfied

---

Both r corrrct

---

@Ruturaj Mohanty

in first line $X \subseteq U$

and in summation $\sum_{k=1}^{n}$ ...you have written 0 to n ...please correct it.

---

@Shaik Masthan can you please explain the  first statement

---

You can think of it like :

In 2nd statement : You first select a subset of k elements and then select one of those k elements as head( representative) and thus find the total number of ways the subset can be formed

In 1st statement : First you select the set representative  and then select k-1 more members from remaining n-1.

 

Work it out using this logic and you will pave your way to the answer.

---

Can anyone tell me fromwhere  to study this kind of concept

---

@Ahabnnc
Yup. That's the intuitive idea.

BTW the idea in $1^{\mathrm{st}}$ statement can be like this below.

First select an element $x$. As we've already taken it, now we can make different subsets from $(n-1)$ elements for every $X$ meaning $2^{n-1}$ subsets. Since there are $n$ elements of choosing $x$, the answer will be $n\cdot2^{n-1}$.

---

The easiest way to to this question in the exam is just substitute $\mathbf{n = 2}$ and verify the answers.

For more satisfaction, if you want you can substitute $\mathbf{n = 3}$ and verify further.

---

@Satbir

can we relate this question into determinant?

---

No, question is asking about cardinality of A , in exam I thought that it was asking for determinant and thus got wrong answer.

---

Yes thanks.

Answer 2

APPROACH 1: Trial and Error

 

$\rightarrow$ For $n=2$, $U={1,2}$.

$\rightarrow$ The subsets of  $U$ are $\left \{ \Phi , \{1\},\{2 \}, \{1,2 \} \}\right.$

$\rightarrow$ So,set $X$ has $4$ possibilities as above.

$\rightarrow$ Seeing $x$ as element of $X$, $x$ can be $1$ or $2$ and nothing else.

$\rightarrow$ So $A$ is the set of ordered pairs where the $1^{st}$ part is an element of $X$ (it is a value of $x$) and the $2^{nd}$ part is a subset of $U$.

$\rightarrow$ There are $2$ possibilities for the $1^{st}$ part, and $4$ possibilities for the $2^{nd}$ part.

$\rightarrow$ i.e. $A$ can have: $(1,\Phi ), (1, \{1 \} ) ,(1, \{2 \}), (1,\{1,2 \}), (2,\Phi ), (2, \{1 \} ) ,(2, \{2 \}), (2,\{1,2 \})$

$\rightarrow$ Here $(1,\Phi)$ will not be considered, as $1$ $\notin$ $ \Phi$.

$\rightarrow$ Similarly, $(1, \{2 \}),(2,\Phi ),(2, \{1 \} )$ won't be considered on similar grounds.

$\rightarrow$ so $A=$ $(1, \{1 \} ), (1,\{1,2 \}),,(2, \{2 \}), (2,\{1,2 \})$

$\therefore $ $\begin{vmatrix} A \end{vmatrix} = 4$

$I.$ gives answer for $n=2$ as: $\begin{vmatrix} A \end{vmatrix} = 2*2 =4$

$II.$ gives answer for $n=2$ as: $\begin{vmatrix} A \end{vmatrix} =$ $1*^{2}C_{1}$ $+ 2 * $ $^2C_2$ $=4$

$\because$ Both $I.$ and $II.$ are True

$\therefore$ Option $C$ is the right answer.

---

 

APPROACH 2:

 

• To show $II.$ is correct:

$\rightarrow$ $A = \{y = (x,X)| X\ proper\ subset\ of\ U,\ x\ in X \}$.

$\rightarrow$ Lets first fix $X$. Here $X$ being proper subset of $U$, $X$ can have all values of that of a power Set of $U$.

$\rightarrow$ Lets say number of elements in $X$ is $k$.

$\because$ Number of elements of $U$ is $n$, $k$ can take values from $0$ to $n$ ($\because$ $X$ is proper subset of $U$)

$\therefore$ The number of ways of selecting $k$ from $n$ is given by $^{n}C_{k}$

$\rightarrow$ So we have $^{n}C_{k}$ choices for choosing $X$.

$\rightarrow$ Now, fixing our choice of $X$, and assuming it has $k$ elements, how many choices for $x$ are there ?

$\rightarrow$ There are $k$ different elements in $X$, so there are $k$ choices for choosing $x$

$\rightarrow$ For eg  $X= \{1,2,3 \} $, then $x$ can be $1$ or $2$ or $3$, as only these $3$ elements belong to $X$.

$\rightarrow$ So for a given $k$, there are $k* ^{n}C_{k}$ choices of $(x,X)$ such that $\begin{vmatrix} X \end{vmatrix} = k$

$\rightarrow$  So how many elements $y$ are there in total?

$\rightarrow$ Sum the above for $k =1$ to $n$. $k$ can't be $0$ because if $X$ has $0$ elements, then $x$ doesn't exist.

$\rightarrow$ i.e.$\begin{vmatrix} A \end{vmatrix}$ =  $\sum_{k=1} ^{n} k \binom{n}{k}$

 

• To show the formula for $I.$ is correct:

$\rightarrow$ Consider choosing an element $x$ in our pair $(x,X)$. There are $n$ choices for $x$.

$\rightarrow$ Then we ask ourselves how many valid choices of $X$ are there, given $x$ ?

$\rightarrow$ $X$ is entirely defined by its elements, and we have a finite list of potential elements $(1$ to $n)$.

$\rightarrow$ For each of these, an element is either in or out, giving us $2$ possibilities each time but $x$ is already fixed to be included in $X$ for it to belong in $X$ .

$\because$ out of $n$ elements, only $x$ has $1$ choice to be included, and all the other $n-1$ elements can have $2$ possibilities as to be included or excluded in $X$.

$\because$  Its an ordered pair, we need both these conditions happening together, so using $product\ rule$ we arrive at $n*2^{n-1}$ choices for $(x,X)$.

$\because$ Both $I.$ and $II.$ are True

$\therefore$ Option $C$ is the right answer.

Comments

In this question main thing is

What $\in$ do and what $\subseteq$ do, for a set.

Can u give example of it??

Say for Set $S=\left \{ 2,3,\left \{ 4 \right \} \right \}$

include contains $\left \{ 3,\left \{ 4 \right \} \right \}$  and it is not a set here, it is an element(though looks like a subset)

but subset of tht set i.e. $\subseteq \left \{ 3,\left \{ 4 \right \} \right \}$ is false

because subset will be $\subseteq\left \{ \left \{ 3,\left \{ 4 \right \} \right \} \right \}$

right??

---

For X={2,3,{4}}

INCLUDE HAS ANY SINGLE ENTITY OF THE SET.

INCLUDE(BELONGS TO) IS AN OPERATOR TO THE RIGHT OF WHICH THERE IS A SET, AND TO THE LEFT OF WHICH THERE ARE ENTITIES WHICH ARE PART OF THAT SET. THAT IS- 2∈X , 3∈X and {4}∈X. Does any other element is included in X? No!Like- X doesn't include {3} or 4

since left side of belongs to operator has single entities which are part of set, we cannot club 2 values together and say they belong to X, because clubbing values means making them a set. If you make them a set then that set itself must be contained in X. Like- {2,{3}}$\notin$X.

But, if Y={9,10,{2,{3}}}, then separate out the single entities of the set Y. These are 9 and 10 and {2,{3}}

So, {2,{3}}∈Y.

Now, X$\subseteq$Y means, Elements in X are all available in Y but Y can have more elements than X or equal to it, but all the elements of X will be in Y. So, unlike 'belongs to', here we can combine values since we are comparing set with a set. It means, a subset operator has RHS and LHS as set.

Now the question asks for formula which satisfies set A. So, we are calculating all possible values which could be included in the answer for a given 'n'.

Hence, we are including all the single entities in place of X, and all the possible subsets possible for U as X can be any one of those possible subsets.

Subsets of X={2,3,{4}} are-

1) empty set

2){2} it is a subset of X as 2 is in X.

3){3}

4){{4}} since {4} is in X

5){2,3} since 2 and 3 are in X

6){2,{4}}

7){3,{4}}

8){2,3,{4}} is an improper subset, since all its entities belong to X and X doesn't contain any extra entity.

{2,3,4} is not subset of X as 4 is not in X.

---

Could anyone explain why this is not considered in A
{Φ,{Φ}}?

Edit : Got it I considered U as power set

Answer 3

$2^{nd}$ statement is easy one

Proof for  $1^{st}$  statement using $2^{nd}$ statement

 

 

Answer 4

Watch my video for clarity

Thanks

https://www.youtube.com/watch?v=MoHPa-Gd3Ug&t=36s