Let . It is quite commonly known that the number of subsets one can form from are , but how many pairs of these subsets is true?

Printable View

- December 17th 2009, 11:37 PMDrexel28Set theory Puzzle
Let . It is quite commonly known that the number of subsets one can form from are , but how many pairs of these subsets is true?

- January 17th 2010, 02:34 PMDinkydoe
Interesting,

So we're interested in finding all pairs such that

Let a set with elements. Then we have sets such that . Namely these are all sets, disjunct with , we can unite with such that .

Thus the total amount of such pairs are: . With the Binomium of Newton. - January 23rd 2010, 08:00 AMnovice
- January 23rd 2010, 09:07 AMDinkydoeQuote:

How much math must I learn to understand this? Am I hopeless?

However this can fairly easily shown by applying the binomium of Newton too!

Observe that .

Namely: it's how many different ways we can choose 0 elements, + how many different ways we can choose 1 element...etc.

However note that . Applying the binomium of newton: with .

And this gives: .

That idea is used here again here.

Taking an element with elements. How many sets exist such that ? Well, we have elements in . So we have elements left to choose from. Observe that the amount of such 's equals the amount of subsets we can create from elements!

Hence there exists of such B's in .

Since we have elements in of length , it follows we have pairs , where is a set of length and .

Now we only need to sum over all different lengths a set can have. Thus we obtain:

**Total amount of pairs**= .

And if we analyse this number close we can recognise the binomium of Newton again with .

Hence we obtain:**Total amount of pairs** - January 25th 2010, 08:11 AMnovice