in Set Theory & Algebra edited by
12,445 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

in Set Theory & Algebra edited by
12.4k views

1 comment

0
0

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.

4 Comments

@Shashank Mishra 

I think this was of 1 mark only..though the question was good and seems like 2 marks :P

0
0
Yes, it was 1 mark
0
0
Hoping that u r right and i am wrong
0
0
11 votes
11 votes

Not considering x=ϕ and X=ϕ since ϕ∈ϕ is not true.

 

2 Comments

thank u for such detailed solution.
0
0
In ur first image how will u deal with |x| = 3. Justify how nC3. 3
0
0
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 vote
1 vote
Both 1&2

4 Comments

Can you prove both of them are equivalent?

Did you try for n=4
0
0

Is this right??

0
0

@Mehul11jain don't write answers like that . Answer with clear explanation , otherwise moderators would flag it or strike it down. :)

0
0
ok, got it .
0
0
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