recategorized by
450 views

1 Answer

Best answer
2 votes
2 votes
Power set of a set contains 2^n elements.

Say S = {1,2,3}

p(S) = {phi, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3})

phi will have a null set intersection with every other element and itself, ie for phi : 2^n such intersections.

Next we pick 'one' element (say {1}). It will intersect with phi, {2}, {3}, {2,3}, i.e. it can be stated as :

1+ n-1C1 + n-1C2 +....+n-1Cn-1 , i.e. we keep on picking elements from set other than the element we are dealing with .
This gives us 2^(n-1). Now there are nC1 such possibilities(i.e. for every 'one' element). Hence total : 2^(n-1)*nC1

Similarly if we pick two elements using same logic and calculation we get : 2^(n-2)*nC2

And it goes on till n elements, i.e. {1,2,3} for 3 elements which has only one intersection with phi : 2^(n-n)*nCn = 1

So summing up it is : 2^n + 2^(n-1)*nC1 + 2^(n-2)*nC2 +......+2^(n-n)*nCn

In ordered pairs (a,b) is different from (b,a), hence we have to take both except (phi,phi),i.e. when a=b.
selected by

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
1 answer
2
dan31 asked Nov 8, 2018
507 views
If A = {1,2,3...n}, then number of equivalence relations possible on A , which are also surjection on A is ________________?How to approach this type of problems?