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?



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

  • 2
    $\begingroup$ 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. $\endgroup$ – JMoravitz Nov 22 '19 at 15:51
  • $\begingroup$ Thank you all. I was using the wrong variable name in my script and it made me doubt it. $\endgroup$ – Amine Marzouki Nov 22 '19 at 16:07

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.