in Combinatory edited by
11,307 views
28 votes
28 votes

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?

  1. Only I
  2. Only II
  3. Both I and II
  4. Neither I nor II
in Combinatory edited by
by
11.3k views

4 Comments

This is one of the exercise problem of Kenneth Rosen.
2
2
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?
1
1
edited by

$\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  

4
4

4 Answers

41 votes
41 votes
Best answer

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.

selected by

4 Comments

@Satbir

can we relate this question into determinant?

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

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.

edited by

4 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??
0
0
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.
0
0
Could anyone explain why this is not considered in A
{Φ,{Φ}}?

Edit : Got it I considered U as power set
0
0
15 votes
15 votes

$2^{nd}$ statement is easy one

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

 

 

3 votes
3 votes

Watch my video for clarity

Thanks

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

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true