A,B $\subset$ {1,2,…,n} .
how many ways are there to choose A and B : A $\cap$ B = $\phi$
I tried to tackle this using say there are $2^n$ – $ 2^{n-1} $ subsets containing 1 for example and $2^{n-1}$ subsets that don't so I could multiply them however I think I'm not covering all cases here..
any ideas?
Best Answer
Hint: Notice that if subsets $A$ and $B$ are disjoint and $i \in \{1, 2, 3, \ldots, n\}$, then exactly one of the following is true: $i \in A$, $i \in B$, $i \in (A \cup B)^C$.