HMMT-Nov 2010 guts, Problem 6

How many ordered pairs $(S, T)$ of subsets of $\{1,2,3,4,5,6,7,8,9,10\}$ are there whose union contains exactly three elements?

Solution: et the three elements in the union be $a, b$, and $c$. We know that $a$ can be only in $S$, only in $T$, or both, so there are 3 possibilities for placing it. (Recall that $S=\{a\}, T=\{b, c\}$ is different from $S=\{b, c\}, T=\{a\}$ because $S$ and $T$ are an ordered pair.) Likewise for $b$ and $c$. The other 7 elements are in neither $S$ nor $T$, so there is only 1 possibility for placing them. This gives $3^{3}=27$ ways to pick $S$ and $T$ once you've picked the union. There are $\left(\begin{array}{c}10 \\ 3\end{array}\right)=120$ ways to pick the elements in the union, so we have $120 \times 27=3240$ ways total. $\fbox{3240}$.

Answer: 3240