Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

Consider the sum $\displaystyle\sum_{j=r}^{n+r-k} \binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}$

I am looking to show this identity combinatorially. Is the general idea perhaps to remove j from n and k from r then pick some 'middle' element, and form a final subset of size r-1? The bounds on the sum are a big roadblock for me.

share|improve this question

marked as duplicate by Micah, Amzoti, Paul, user17762, Joe Apr 25 '13 at 3:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
This question is a duplicate of several questions, but not of the one that is linked to. That question involves the classical Vandermonde identity, with summation over the lower index. Here the summation is over the upper index, and there are shifts $-1$. Also classical Vandermonde is a polynomial identity in its (fixed) upper indices, this one is not polynomial at all. The two are related, but it is not even easy to see how exactly. And in any case the combinatorial explanations for the two identities are rather different. –  Marc van Leeuwen Apr 25 '13 at 13:28
    
Here is a question of which this one is a duplicate: math.stackexchange.com/q/326107. Useful answers are also at math.stackexchange.com/questions/73015 and math.stackexchange.com/q/76819. –  Marc van Leeuwen Apr 25 '13 at 13:48
    
One more hit for a true duplicate: math.stackexchange.com/questions/98495/… –  Marc van Leeuwen May 7 '13 at 11:57

2 Answers 2

up vote 2 down vote accepted

Take $n$ objects $1,2,3,\dots, n$, and choose $k$ of them in $\binom{n}{k}$ ways.

Alternatively, suppose the $r$-th largest selection is in position $j$. Then there are $\binom{j-1}{r-1}$ ways to choose the smallest $r-1$ objects and $\binom{n-j}{k-r}$ ways to choose the largest $k-r$ objects.

Now to combine for all possible values the $r$-th selection can be, we have to fit the first $r$ in positions $j$ and under, so $j \geq r$. Similarly, we have to fit the remaininkg $k-r$ in positions $j+1$ through $n$, which gives $k - r \leq n - (j+1) + 1$, or $j \leq n + r - k$.

share|improve this answer

Classify the $k$-element subsets of $\{1,2,\dots,n\}$ according to their $r$-th element. That element will always be at least $r$ (obviously) and at most $n-(k-r)$ (because there are $k-r$ more elements in the subset after the $r$-th element). If you call the $r$-th element $j$, then $j$ is in the range given for your sum. Furthermore, the factor $\binom{j-1}{r-1}$ counts the possibilities for the $r-1$ elements of your subset that precede the $r$-th element, while the other factor $\binom{n-j}{k-r}$ counts the possibilities for the $k-r$ later elements of your subset.

share|improve this answer
    
Thank you both, your explanations were very clear. Points awarded to both of you but acceptance given to Michael for his edit (it was really that close) which fixed up my messy question. –  user73041 Apr 25 '13 at 0:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.