How many pairs $(A_1, A_2)$ of subsets of $\{1,2,\ldots,n\}$ are there such that $A_1 \cap A_2 = \emptyset$?

I am to give a solution involving binomial coefficients.

The hint I was given is to choose $A_1$ and then choose $A_2$ as a subset of its complement. Then determine the sum of products of binomial coefficients.

I do not know where to begin, so any guidance is appreciated.

  • $\begingroup$ If you want the solution specifically in terms of binomials, I'd say $\sum_{k=0}^n 2^k\binom nk$, though I'd rather call it $3^n$. $\endgroup$ – Gae. S. Aug 2 '19 at 19:24
  • $\begingroup$ Well, not sure that hint is optimal but for another approach: any such such selection is the same as a map to $\{1,2,3\}$ where an element maps to $1$ if it is in $A_1$, $2$ if it is in $A_2$, and $3$ if it is in neither. $\endgroup$ – lulu Aug 2 '19 at 19:25

Take any $k \in \{ 0,...,n \}$ and say that set $A_1$ will have $k$ elements chosen from $\{1,...,n\}$. Then there are $n-k$ elements left, and set $A_2$ can be any subset of set of those remaining elements. That is, for a fixed $k$, we have ${n \choose k}$ ways of choosing $A_1$, then for every $A_1$ (cause this is only matter of $|A_1|$) we have $2^{n-k}$ ways to choose $A_2$. Now we have to sum over all values $k$, which gives us: $\sum_{k=0}^n {n \choose k} 2^{n-k}$.

However, we can count it in different way. Note, that since we want $A_1 \cap A_2 = \emptyset$, that means we can form a set $A_3$ (for every choice of $A_1,A_2$) containing only those elements, which are in set $\{1,...,n\}$ and aren't in $A_1$ nor $A_2$. So we can say, we're just considering triples $(A_1,A_2,A_3)$, where $A_i \cap A_j = \emptyset$, for every $i,j \in \{1,2,3\} $, $ i \neq j$. And $A_1 \cup A_2 \cup A_3 = \{1,...,n\}$. How to do this? Just take elements in $\{1,...,n\}$ one by one, and ask yourself, whether u want to put it in $A_1,A_2$ or $A_3$. How many ways it gives? Well, there are $n$ elements, and $3$ choices for every, so $3^n$.

We ended up with $\sum_{k=0}^n {n \choose k} 2^{n-k} = 3^n$


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.