1.4k views

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 | 1.4k views

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.
by Loyal (5.9k points)
0
How can x be phi ?

Phi is the subset of every set not the element of every set.
0
Question was n*2^(n-1) not n*(2n-1)

So for x= 3 it comes 12 only.

Both are equivalent
0
0
See thr given question , i couldn't see power there. Sorry , yes with power both must be the answer
0
In actual question option (i) was n*(2^(n-1))

Which is same as option (ii)
0
its $n{2^{n-1}}$
0
This was asked for how many marks?
0
correct.

And I solved full question correctly and ruined it while calculating nCk . and I marked only one as answer.
0
2marks..so i loose -2.66 here
0

@Abbas2131 $\phi$ can be taken as an element , but won't make any difference since $\phi \in \phi$ is false.

If instead of X=$\phi$ X=$\{\phi\}$ was there , it would've made a difference.

0

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

0
Yes, it was 1 mark
0
Hoping that u r right and i am wrong ## Not considering x=ϕ and X=ϕ since ϕ∈ϕ is not true. by (69 points)
0
thank u for such detailed solution.
0
In ur first image how will u deal with |x| = 3. Justify how nC3. 3
+1 vote
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.
by Active (1.2k points)
Both 1&2
by (21 points)
0
Can you prove both of them are equivalent?

Did you try for n=4
0

Is this right?? 0

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

0
ok, got it .