For my discrete maths course i did the following exercise:

Let M be a finite set with n elements, find

$| \\{(U,V)|U,V\subseteq M , U \not = V,U\cap V= \emptyset \\}|$

I did it the following way: choose a set $C\subseteq M$ and then partion $C$ into two sets. There are ${n}\choose{k}$ ways to choose $C$ with cardinality $k$. $C$ has $2^k$ subsets and if $k>0$ then these subsets come in $2^{k-1}$ complementary pairs. So $C$ can be split int two disjoint subsets in $2^{k-1}$ ways. And altogether there are then $$ \sum_{k=1}^{n} {{n}\choose{k}}2^{k-1} $$ However, i do not understand my approach anymore. Why are there $2^{k-1}$ complementary pairs. And also wouldn't it be possible to combine $C$ with any subset of $M\backslash C$ such that we would reach $$ \sum_{k=1}^{n} {{n}\choose{k}}2^{n-k} $$ any help in trying to understand my thoughts from one year ago would be greatly appreciated

For my discrete maths course i did the following exercise:

Let M be a finite set with n elements, find

$|\{(U,V)|U,V\subseteq M , U \not = V,U\cap V= \emptyset \}|$

I did it the following way: choose a set $C\subseteq M$ and then partion $C$ into two sets. There are ${n}\choose{k}$ ways to choose $C$ with cardinality $k$. $C$ has $2^k$ subsets and if $k>0$ then these subsets come in $2^{k-1}$ complementary pairs. So $C$ can be split int two disjoint subsets in $2^{k-1}$ ways. And altogether there are then $$ \sum_{k=1}^{n} {{n}\choose{k}}2^{k-1} $$ However, i do not understand my approach anymore. Why are there $2^{k-1}$ complementary pairs. And also wouldn't it be possible to combine $C$ with any subset of $M\backslash C$ such that we would reach $$ \sum_{k=1}^{n} {{n}\choose{k}}2^{n-k} $$ any help in trying to understand my thoughts from one year ago would be greatly appreciated