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

For n = 4 option 1 is not equivalent to option 2 . Option 1 is true only for few values of n (n<=3) so answer should be only option 2 . Plz check @Arjun

---

@Jagmeet1996 

for n=4

I) $ 4*2^3=32$ II) 4 + 6*2 +4*3 + 4=32.

---

No, both the statements are correct

---

A simple combinatorial proof:

Both LHS and RHS answer the following question: select a commitee of any size with a president, from a group of $n$ people.

The summation one is pretty obvious, $n \choose k$$\times k$, summed over all possible values of $k$.

For the second equation, first select a president. This can be done in $n$ ways. Now, for the rest of the elements, they can be in or out of the committee, so there are a total of $n \times 2^{n-1}$ ways.

---

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  

---

Not possible bro. Phi is an empty set how it can contain anything.

---

sir ek doubt hai can u help 2^n-1 give all possible subsets that are possible thats fine but we are multiplying it by nc1 y thats the case story samjh aagyi but multiply kyun kiye

humlog ne nc1 * 2^n-1 kr diya multiply ki basis pe kiye

---

How to think a Question in another ways :

Think  in terms of system architecture. Suppose $U$ is a pool of $n$ available servers.

1. We want to form a computing cluster ($X$) from these available servers.

2. From within that chosen cluster, we must designate exactly one server to act as the "master node" ($x$).

   The set $A$ represents all the possible (master node, cluster) configurations we can create.

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution    

---

$Method$ $1:$ $Story$ $Method$ $(Best Method)$
$Method$ $2:$ $by$ $Taking$ $value$ $of$ $n$ 
$Method$ $3:$ $By$ $differentiating$ $(1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$ $and$ $then$ $put$ $x=1$

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

not getting

---

Great soln!!

---

just find : sum of size of each subset of U.(think about it)

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

The core skill you need to have is counting in two ways.

When you see a set like A = {(x, X) | x ∈ X, X ⊆ U}, you're counting pairs.

What are the two things in the pair?

Here: (element, subset)

When counting pairs, there are always two ways to group:

Approach	Question to ask
Fix the first thing	"For each element x, how many subsets contain it?"
Fix the second thing	"For each subset X, how many elements does it have?"

 

Method 1: Fix the element

Let me fix x = 1. How many subsets contain 1?

subsets containing 1 = {1} ∪ (any subset of the rest) = 2^(n-1)

Same for every element. There are n elements.

Total = n × 2^(n-1) ✓

Method 2: Fix the subset

Let me group subsets by size.

How many subsets of size k? We're choosing k elements from n elements. → C(n,k)

Each such subset contributes how many pairs? 

Each element can form a pair (element, X).

So k pairs per subset of size k.

Total from size-k subsets? → k × C(n,k)

Add them all up:  Σ k·C(n,k) ✓

Comments

this one's the exact same explaination that i would've posted for this question. Nice!

Answer 5

Good Luck