0
$\begingroup$

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?

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

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

$\endgroup$
5
  • 2
    $\begingroup$ so i is either in A , B or neither of A and B , 3 totally, so $3^n$? $\endgroup$
    – se718
    Mar 19 '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$ Mar 19 '19 at 17:14
  • 1
    $\begingroup$ @AustinMohr A and B are considered different so the answer is yes $\endgroup$
    – se718
    Mar 19 '19 at 17:20
  • $\begingroup$ @lidor718 In that case, you are correct. $\endgroup$ Mar 19 '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$ Mar 19 '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.