Sum involving to combinatorics

Question

I want to calculate the following sum: $$\sum_{m=1}^{\min\left\{M,n\right\}} \binom{N-M}{n-m}\binom{M}{m}.$$

Attempt: The above sum is a part of a bigger problem. By rearranging the bigger problem, I found that instead of above sum I need to find an ``alternative'' sum which is $$\sum_{m=1}^{\min\left\{M,n\right\}} \binom{N-n}{M-m}\binom{n}{m}.$$ I also found that such sums may be related to Gamma function, but I could not apply it here.

Answer 1

Hint:

Suppose there are $N$ people, $M$ of which are women and the remaining $N-M$ of which are men. Count how many ways there are to select $n$ of them such that there is at least one woman:

• Directly

or

• Indirectly by breaking into case based on the number of women selected

---

If we do it indirectly, we get the expression you wrote in your question, $\sum\limits_{m=1}^n \binom{N-M}{n-m}\binom{M}{m}$ (note, the min in the limits doesn't actually matter)

If we do it directly, you get a much simpler expression. I'll leave it to you to find that expression. The analogy of men and women and selecting $n$ of them should make it clear how to proceed. By the nature that these expressions both correctly count the same scenario, they must be equal despite appearing differently.

Count how many ways you can choose $n$ people from the $N$ available and remove those ways that contained only men.