Number of non-disjoint, unlabeled subset pairs of [n] Given that $[n]$={1, 2,..., n}, I want to find how many ways I can select two unlabeled subsets from $[n]$ such that they are non-disjoint.
My thinking is that there are $4^n$ ways to select two subset pairs of $[n]$ with no restrictions - each element has the choice to be in neither, both, one, or the other of the two sets. Then, there are $3^n$ ways to select two disjoint subset pairs of $[n]$ - each element has the choice to be in neither, one, or the other of the two sets. Thus, there are $\frac{1}{2}(4^n-3^n)$ ways to select two non-disjoint, unlabeled subset pairs of $[n]$.
On the other hand, I got to thinking that there are $2^n$ ways to select two subset pairs from $[n]$ - each element has the choice to be in neither or both of A and B. Thus, there are $4^n-3^n-2^n$ to select two unequal, labelled subset pairs of $[n]$, and $\frac{1}{2}(4^n-3^n-2^n)$ ways to select two unequal, unlabeled subset pairs of $[n]$. Now, if we wish to instead count the cases where equal subset pairs are allowed then we get $\frac{1}{2}(4^n-3^n-2^n)+2^n=\frac{1}{2}(4^n-3^n+2^n)$ as the number of ways to select two non-disjoint subset pairs of $[n]$.
My question, then, is which is the correct count?
 A: It's always worth looking at an example to see where the error is.
When $n=2$, there are $4^2 = 16$ pairs $(A,B)$ where $A,B \subseteq \{1,2\}$:
\begin{array}{cccc}
    (\emptyset,\emptyset) & (\emptyset, \{1\}) & (\emptyset, \{2\}) & (\emptyset, \{1,2\}) \\
    (\{1\},\emptyset) & (\{1\}, \{1\}) & (\{1\}, \{2\}) & (\{1\}, \{1,2\}) \\
    (\{2\},\emptyset) & (\{2\}, \{1\}) & (\{2\}, \{2\}) & (\{2\}, \{1,2\}) \\
    (\{1,2\},\emptyset) & (\{1,2\}, \{1\}) & (\{1,2\}, \{2\}) & (\{1,2\}, \{1,2\}) \\
\end{array}
There are indeed $3^2 = 9$ pairs $(A,B)$ where $A$ and $B$ are disjoint, and we can remove them to get $4^2 - 3^2$ pairs:
\begin{array}{cccc}
    - & - & - & - \\
    - & (\{1\}, \{1\}) & - & (\{1\}, \{1,2\}) \\
    - & - & (\{2\}, \{2\}) & (\{2\}, \{1,2\}) \\
    - & (\{1,2\}, \{1\}) & (\{1,2\}, \{2\}) & (\{1,2\}, \{1,2\}) \\
\end{array}
Looking at this table, we see that we cannot simply divide the number of remaining sets by $2$ to account for symmetry. There are some pairs with $A \ne B$, and we can divide their number by $2$; however, the pairs with $A=B$ should be left alone. This tells us that $\frac12(4^n - 3^n)$ will not work.
The general logic in the answer $\frac12(4^n - 3^n + 2^n)$ is reasonable - however, looking at this second table, we also can count and see that there are not $2^2 = 4$ pairs $(A,B)$ where $A=B$. There are only $3$.
Why are there $3$ and not $4$? In general, how many pairs should there be instead of $2^n$? Answer that, and you will know the general formula.
