Stars and Bars Derivation I am trying to understand the derivation of the stars and bars formula. I understand how a problem can be converted to the stars and bars format, but I am confused about how the problem of choosing all the different ways to put k stars in n sections can be written as ${n+k-1 \choose k}$. Generally "n choose k" is for counting the number of combinations of k objects we can get given n distinct objects right? That I understand since we're doing permutation divided by the number of orderings for each group since order doesn't matter. I need help figuring out how stars and bars fits into this.
 A: Consider $n=5$ and $k=3$.  Take as an example a particular solution where the first group contains 2 elements, the second 3, and the third 0.  You can express this as a string, like "**|***|", where the stars are items and the vertical bars are boundaries between groups.  Any solution for this problem can be expressed as a string with 5 stars and 2 vertical bars, and any such string corresponds to a solution, so there is a 1-to-1 relationship between these strings and solutions to the problem.
There are $\binom{a+b}{a}$ ways to generate strings with $a$ elements of one type and $b$ elements of another.  So there are $\binom{n+k-1}{n} = \binom{n+k-1}{k-1}$ ways to make these strings, and that is also the number of solutions for the problem.
A: Stars and bars is used to enumerate the sums of $k$ numbers that add to $n$.  You need to distinguish whether $0$ is allowed as a number for this.  If it is not, you have $n$ stars and $n-1$ places between the stars to separate them, so the number of possibilities is $n-1\choose k-1$.  If $0$ is permitted that approach doesn't work because you now allow multiple separators in a space.  The clever trick is to add $1$ to each number and disallow $0$.  As you have added $1$ to $k$ numbers, you now have $n+k$ stars and $n+k-1$ spaces between them to put the bars.  You now have $n+k-1 \choose k-1$ ways to place the bars.
