Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have to find the number of options for setting pair $(a,b)$ under the terms: $a ⊆ b ⊆\{1, 2,\ldots, n\}$ Means, they are both subsets of $\{1, 2,\ldots, n\}$ and $a⊆ b$.

I was thinking to handle the $b$ coordinate first and by that, to handle the $a$ coordinate. But, what are the number of options for $b$?

tahnx.

share|improve this question
1  
The number of options for $b$ is $2^n,$ the number of subsets of $\{1,\ldots,n\}.$ –  Giuseppe Tortorella May 26 '12 at 13:29
    
ordered-fields? –  Phira May 26 '12 at 14:26
add comment

3 Answers 3

up vote 3 down vote accepted

Well, considering each element $1 \le m \le n$, we have ($m \not\in B$) or ($m \in B$ but $m \not\in A$) or ($m \in A$), hence there're three choice for each element.

So the answer is $3^n$.

Your thought is also available. It's algebraic: Let $U = \{1, 2, \ldots, n\}$, \begin{align*} \sum_{B \subseteq U} \sum_{A \subseteq B} 1 &= \sum_{B \subseteq U} 2^{|B|} \\ &= \sum_{k} \sum_{\scriptstyle B \subseteq U \atop \scriptstyle |B| = k} 2^k \\ &= \sum_{k} \binom n k 2^k \\ &= (2+1)^n \\ &= 3^n \end{align*}

share|improve this answer
add comment

The number of options for your pairs $(a,b)$ should be $\Sigma_{k=0}^n 2^k\binom{n}{k}$

share|improve this answer
add comment

Each element is either in a and b, in b but not in a, or non of both. edit: did'nt see the first part of Frank's answer. It's perfect.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.