# How many pairs of sets that have no element in common?

Consider three positive integers n, k and m such that k <= m.

And a set S = {1,2,…,n+k}.

There are $${ {n+k} \choose {k}}$$ subsets of size k from the set S, and $${ {n+k} \choose {m}}$$ subsets of size m from the set S.

So there is a total of $${ {n+k} \choose {k}} * { {n+k} \choose {m}}$$ pairs of subsets that I can choose from, but I need to eliminate any pair $$p=(s1,s2)$$ such that $$s1∩s2 ≠ ∅$$ that is to say if they have at least one element in common, it has to be counted so we can eliminate it from the total.

For example: n = 3, k = 2 and m = 3 S = {1,2,3,4,5}

Pairs = [({1,2}, {1,2,3}), ..., ({1,2}, {3,4,5})..., ({4,5}, {3,4,5})] So for the 3 explicit examples above, there are 2 to be eliminated: ({1,2}, {1,2,3}) -> common elements are {1,2} ({4,5}, {3,4,5}) -> common elements are {4,5}

No elimination for ({1,2}, {3,4,5}) because the 2 sets of {1,2} and {3,4,5} are disjoint.

So, how many pairs of sets that have no element in common?

Thanks

The $$k-$$set can be choosen in $$\binom{n+k}{k}$$ ways. There are only $$n$$ elements left to choose from, so the $$m-$$set can be choosen in $$\binom{n}{m}$$ ways. That makes ... $$\begin{eqnarray*} \binom{n+k}{k}\binom{n}{m} = \frac{(n+k)!}{k!m!(n-m)!}. \end{eqnarray*}$$
• It is worth pointing out that $\binom{n+k}{k}\binom{n}{m} = \binom{n+k}{m}\binom{n+k-m}{k}$, that we could have chosen the sets in the other order and gotten the same result. Commented Nov 22, 2019 at 15:51