# 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 <= 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?

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

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.