How can I show that the set {$\displaystyle (A, B) \in P(S) \times P(S) | A \subseteq B$} contains $\displaystyle 3^n$ elements, where S is a set of n elements and P(S) is the power set of S.

[SOLVED]

Printable View

- Apr 29th 2010, 12:26 PMposix_memalignCardinality of a set
How can I show that the set {$\displaystyle (A, B) \in P(S) \times P(S) | A \subseteq B$} contains $\displaystyle 3^n$ elements, where S is a set of n elements and P(S) is the power set of S.

[SOLVED] - Apr 29th 2010, 01:30 PMPlato
Here is some notation. $\displaystyle |A|$ is the number of elements is set $\displaystyle A$.

Thus $\displaystyle |S|=n$ and $\displaystyle |\mathcal{P}(S)|=2^n$.

For each set $\displaystyle A$ that are $\displaystyle 2^{n-|A|}$ subsets of $\displaystyle S$ that are super-sets of $\displaystyle A$

i.e. $\displaystyle |\{X\in \mathcal{P}(S):A\subseteq X\}|=2^{n-|A|}$

Hence that is the number of wanted pairs $\displaystyle (A,B)$.

To count them find the sum $\displaystyle \sum\limits_{k = 0}^n {\binom{n}{k} \cdot 2^{n - k} } $. Do you see why?

Now use the binomial expansion theorem on $\displaystyle 3^n=(1+2)^n$ - Apr 29th 2010, 03:44 PMposix_memalign
- Apr 29th 2010, 04:03 PMPlato