Cardinality of the set $\{(A, B) \mid A ⊆ B ⊆ S\}$ If $S$ is a set with $n$ elements, what is the cardinality of the set
$\left\{(A, B) \mid A ⊆ B ⊆ S\right\}$
 A: CORRECTED HINT: Every such pair $\langle A,B\rangle$ divides $S$ into three pairwise disjoint sets: $A$, $B\setminus A$, and $S\setminus B$. Each of the $n$ elements of $S$ can go into any one of the three classes. That’s a $3$-way choice made $n$ times in a row. This can be done in how many ways?
A: If you draw the venn diagram of the sets the solution will peek at you.
At first draw a circle or a rectangle or even a square signifying the set S.
Inside that figure draw a circle signifying the set B as B is a subset of S so it will be wholly inside the figure signifying S. Now Draw another circle signifying the set A and this will again be wholly inside B.
Now pick one element after the other from S.For each picked element you can put it in the one of the 3 regions inside the figure signifying S(If you put it inside S but outside B it means you dont select the element,if you place it inside B but outside A it means you select that element as an element of B only,and lastly if you place it inside A it means that you have selected the element as an element of A which also implies that it has been selected for B as well).
So you have 3 choces for each element. Now you have n elements so the total no. of choices will be: $3\dots3$ n times =$3^n$
A: Choose $A$ first, then $B$.
For $A$ of cardinality $k$, you have $\binom{n}{k}$ choices. 
Then $B$ is $A\cup C$ with $C$ a set of $l$ elements chosen among $n-k$, with $0\leq l\leq n-k$.
So the answer is:
$$
\sum_{k=0}^{n}\binom{n}{k}\sum_{l=0}^{n-k}\binom{n-k}{l}=\sum_{k=0}^{n}\binom{n}{k}2^{n-k}=3^n
$$
which follows from a double application of the binomial theorem.
A: we have:
$$|\{(A,B)\in \mathcal P(S)^2 \mid A \subseteq B \}|=|\bigcup_{B\in \mathcal P( S)}\bigcup_{A\in \mathcal P(B)}\{(A,B)\}|=\sum_{B\in \mathcal P( S)}|\mathcal P(B)|=\sum_{B\in \mathcal P( S)}2^{|B|}=\sum_{k=1}^{n}2^k|\{B\in \mathcal P(S) \mid |B|=k \}|=\sum_{k=1}^{n}2^k\binom{n}{k}=\sum_{k=1}^{n}\binom{n}{k}2^k$$
which can be simplified by binomial theorem (as in julien's answer).
