How can I show that the set { } contains elements, where S is a set of n elements and P(S) is the power set of S.

[SOLVED]

Printable View

- April 29th 2010, 12:26 PMposix_memalignCardinality of a set
How can I show that the set { } contains elements, where S is a set of n elements and P(S) is the power set of S.

[SOLVED] - April 29th 2010, 01:30 PMPlato
Here is some notation. is the number of elements is set .

Thus and .

For each set that are subsets of that are super-sets of

i.e.

Hence that is the number of wanted pairs .

To count them find the sum . Do you see why?

Now use the binomial expansion theorem on - April 29th 2010, 03:44 PMposix_memalign
- April 29th 2010, 04:03 PMPlato