Set theory Puzzle

Printable View

December 17th 2009, 11:37 PM
Drexel28

Set theory Puzzle

Let $S=\left\{1,2,\cdots,n\right\}$ . It is quite commonly known that the number of subsets one can form from $S$ are $2^n$ , but how many pairs $A,B$ of these subsets is $A\subseteq B$ true?
January 17th 2010, 02:34 PM
Dinkydoe

Interesting,

So we're interested in finding all pairs $(A,B)\in n\times n$ such that $A\subseteq B$

Let $A\in \mathcal{P}(n)$ a set with $k$ elements. Then we have $\sum_{i=0}^{n-k}{n-k\choose i}= 2^{n-k}$ sets $B\in \mathcal{P}(n)$ such that $A\subseteq B$ . Namely these are all sets, disjunct with $A$ , we can unite $A$ with such that $A\cup B \in \mathcal{P}(n)$ .

Thus the total amount of such pairs are: $\sum_{k=0}^{n}{n\choose k}2^{n-k} = (1+2)^n = 3^n$ . With the Binomium of Newton.
January 23rd 2010, 08:00 AM
novice

Quote:

Originally Posted by Dinkydoe

Interesting,

So we're interested in finding all pairs $(A,B)\in n\times n$ such that $A\subseteq B$

Let $A\in \mathcal{P}(n)$ a set with $k$ elements. Then we have $\sum_{i=0}^{n-k}{n-k\choose i}= 2^{n-k}$ sets $B\in \mathcal{P}(n)$ such that $A\subseteq B$ . Namely these are all sets, disjunct with $A$ , we can unite $A$ with such that $A\cup B \in \mathcal{P}(n)$ .

Thus the total amount of such pairs are: $\sum_{k=0}^{n}{n\choose k}2^{n-k} = (1+2)^n = 3^n$ . With the Binomium of Newton.

How much math must I learn to understand this? Am I hopeless?
January 23rd 2010, 09:07 AM
Dinkydoe

Quote:

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

Not much really, it's pretty elementary. You've seen the induction proof of $|\mathcal{P}(n)| = 2^n$ .

However this can fairly easily shown by applying the binomium of Newton too!
Observe that $|\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n}$ .

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 $2^n = (1+1)^n$ . Applying the binomium of newton: $(x+y)^n = \sum_{k=1}^{n}{n \choose k}x^ky^{n-k}$ with $x= y = 1$ .

And this gives: $|\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n} = (1+1)^n = 2^n$ .

That idea is used here again here.
Taking an element $A\in \mathcal{P}(n)$ with $k$ elements. How many sets $B\in \mathcal{P}(n)$ exist such that $A\subseteq B$ ? Well, we have $k$ elements in $A$ . So we have $n-k$ elements left to choose from. Observe that the amount of such $B$ 's equals the amount of subsets we can create from $n-k$ elements!

Hence there exists $2^{n-k}$ of such B's in $\mathcal{P}(n)$ .

Since we have ${n \choose k}$ elements in $\mathcal{P}(n)$ of length $k$ , it follows we have ${n\choose k}2^{n-k}$ pairs $(A,B)\in \mathcal{P}(n)\times \mathcal{P}(n)$ , where $A$ is a set of length $k$ and $A\subseteq B$ .

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

Total amount of pairs $(A,B)$ = $\sum_{k=0}^{n}{n\choose k}2^{n-k}$ .

And if we analyse this number close we can recognise the binomium of Newton again with $x= 1, y = 2$ .

Hence we obtain: Total amount of pairs $(A,B) = 3^n$
January 25th 2010, 08:11 AM
novice

Quote:

Originally Posted by Dinkydoe

Not much really, it's pretty elementary. You've seen the induction proof of $|\mathcal{P}(n)| = 2^n$ .

However this can fairly easily shown by applying the binomium of Newton too!
Observe that $|\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n}$ .

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 $2^n = (1+1)^n$ . Applying the binomium of newton: $(x+y)^n = \sum_{k=1}^{n}{n \choose k}x^ky^{n-k}$ with $x= y = 1$ .

And this gives: $|\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n} = (1+1)^n = 2^n$ .

That idea is used here again here.
Taking an element $A\in \mathcal{P}(n)$ with $k$ elements. How many sets $B\in \mathcal{P}(n)$ exist such that $A\subseteq B$ ? Well, we have $k$ elements in $A$ . So we have $n-k$ elements left to choose from. Observe that the amount of such $B$ 's equals the amount of subsets we can create from $n-k$ elements!

Hence there exists $2^{n-k}$ of such B's in $\mathcal{P}(n)$ .

Since we have ${n \choose k}$ elements in $\mathcal{P}(n)$ of length $k$ , it follows we have ${n\choose k}2^{n-k}$ pairs $(A,B)\in \mathcal{P}(n)\times \mathcal{P}(n)$ , where $A$ is a set of length $k$ and $A\subseteq B$ .

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

Total amount of pairs $(A,B)$ = $\sum_{k=0}^{n}{n\choose k}2^{n-k}$ .

And if we analyse this number close we can recognise the binomium of Newton again with $x= 1, y = 2$ .

Hence we obtain: Total amount of pairs $(A,B) = 3^n$

Oh, thank you. You are a very good teacher.