edited by
12,469 views
14 votes
14 votes

Let U = {1, 2, ..., n} and A = {(x, X), x ∈ X and X ⊆ U}. Consider the following two
statements for |A|.

  1. (i) |A| = n*$\small 2^{n-1}$

(ii) |A|= Sigma(k=1 to n) k.(nCk) 
Which of the following is correct?
(a) (i) only (b) (ii) only
(c) Both (i) and (ii) (d) None of the above

edited by

5 Answers

14 votes
14 votes
Let U=$\{1,2,3\}$

All Possible subsets of U = $\{\phi,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

$A = {(x, X), x ∈ X \ and\ X ⊆ U}$

$x$ can be only $\{\phi,1,2,3\}${Considering $\phi$ also a valid $x$}

Now A can have elements like :- $\{1,\{1,2\}\}$ {Here X is $\{1,2\}$ }.

When $x=1$ , total elements in A = 4.

Similarly for $x=2$ and $x=3$ , total elements in A would be 4,4 respectively.

Therefore, total elements in A , $i.e \ |A|$ = $4+4+4 = 12$.

Not considering $x=\phi$ and $X=\phi$ since $\phi \in \phi $ is not true.
Now comparing against options ,

option (i) -> $n*2^{(n-1)}$ when n=3 , this option gives $12$ , matches.

option (ii) -> $\sum_{k=1}^{n}k*n_{C_{k}} = 1*3_{C_{1}} + 2*3_{C_{2}}+3*3_{C_{3}} = 3 + 6 +3 = 12.$

Thus both are correct.
2 votes
2 votes
I think this could be an equivalence explanation for the two options:

Option 2 says : |A|= Sigma(k=1 to n) k.(nCk) : This can be thought of as number of ways to choose k-member-team from n people and then selecting 1 among those k as the team leader. And then it sums over all k.

Option 1 says: Select 1 team leader from n people and then select k-1 other team members from remaining n-1 people which will be : n*((n-1)C(k-1)) and sum over all k here will give n*2n−1.
1 votes
1 votes
Both 1&2

Related questions

37 votes
37 votes
9 answers
2
0 votes
0 votes
2 answers
3
sai charan chakrala asked Feb 4, 2019
891 views
What is the for the question where two statements were given as:S1: matrix A is invertibleS2:|A|=0?