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?

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

  • 2
    $\begingroup$ so i is either in A , B or neither of A and B , 3 totally, so $3^n$? $\endgroup$ – sadElephent Mar 19 at 17:11
  • 1
    $\begingroup$ Do you consider $A = \{1\}$, $B = \{2\}$ different from $A = \{2\}$, $B = \{1\}$? If not, then you should divide by $2$. $\endgroup$ – Austin Mohr Mar 19 at 17:14
  • 1
    $\begingroup$ @AustinMohr A and B are considered different so the answer is yes $\endgroup$ – sadElephent Mar 19 at 17:20
  • $\begingroup$ @lidor718 In that case, you are correct. $\endgroup$ – N. F. Taussig Mar 19 at 17:21
  • $\begingroup$ 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$. $\endgroup$ – N. F. Taussig Mar 19 at 17:30

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.