A set $M$ consists of $n$ elements. Determine the number of pairs of subsets of $M$ which have no elements in common (don't forget to account for the empty set).
If we choose a subset of one element, then there are $(n-1)+1$ corresponding different subsets of the same size, hence the total is ${n\choose1}+\frac12{{n-1}\choose 1}{n\choose1}$ when we shuffle through each subset and repeat the same operation.
Then, if we choose one with two elements, then there are $1+{{n-2}\choose1}+{{n-2}\choose2}$ corresponding different subsets of the same size and of size = 2-1, which gives us a total of ${n\choose2}+{{n-2}\choose1}{{n}\choose2}+\frac12{{n-2}\choose2}{n\choose2}$.
With three, we get for the one selection ${n\choose3}+{{n-3}\choose1}{n\choose3}+{{n-3}\choose2}{n\choose3}+\frac12{{n-3}\choose3}{n\choose3}$ for the same size, size-1 and size-2.
If I am to do this for a subset with $k$ elements, then the total is $s_k={n\choose k}+\frac12{{n-k}\choose k}{n\choose k}+\sum_{i=1}^{k-1}{{n-k}\choose i}{n\choose k}$.
The big total is when I shuffle through all possible values of $k$, so $\sum_{k=1}^{n-1}s_k$.
Is there any flaw in my reasoning? Thank you for your time!
Best Answer
Note: Like you, I take pairs to mean unordered pairs. If ordered pairs are intended, the calculation is a bit simpler, both via your approach and via mine.
The explanation could be a good bit clearer, but it appears to be right. However, it results in a very complicated expression that can be greatly simplified. It’s easier, however, to adopt a different approach from the start.
We can choose disjoint subsets of $M$ by first choosing a set $C\subseteq M$ and then partitioning $C$ into two sets. There are $\binom{n}k$ ways to choose a $C\subseteq M$ of cardinality $k$. $C$ has $2^k$ subsets, and if $k>0$, these subsets come in $2^{k-1}$ complementary pairs. Thus, $C$ can be split into two disjoint subsets in $2^{k-1}$ ways if $k>0$. If $k=0$, $C=\varnothing$, which is the union of two disjoint subsets in only one way: $\varnothing=\varnothing\cup\varnothing$. Altogether, then there are
$$\begin{align*} 1+\sum_{k=1}^n\binom{n}k2^{k-1}&=1+\frac12\sum_{k=1}^n\binom{n}k2^k\\ &=1+\frac12\left(\sum_{k=0}^n\binom{n}k2^k-\binom{n}02^0\right)\\ &\overset{*}=1+\frac12\left(3^n-1\right)\\ &=\frac12\left(3^n+1\right)\,, \end{align*}$$
where the starred step uses the binomial theorem applied to $(2+1)^n$.