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

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.

-

1
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

## 3 Answers

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

-

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

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8476875424385071, "perplexity_flag": "middle"}