0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ If you factor in that $k$ can be $0$, then $\sum_{k=0}^n{n\choose k}2^{n-k}$ is the right answer, since it’s equal to $3^n$ due to the binomial theorem. $\endgroup$
    – Aig
    Commented Mar 9 at 11:14
  • $\begingroup$ Once you have chosen U a subset of C (2^k possibilities), there is only one way to choose the complementary V of U in C to form a partition of C. So in total $\sum_{k=1}^{n}\left(\matrix{n\\k}\right)2^k=\sum_{k=0}^{n}\left(\matrix{n\\k}\right)2^k-1=3^n-1$ $\endgroup$
    – Jean-Claude Colette
    Commented Mar 9 at 12:04
  • $\begingroup$ I missed $U\ne V$, the answer is $3^n-1$ indeed. $\endgroup$
    – Aig
    Commented Mar 9 at 12:26
  • 1
    $\begingroup$ Another way to see $3^n-1$ is to note that each element $i\in M$ appears in $U$, $V$, or neither ($3^n$ choices), but we must exclude $U=V=\emptyset$. $\endgroup$
    – RobPratt
    Commented Mar 9 at 14:54

0

Reset to default

You must log in to answer this question.