Combinatorics Ordered Pair of embeded Subsets Let X be the set {1,2, .... n}. Count the number of ordered pairs (A, B) where A and B are subsets of X and A is a subset of B.
I'm just starting to learn how combinatorics works and I have no clue how this basic problem works. Could anyone give me an example process for finding the answer?
I know their exists 2^n subsets of an N size set, but I don't know where to go from there.
 A: Consider a function $f:X\to\{1,2,3\}$ and define $A=\{x\in X\mid f(x)=1\}$ and $B=\left\{x\in X\mid f(x)\in\{1,2\}\right\}$. Show this correspondence is $1-1$ and onto pairs $(A,B)$.
A: First, consider an easier problem: count the number of sets $A$ such that $A\subseteq X$.
Solution: For each $x\in X$, there are two choices: either $x\in A$, or else $x\notin A$; so the answer is $2^n$.
Now for your problem: count the number of pairs $(A,B)$ such that $A\subseteq B\subseteq X$.
Solution: For each $x\in X$, there are now three choices: $x$ belongs to both of the sets $A,B$, or $x$ belongs to neither of them, or $x$ belongs to just one of them (which must then be $B$ since $A\subseteq B$); so the answer is . . .
A: Suppose you have a choice for $A$ and $B$. Then define a function $f:X \rightarrow \{0,1,2\}$ by $f(x)=2$ if $x \in A$, $f(x)=1$ if $x \in B$ and $x \notin A$ and $f(x)=0$ otherwise. On the other hand if such a function is given then define $B=\{x: f(x)\geq 1\}$ and $A=\{x: f(x)=2\}$. Now, counting the number of these functions is easy and gives a short answer, the reasonment is the same as for determining the number of subsets $2^{|X|}$ of a set $X$.                                                                               
