combinatorics: number of options to set a (a,b) ordered pair under terms

Question

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.

Answer 1

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*}

Answer 2

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

Answer 3

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.