Why does the combinatorial sum have the upper bound of $m$?

Question

What does $\sum_{k=0}^m{n \choose k} {n-k \choose m-k}$ mean?

Let's say we have $n$ balls, which are either black or white. We choose $k$ out of $n$ balls to be black, which means that out of the remaining $n-k$ balls, we choose $m-k$ to be white. Summing over this gives us the number of ways to choose either black or white balls from $n$. However, I am not sure why the sum goes all the way to $m$ and how that relates.

Answer 1

The formula gives you the number of ways to choose either black or white balls from $n$, but so that the total number of black or white balls is not larger than $m$ (i.e. $n-m$ balls are left unchosen).

Answer 2

I would suggest to alter the story as follows. We have $n$ distinguishable white balls in a bin and we would like to pick $m$ among them. Then, among those $m$ balls, we again choose some balls to be painted black, where the number of painted black balls is free to choose (might have zero number of black painted as well).

So we can break the counting into several cases. Suppose there are $k$ balls chosen to be painted black. It is clear that $0\le k\le m$, since we pick only $m$ balls in total from the whole $n$ balls collection.

There are many ways to count the number of choices. The one which suits the sum is described as follows. We first choose the balls to be painted black. Since there are $k$ black balls to be, there are ${n \choose k}$ choices. Next, to complete our picking of $m$ balls, we still need to choose $m-k$ balls from the remaining $n-k$ from the bin which are not to be painted black. There are ${n-k \choose m-k}$ such choices. So, in total, there are $$ \sum\limits_{k=0}^m {n \choose k}{n-k \choose m-k} $$ choices.

We can actually count in another way (which might also be more natural in daily conduct). Simply, pick first all the $m$ white balls from the bin and then choose a subset from those $m$ balls to be painted black. The number of such choices is ${n \choose m}2^m$. So, by double counting argument, we have $$ \sum\limits_{k=0}^m {n \choose k}{n-k \choose m-k} = {n \choose m}2^m. $$