Set of pairs in combinatorics Let $X_n$ be a set of pairs $(A,B)$ such that $A \subseteq B \subseteq \{\ 1 \dots n \}\ $
Determine $|X_n|$.
How I understand the problem:
$X_n$ is a set of pairs like $(a,b)$ but I'm lost at the part where it says $A \subseteq B$. Is $A$ a set? I thought $A$ was an element of a pair?
Can someone shed some light on this?
 A: You are asked to find pair of subsets of $\{1, \ldots n\}$ say $(A,B)$, such that $A \subseteq B$. 
For example for $n = 2$ some possible pairs are $A = \{1\}$, $B = \{1,2\}$ or $A = \{2\}$, $B = \{2\}$ (Notice they can be the same).
Hint Fix $B$, let say it has $k$ elements, how many other $A$ will satisfy $A \subseteq B$? With that you should be able to count the pairs where $B$ has fixed size, and from that you should be able to count all possible pairs.
A: Hint: Without the need to fix a set size, you can do the following. Instead of looking at things from the sets' perspective, try looking at the problem from the numbers' perspective. For each number $i$ in $\{1,2,\cdots,n\}$, how many possibilities are there? In how many different "positions" can $i$ be? 

 For example, it can be in $A$, but then it will have to be in $B$. Alternatively, it can be in $B$, but not $A$, i.e. in $B \backslash A$. Any other alternatives?

Then, the rest is pure combinatorics. What do you get as the result?
Edit (more spoilers):

For each number $i \in \{1,2,\cdots,n\}$ , there are 3 "boxes" in which it can go: into $A$, $B \backslash A$, or into none of them, say $S := \{1,2,\cdots,n\} \backslash B$. Thus, there are $3^n$ total choices to select the pair $(A, B)$.

Another way to think of this problem is writing a "word" of length $n$ using the letters $\{a, b, s\}$. The $i^{th}$ letter corresponds to which "box" the number $i$ goes into. (Having letter "a" means being in $A$ (thus readily in $B$), having letter "b" means being in $B$ but not $A$, and having letter $S$ means being in neither.) This forms a one-to-one correspondence with the pairs $\{A, B\}$. For example, the word "$ABASSB$" corresponds to the case that $A = \{1, 3\}, B =\{1, 2, 3, 6\}$. Clearly, there are $3^n$ such words.
