3
$\begingroup$

I saw this question here:- Combinatorial sum identity for a choose function

This looks so much like a vandermonde identity, I know we can give a counting argument for Vandermonde. However much I try I am not able to come up with a counting argument for this.

$\endgroup$
3
$\begingroup$

Let $S=\{-m,-m+1,\ldots,n-1,n\}$; $|S|=m+n+1$, and we want to count the subsets of $S$ of cardinality $r+s+1$. Suppose that $A$ is such a subset. Then there is a unique $k_A\in A$ such that $r$ members of $A$ are smaller than $k_A$, and $s$ members of $A$ are larger than $k_A$. Let $\mathscr{A}_k$ be the family of $(r+s+1)$-element subsets $A$ of $S$ such that $k_A=k$. There are $k-(-m)=m+k$ elements of $S$ less than $k$ and $n-k$ elements of $S$ greater than $k$, so

$$|\mathscr{A}_k|=\binom{m+k}r\binom{n-k}s\;.$$

Summing over $k$ gives us the total number of $(r+s+1)$-element subsets of $S$, which is of course $\binom{m+n+1}{r+s+1}$, so

$$\sum_{k=-m}^n\binom{m+k}r\binom{n-k}s=\binom{m+n+1}{r+s+1}\;.$$

$\endgroup$
  • $\begingroup$ Could you clarify this "there are k-(-m)=m+k elements of S less than k and n-k elements greater than k " ? Here k is just a element of A right? $\endgroup$ – Amrita Sep 23 '16 at 19:27
  • 1
    $\begingroup$ @Amrita: $k$ is a potential element of some $A$, so it can be any element of $S$. Since $-m$ is the smallest element of $S$, there are $k-(-m)$ elements of $S$ smaller than $k$. Similarly, since $n$ is the largest element of $S$, there are $n-k$ elements of $S$ larger than $k$. I use that information to count the sets $A\subseteq S$ such that $|A|=r+s+1$, $k\in A$, and $A$ has exactly $r$ of its elements less than $k$. $\endgroup$ – Brian M. Scott Sep 23 '16 at 19:32
  • $\begingroup$ Wow! you came up with this in 20 mins. I have been trying that question since it was posted. I would be very interested in knowing how you started and approach such a question. $\endgroup$ – Amrita Sep 23 '16 at 19:41
  • 1
    $\begingroup$ @Amrita: As you said in the question, it strongly resembles Vandermonde’s identity, so I looked for a combinatorial argument similar to the one for that identity. The terms in the summation are clearly choosing $r$ members of one set and $s$ of another, and the righthand side is clearly counting sets of size $r+s+1$, so experience tells me that there’s a good chance that the lefthand side is counting sets categorized by their $(r+1)$-st member, the one with $r$ elements below it and $s$ above. Then it was just a matter of checking that $m+k$ and $n-k$ fit that interpretation. $\endgroup$ – Brian M. Scott Sep 23 '16 at 19:46
  • 2
    $\begingroup$ @Sarah: List the $r+s+1$ elements of $A$ from smallest to largest; the $(r+1)$-st element in that list is the only member of $A$ that is larger than $r$ members of $A$ and smaller than $s$ members of $A$. $\endgroup$ – Brian M. Scott Sep 28 '16 at 21:29
0
$\begingroup$

You have $m+n+2$ identical coins, and $r+s+2$ distinct boxes.
How many ways are there to place all the coins in the boxes so no box is empty?

If you place these $m+n+2$ coins in a line, then there are $m+n+1$ spaces between pairs of adjacent coins, and we can choose $r+s+1$ of these spaces to place a divider in. These dividers split the row of coins into $r+s+2$ contiguous blocks, representing the $r+s+2$ boxes, and therefore uniquely describing a placement of coins in boxes. Therefore, the number of ways to place the coins is $\binom{m+n+2}{r+s+1}$.

On the other hand, we can instead count how many ways to place the coins there are where the first $r+1$ boxes receive $m+k+1$ coins total, meaning the remaining $s+1$ boxes receive the remaining $n-k+1$ coins, and then sum over $k$. By the same argument, there are $\binom{m+k}r$ ways to place the $m+k+1$ coins in the first $r+1$ boxes, and $\binom{n-k}{s}$ ways to place the remaining $n-k+1$ coins in the other $s+1$ boxes.

$\endgroup$

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.