Stars and Bars Derivation

Question

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.

Answer 1

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.

Answer 2

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.