Number of ways to pick an equal number of elements from two sets?

288 Views Asked by At

There are two groups such that one group contains $m$ elements and another group contains $n$ elements. We have to find number of ways to pick same number of elements from both the groups.

My approach is $1+\dbinom m1.\dbinom n1+\dbinom m2 . \dbinom n2 +.... $upto $\dbinom mm$ or $\dbinom nn$ whatever is smaller.
Is there any faster way to do the same?

Example:
$3$ and $2$
$1+\dbinom 31.\dbinom 21+\dbinom 32 . \dbinom 22=10$ ways

1

There are 1 best solutions below

0
On

Yes, you can do better! The number of objects as you've described can be written as:

$$ \sum_{k=0}^{\min(m,n)} \binom{n}{k}\binom{m}{k}. $$

Notice that we could choose to stop the sum at either $m$ or $n$, regardless of which one is larger. For instance, even if $m>n$, whenever $k>n$ the first factor vanishes. We'll choose to stop the summation at $m$, and then apply the symmetry of binomial coefficients to get

$$ \sum_{k=0}^m \binom{n}{k}\binom{m}{m-k} $$

I claim that this can simplify in the following way:

Proposition: $\qquad\qquad\displaystyle \sum_{k=0}^m \binom{n}{k}\binom{m}{m-k} = \binom{m+n}{m}$.

The right-hand side clearly counts the number of ways to choose $m$ objects from $m+n$. The left-hand side also counts this because you must choose some number of the first $n$; call that $k$. By definition, the other $m-k$ must be chosen from the remaining $m$. Apply the product principle and we're done.