Let $S$ be a set containing $n$ elements. How many ways are there to choose two subsets of $S$ (not necessarily distinct) whose union is equal to the set $S$?

Counting paths and figures
Let $A$ and $B$ be the two sets. Each element must be either only in $A$, only in $B$, or in both $A$ and $B$. Thus, there are 3 possibilities for each element, which gives a total of $3^{n}$ possibilities. However, since the order of the sets does not matter, each choice of two sets is counted twice, except for the one that corresponds to $A=B=S$. Therefore, the number of ways to choose two subsets whose union is $S$ is equal to $\frac{3^{n}+1}{2}$.