I believe that this is a pretty simple question in terms of combinatorics.
Assuming we have the following set $\{ {1,2,3…n} \}$
In how many ways can we choose 3 subsets (A,B,C) such that the intersection between all them is empty?
$ A \cap B \cap C = \emptyset $
Well, what I have so far is the following:
For A we have $ 2^n $ options (where n is the size of the set)
Then, for B, the remaining options are exactly $ 2^{n-|A|} $ since we can choose only from subsets who does not have elements in common with A.
And finaly, for C, since we already have an empty intersection, we can choose whatever subset we want and get the expected result $ \emptyset $.
But for some reason it feels like the numbers are too big.
If we take for example the set {1,2}, then, according to my "formula", the number of options should be:
$ \binom{4}{1} * \binom{2}{1} * \binom{2}{1} = \frac{4!}{3!} * \frac{2!}{1!} * \frac{2!}{1!} = 16 $
Does it make sense?
Best Answer
Think of it this way: for each $i\in\{1,\cdots,n\}$, $i$ can be in at most two sets. Therefore, $i$ could be in none of the sets, $i$ could be in exactly one of $A$, $B$, or $C$, or $i$ could be in exactly two of $A$, $B$, and $C$. This gives $7$ possible situations for each $i$. Since the sets for each $i$ can be chosen independently, this gives $7^n$ ways to define $A$, $B$, and $C$.
This works for $n=1$. In this case, there are:
$A=B=C=\emptyset$.
($A=\{1\}$ and $B=C=\emptyset$) or ($B=\{1\}$ and $A=C=\emptyset$) or ($C=\{1\}$ and $A=B=\emptyset$)
($A=B=\{1\}$ and $C=\emptyset$) or ($A=C=\{1\}$ and $B=\emptyset$) or ($B=C=\{1\}$ and $A=\emptyset$)