3
$\begingroup$

I think I got some serious problem with those combinatorial proofs. Why would the following be true ($1\leq r\leq k\leq n$):

$$\sum_\limits{j=r}^{n+r-k}\binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}?$$

It doesn't make sense to me. We could choose $r$-th element of our set and choose from lesser and greater elements but this is not what this formula gives.

$\endgroup$
6
$\begingroup$

There are of course $\binom{n}k$ ways to choose $k$ elements from the set $[n]=\{1,\ldots,n\}$. Now let’s count them in a different way. How many ways are there to choose a set $S$ of $k$ elements of $[n]$ so that $j$ is the $r$-th smallest element of the set?

  • There are $j-1$ elements of $[n]$ less than $j$, so we have to choose $r-1$ of them to be the $r-1$ elements of $S$ that are less than $j$. We can do that in $\binom{j-1}{r-1}$ ways.

  • There will be $k-r$ elements of $S$ that are bigger than $j$, and they must come from the $n-j$ elements of $[n]$ that are bigger than $j$, so there are $\binom{n-j}{k-r}$ ways to choose them.

Thus, there are

$$\binom{j-1}{r-1}\binom{n-j}{k-r}$$

ways to choose a $k$-element subset of $[n]$ whose $r$-th smallest element is $j$. Now just sum over the possible values of $j$ to get the identity.

$\endgroup$
  • $\begingroup$ $r$-th smallest, ok, that absolutely makes sense. Why didn't I see this? Man, I hope it'll come to me one day. $\endgroup$ – Jules Jun 20 '16 at 22:45
  • $\begingroup$ @Jules: Give it time: my experience has been that the more combinatorial arguments I see, the easier it is to come up with new ones. Some ideas just keep cropping up, and one gets a feel for where they might be useful. $\endgroup$ – Brian M. Scott Jun 20 '16 at 22:47
  • $\begingroup$ Yup, that's called expert's knowledge in psychology, right :) Thank you for your help! $\endgroup$ – Jules Jun 20 '16 at 22:49
  • $\begingroup$ @Jules: You’re welcome! $\endgroup$ – Brian M. Scott Jun 20 '16 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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