5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It looks to low. Since if $A= \{1, \dots , n \}$, then $B = \emptyset$ and $C=$whatever, however, $A= B = \{ 1, \dots, n \}$ and $C = \emptyset$ is also an option, but not in your formula. As in your example of $\{1,2\}$, then $A = \emptyset$ makes $B$ and $C$ arbitrary, so we get at least $4 \times 4 =16$ options. $\endgroup$ – Hetebrij Mar 19 '16 at 10:03
  • 2
    $\begingroup$ It could be possible that $A,B,C$ are not pairwise disjoint. For example, if $A=\{1,2\}, B=\{ 2,3\}, C=\{ 1,3\}$, then these three have empty intersection. $\endgroup$ – Crostul Mar 19 '16 at 10:06
  • $\begingroup$ The problem is that when you say the remaining options for $B$ are $2^{n-|A|}$ because this implies that $A$ and $B$ are disjoint. It is possible that $A$ and $B$ are not disjoint but $C$ is disjoint from both of them. $\endgroup$ – Michael Burr Mar 19 '16 at 10:08
  • $\begingroup$ Here is an idea. Choose ANY $A,B$. Then, choose any $C \subset \{ 1, \dots , n\} \setminus (A \cap B)$. $\endgroup$ – Crostul Mar 19 '16 at 10:10
  • $\begingroup$ Thanks @Crostul. How can I assure that this covers all options? I'm pretty new to the subject so I would like to learn as much tools as possible... $\endgroup$ – Ngk Mar 19 '16 at 10:13
10
$\begingroup$

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$)

$\endgroup$
  • $\begingroup$ Is there no possibility that some of the options are counted more than once? $\endgroup$ – Ngk Mar 19 '16 at 10:34
  • $\begingroup$ No, if you change the choice for $i$, then you change the sets that $i$ is in (or not in) so you change one of $A$, $B$, or $C$. A different problem where you could permute the $A$, $B$, and $C$ seems much harder. $\endgroup$ – Michael Burr Mar 19 '16 at 10:38
0
$\begingroup$

For every $x\in\{ {1,2,3...n} \}$ there are 4 options:$$x\in A\ strong \ or\ x\in b\ strong \ or\ x\in C strong \ or\ x\notin A\bigcup B \bigcup C$$ and every option like that gives you $A,B,C$ as you want. So the number of options is $4^n$.

$\endgroup$
  • 1
    $\begingroup$ There should be $7^n$ possibilities, not $4^n$. This looks like you're assuming that the sets must be pairwise disjoint. $\endgroup$ – Michael Burr Mar 19 '16 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.