0

Let $H$ has $n$ elements and $A, B, C \subseteq H$.

(a) # of ways to have this triple such that $A\cap B \cap C =\emptyset$.

(b) # of ways to have this triple such that $A \cup B \cup C=H$

For (a), I have $\sum^{n}_{k_3=0} \sum^{n}_{k_2=0} \sum^{n}_{k_1=0} {n \choose k_1} {n-k_1 \choose k_2}{n-k_1-k_2\choose k_3}$

Is this right? Is there a way to simplify this? Can this be equal to $(2^n)(2^{n-k_1})(2^{n-k_1-k_2})$

How about part (b)? It seems there are so many possible ways. Like if $A=H$, then we have $(n+1)^2$ ways. If $A$ is only missing one element from $H$, then it becomes even more complicated. I'm not sure how to solve it.

user26857
  • 52,094
user665125
  • 139
  • You are looking for the number of triples $(A,B,C)$ such that $A,B,C\subseteq H$ and $A\cap B\cap C=\emptyset$? For each element $h$ of $H$, exactly one of seven things will be true. Either $h$ is in none of $A,B,C$, $h$ is only in $A$ and not in the other two, $h$ is only in $B$ and not the other two,... $h$ is in $A$ and $B$ but not in $C$, ... We get then a total of $7^n$ such triples for $A,B,C$. Try doing something similar for (b). – JMoravitz Nov 06 '19 at 19:27
  • Note that $A\cap B\cap C=\emptyset$ does not imply that $A\cap B=\emptyset$ nor does it imply that $A\cap C$ or $B\cap C$ are empty either. For example ${1,2}\cap {2,3}\cap {1,3}=\emptyset$ – JMoravitz Nov 06 '19 at 19:28
  • By using similar method, I get $7^n$. Is this right? Thanks. – user665125 Nov 06 '19 at 22:14
  • Yes, both are 7^n – JMoravitz Nov 06 '19 at 22:25

0 Answers0