# how many ways to choose 2 disjoint subsets of a given set

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?

• Why did you delete the previous question? Will you do it again now? – Aqua Mar 19 at 16:57
• @MariaMazur because I found a different question quite the same as mine so I avoided duplicating posts – sadElephent Mar 19 at 17:00
• Can you show it – Aqua Mar 19 at 17:01
• Why did you mention set $C$? What relevance does it have to your question? – N. F. Taussig Mar 19 at 17:01
• @N.F.Taussig there is more to the question where C comes into play – sadElephent Mar 19 at 17:06

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$$.
• so i is either in A , B or neither of A and B , 3 totally, so $3^n$? – sadElephent Mar 19 at 17:11
• Do you consider $A = \{1\}$, $B = \{2\}$ different from $A = \{2\}$, $B = \{1\}$? If not, then you should divide by $2$. – Austin Mohr Mar 19 at 17:14
• A clarification: If $A$ and $B$ were considered to be indistinguishable, the answer would be $\frac{3^n + 1}{2}$ since each choice would be counted twice except the one in which $A = B = \emptyset$. – N. F. Taussig Mar 19 at 17:30