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.