1
$\begingroup$

Given two sets of elements S and R, with p elements and q elements respectively. 1 <= p,q <= n. Now, the number of ways to choose same number of elements from set S and R is $$\sum_{i=0}^{\min(p, q)} pCi * qCi$$. I want to calculate the result for all possible combinations of p and q. I can think of a O(n^3) solution by first calculating all the mCr values for all possible combinations of m and r. And then for each pair of (p, q) answer is the sum of products of the pre-calculated terms. Is there any way to do it within O(n^2) time?

$\endgroup$
  • $\begingroup$ Thank you. Using Vandermonde's identity it can be computed in O(n^2) time. $\endgroup$ – Soumen Nov 5 '18 at 14:58
1
$\begingroup$

Sometimes a summation of products of binomial coefficients can be simplified using Vandermonde's identity.

In your case, Assuming $p\ge q$ we have $\sum^q_{k=0}{p\choose k}{q\choose k}=\sum^q_{k=0}{p\choose k}{q\choose q−k}$, which by Vandermonde equals $p+q\choose q$.

Actually this equality can be understood with elementary combinatorial arguments. Put the $p+q$ elements in one box. Now grabbing $q$ elements from the box means you have selected some $i$ elements from $S$ and $q−i$ elements from $R$. Or unselected $i$ elements from $R$ which is the same.

$\endgroup$

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.