The Gateway to Computer Science Excellence
+5 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 by (301 points)
edited by | 1.4k views

4 Answers

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

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

So for x= 3 it comes 12 only.

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

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

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

@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.


@Shashank Mishra 

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

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

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


by (69 points)
thank u for such detailed solution.
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)
0 votes
Both 1&2
by (21 points)
Can you prove both of them are equivalent?

Did you try for n=4

Is this right??


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

ok, got it .

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
50,737 questions
57,385 answers
105,388 users