While doing some Computer Science problems, I found one which I thought could be solvable using combinatorics instead of programming:
Given two positive integers $n$ and $k$, in how many ways do $k$ numbers, all of which are between $0$ and $n$ (inclusive), add up to $n$?
In the problem, order does matter. For example, 0+20 is not equivalent to 20+0. This led me to the following solution:
Assume you do want to create the sum without any of the terms being zero. Then, the problem can be looked at as if you have $n$ rocks, and you want know the number of ways you can place $k-1$ sticks between them, such that no stick may be placed between the same two rocks. This is obviously equal to $\binom{n-1}{k-1}$.
If you then want to count the number of ways you can create the sum with exactly one of the terms being zero. Then the solution is (number of ways to get to $n$ using $k-1$ non-zero terms)*(the number of ways we can choose 1 element among k). Then, when wanting to count the number of ways with exactly $x$ zeroes, the answer is (number of ways to get to n using $k-x$ non-zero terms)*(the number of ways we can choose $x$ elements among $k$).
The solution to the original problem will basically the sum of the above expression, with x ranging between $0$ and $k-1$ (since there needs to be at least 1 non-zero term).
This leads to
$\displaystyle\sum_{i=0}^{k-1}\left[ \binom{n-1}{k-i-1}\binom{k}{i}\right]$
I later went on to search on Google if there existed any simpler solution, and found that $\binom{n+k-1}{n}$ worked as well, but without explanation and proof.
Both solutions give the same answer for any positive $n$ and $k$, but I really have trouble understanding why. I've tried to simplify my summation, and proving it inductively, but I have not been successful.
Could somebody help me prove the equality?
$\binom{n+k-1}{n} = \displaystyle\sum_{i=0}^{k-1}\left[ \binom{n-1}{k-i-1}\binom{k}{i}\right]$
Best Answer
Taking your rocks and sticks example, your basic question is how many ways are there to place $n$ rocks and $k-1$ sticks in order as each pattern (of the rocks) is one solution to your problem. This is ${n+k-1 \choose n}$.
If $n=1$ then all your discussion of $i$ zero terms will come out at $0$ except when $i=k-1$ and in that case you will have $\left[ \binom{0}{0}\binom{k}{k-1}\right] = k$, so you do not need to distinguish $n=1$ in your expression.