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