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

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.

• 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$. – Gae. S. Aug 2 '19 at 19:24
• 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. – 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$$