# Counting the number of set-subset pairs within H

#### Mr Davis 97

1. The problem statement, all variables and given/known data
$H=\{1,2,3,\dots , 10\}$. Determine the following number: $\#([G,F];G\subseteq F \subseteq H)$.

2. Relevant equations

3. 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?

Related Calculus and Beyond Homework News on Phys.org

#### BvU

Science Advisor
Homework Helper
Not clear to me if the ordering is relevant. If not, your 210 shrinks to 20... #### Mr Davis 97

Not clear to me if the ordering is relevant. If not, your 210 shrinks to 20... 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

Science Advisor
Homework Helper
My bad, it looks like the total number is staggering indeed...

#### Dick

Science Advisor
Homework Helper
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.

### Want to reply to this thread?

"Counting the number of set-subset pairs within H"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving