Counting the number of set-subset pairs within H

[Mr Davis 97]

Homework Statement

$H=\{1,2,3,\dots , 10\}$. Determine the following number: $\#([G,F];G\subseteq F \subseteq H)$.

Homework Equations

The Attempt at a Solution

Here is my reasoning. If $G=\emptyset$, there are $2^{10}$ ways to choose $F$, so $\binom{10}{0}2^{10}$ total. If $|G|=1$, there are $2^9$ ways to choose $F$, so $\binom{10}{1}2^9$ ways total. And so on, until $|G|=10$, so there is only one way to choose $F$, and so $\binom{10}{10}\cdot 1$ ways in total.

These are are disjoint cases, so we sum them up: $$\sum_{k=0}^{10}\binom{10}{10-k}2^{k} = \sum_{k=0}^{10}\binom{10}{k}2^{k} = 3^{10}$$.

Does this all look like the correct reasoning?

 

[BvU]

Not clear to me if the ordering is relevant. If not, your 2¹⁰ shrinks to 2⁰...

 

[Mr Davis 97]

Not clear to me if the ordering is relevant. If not, your 2¹⁰ shrinks to 2⁰...

Could you elaborate? In my solution $2^{10}$ is how many subsets of $H$ there are. Order is not relevant because we're just forming subsets, I believe.

 

[BvU]

My bad, it looks like the total number is staggering indeed...

 

[Dick]

Does this all look like the correct reasoning?

You can also count your $3^{10}$ directly. The sets $G\subseteq F \subseteq H$ can be identified by assigning a status to each element of $H$. It can be either i) only in $H$, ii) in $F$ and $H$ but not in $G$ or ii) in all three sets. That's three possibilities for each element of $H$. Hence $3^{10}$ ways.