22. Find the number of pairs $(A, B)$ of distinct subsets of $1,2,3,4,5,6$ such that $A$ is a proper subset of $B$. Note that $A$ can be an empty set.
22. Answer: 665
Since $B$ cannot be empty, the number of elements in $B$ is between 1 to 6 . After picking $B$ with $k$ elements, there are $2^{k}-1$ possible subsets of $B$ which qualifies for $A$, as $A$ and $B$ must be distinct. Thus the total number of possibilities is
$$
\begin{aligned}
\sum_{k=1}^{6}\binom{6}{k}\left(2^{k}-1\right) & =\sum_{k=0}^{6}\binom{6}{k}\left(2^{k}-1\right) \\
& =\sum_{k=0}^{6}\binom{6}{k} 2^{k}-\sum_{k=0}^{6}\binom{6}{k} \\
& =(2+1)^{6}-(1+1)^{6} \\
& =3^{6}-2^{6} \\
& =665 .
\end{aligned}
$$