2
$\begingroup$

I am attempting to solve this counting problem through combinatorial argument. The following is the equation I am given:

$$\sum_{i=0}^k \binom{m+k-i-1}{k-i}\binom{n+i-1}{i} = \binom{m+n+k-1}{k}$$

To be honest I'm pretty lost with this one... This reminds me of problems where you use pirates and gold, but I am not sure what is being counted in either of side of this equation. I keep trying to think of how we are partitioning a given set, but I can't come up with an example.

Thanks!

$\endgroup$
  • $\begingroup$ Tell us more about the Pirates and the gold ! $\endgroup$ – user230452 Feb 25 '16 at 13:02
2
$\begingroup$

HINT: Let $A=\{0,1,2,\ldots,m+n+k-2\}$; we want to count the subsets of $A$ of cardinality $m+n-1$.

On the one hand this is clearly

$$\binom{m+n+k-1}{m+n-1}=\binom{m+n+k-1}k\;,$$

since $|A|=m+n+k-1$.

On the other hand, if $S$ is such a subset, there is a unique $\ell_S\in S$ such that $n-1$ elements of $S$ are less than $\ell_S$, and $m-1$ elements of $S$ are greater than $\ell_S$. Clearly the smallest possible value of $\ell_S$ is $n-1$, and with a little work you can calculate that the largest possible value of $\ell_S$ is $n+k-1$. If we let $i_S=\ell_S-n+1$, the range of possible values of $i_S$ is from $0$ through $k$. For each of the possible values of $i_S$ we want to count the sets $S$ having that value; then we want to sum over the possible values of $i_S$.

  • Given $i$, how many ways are there to choose $m-1$ elements of $A$ that are less than $\ell=n+i-1$?
  • And how many ways are there to choose $n-1$ elements of $A$ that are greater than $\ell=n+i-1$?
  • Putting the pieces together, how many subsets $S$ of $A$ with cardinality $m+n-1$ have $i_S=i$?

Now sum over the possible values of $i$ and show that your summation is equivalent to

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

$\endgroup$
  • $\begingroup$ @brianmscott Thanks for the help Brian!! $\endgroup$ – King Tut Feb 22 '16 at 8:57
  • $\begingroup$ @KingTut: You’re very welcome! $\endgroup$ – Brian M. Scott Feb 22 '16 at 8:59

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.