• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Counting the number of set-subset pairs within H

1,456
44
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?
 

BvU

Science Advisor
Homework Helper
11,828
2,579
Not clear to me if the ordering is relevant. If not, your 210 shrinks to 20...:rolleyes:
 
1,456
44
Not clear to me if the ordering is relevant. If not, your 210 shrinks to 20...:rolleyes:
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
11,828
2,579
My bad, it looks like the total number is staggering indeed...
 

Dick

Science Advisor
Homework Helper
26,252
615
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" You must log in or register to reply here.

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
Top