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?
1
-
$\begingroup$ Thank you. Using Vandermonde's identity it can be computed in O(n^2) time. $\endgroup$– SoumenNov 5, 2018 at 14:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Nov 10, 2018 at 14:14