How many $i$ tuples of subsets $A_1,...,A_i$ are there such that the $A_j$ are pairwise disjoint? and $A_1 \cap ....\cap A_i = \emptyset$?.

attempt: Suppose we have the case when $ i = 4$, then with a Venn diagram, we would have $4$ sets $A_1,A_2,A_3,A_4$ to insert n objects, and also in $A_1 \cup A_2 \cup A_3 \cup A_4$ since we can include the outside. So there are 5 possibles places where the $n$ objects can go, not including $A_1 \cap A_2, A_2 \cup A_3,A_3 \cup A_4$. Thus we can choose $i+1$ from ? . I am confuse about this part? Could someone please help? Also for the second part , we must show how many $i$ tuples of subsets $A_1,...,A_i$ are there such that $A_1\cap ...\cap A_i = \emptyset$. Consider if we have $n$ objects , then the $n$ will either be in $A_1$ or not, thus there are $2$ choices, similarly for $A_2$ there are 2 choices, in general, there are $2^{i} + 1$ choices since we can include the empty complement. I am not really sure. Any feedback would really help. Thanks

  • $\begingroup$ can someone please comment something? $\endgroup$ – Mahidevran Mar 2 '17 at 5:43
  • $\begingroup$ The question is a bit unclear, are $A_1, A_2,..A_i$ the subsets of some larger set and you want to pick $i$(which means all) of these so that they are all pairwise disjoint(The meaning of $A_j $ are pairwise disjoint is not clear.)? Also, is it an assumption that $A_1\cap ...\cap A_i = \emptyset$? $\endgroup$ – Akay Mar 2 '17 at 6:22
  • $\begingroup$ That is all that is given. I think the $A_j$ are subsets of a bigger set $S$ where $S$ has $n$ elements. $\endgroup$ – Mahidevran Mar 2 '17 at 6:24

Your Answer

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

Browse other questions tagged or ask your own question.