Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?


share|cite|improve this question
The number of options for $b$ is $2^n,$ the number of subsets of $\{1,\ldots,n\}.$ – Giuseppe May 26 '12 at 13:29
ordered-fields? – Phira May 26 '12 at 14:26
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|cite|improve this answer

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

share|cite|improve this answer

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|cite|improve this answer

Your Answer


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.