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

Question

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

Answer 1

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*}