Let $S = \{ 1,2 , \ldots , n \}$. Find the number of unordered pairs $\{ A , B \}$ of subsets of $S$ such that $A$ and $B$ are disjoint, where $A$ or $B$ or both may be empty.
The number is $\frac { 3 ^ { n } + 1 } { 2 }$. An ordered pair $(A, B)$ of disjoint subsets of $S$ is determined by 3 choices for every element of $S$ (either it is in $A$, or in $B$ or in neither of them). Hence such pairs are $3 ^ { n }$ in number. An unordered pair will be counted twice in this way, except for the case $A$ and $B$ both empty. Hence the number is $1 + \frac { 3 ^ { n } - 1 } { 2 }$.
Let $S = \{ 1,2 , \ldots , n \}$. Find the number of unordered pairs $\{ A , B \}$ of subsets of $S$ such that $A$ and $B$ are disjoint, where $A$ or $B$ or both may be empty.