I was looking for a different way of writing the formula of the number of different $k$-tuples of non-negative integers whose sum is equal to $n$ and I thought of this formula followed by this combinatorial proof :
$$
\sum_{i = 1}^k \binom{n + 1}{i}\binom{k – 1}{i – 1}
$$
The first combination is the number of positions that we can choose from to place the bars. There are $n+1$ positions to choose from, since now we can also place the bars before and after the stars. The next combination is the number of different ways of splitting the stars between the positions that were chosen for the bars to be placed.
Lastly, we'll have to add all the different ways of combinations of bar positions and number of bars in each position. I haven't found a flaw in my proof yet but I can't seem to conclude that the above formula is equal to $$\binom{n + k – 1}{k – 1}$$
Could someone more experienced verify my proof or show me where the flaw is?
Best Answer
Your formula and argument are incorrect, but they can both be made correct with a small change. The correct formula is $$ \sum_{i=1}^{n+1}\binom{n+1}{i}\binom{k-\color{red}2}{i-1} $$ The idea is this; once you have chosen the $i$ spaces out of $n+1$ which will receive bars, you now need to split the $k-1$ bars into $i$ non-empty groups. This can be done in $\binom{k-\color{red}2}{i-1}$ ways; if we now imagine a line of $k-1$ bars, with $k-2$ spaces between them, then such a partition is uniquely chosen by selecting a subset of $i-1$ spaces, and splitting at those spaces.
This combinatorial proof establishes the fact that $$ \sum_{i=1}^{n+1}\binom{n+1}{i}\binom{k-\color{red}2}{i-1}=\binom{n+k-1}{k-1} $$ It is easy to give an alternative proof of this by rewriting $\binom{k-2}{i-1}$ as $\binom{k-2}{k-1-i}$, and applying Vandermonde's identity.