Number of ways to choose same number of elements from two different sets Given two sets of elements S and R, with p elements and q elements respectively. 1 &lt;= p,q &lt;= 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?
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.