# Evaluate $\sum\limits_{k = 0}^n \binom{n}{n-k} \binom{m}{k}$. Give combinatorical arguments.

Evaluate $$\sum\limits_{k=0}^n \binom{n}{n-k} \binom{m}{k}$$, $$n \leq m$$. So far, I have $$\sum\limits_{k=0}^n \binom{n}{n-k} \binom{m}{k}=\sum\limits_{k=0}^n \binom{n}{k} \binom{m}{k}$$ since $$\binom{n}{n-k} = \binom{n}{k}$$. I believe I need to use Vandermonde's Identity somewhere, but I'm not sure what to do from where I'm at.

• "I believe I need to use Vandermonde's Identity somewhere" This is the left hand side of Vandermonde's identity (or right hand side, depending on the order in which you write it). – JMoravitz Oct 3 '18 at 19:25

## 1 Answer

Vandermonde's Identity:

$$\sum\limits_{k=0}^r \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$

Your expression you wish to evaluate is exactly this where we replace $$r$$ by $$n$$.

An example of a combinatorial argument: Suppose you have $$n$$ men and $$m$$ women. We wish to make a team of $$n$$ people. We could count how many ways we could do this by just choosing $$n$$ people directly from the $$n+m$$ total people. Alternatively we could count this by breaking into cases based on the number of men selected in the group which yields the expression given.

• I didn't think of it that way. Thanks for clearing that up for me. – cosmicbrownie Oct 3 '18 at 19:28
• Would you call this a combinatorical argument? – GNUSupporter 8964民主女神 地下教會 Oct 3 '18 at 19:28
• @GNUSupporter8964民主女神地下教會 no, I wouldn't but given that the OP has heard of vandermonde's identity before, I would assume that they are aware of the combinatorial proofs for vandermonde's identity in the first place. If they are not aware of such proofs, there is one included in the wikipedia link. – JMoravitz Oct 3 '18 at 19:30
• OK. This addresses the first prompt in the question body. I believe that the link can help others. – GNUSupporter 8964民主女神 地下教會 Oct 3 '18 at 19:32