https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two
I can see that in case 2, where it is possible to have bars in the same gaps, that there are $n+1$ gaps and $k-1$ bars. But surely the binomial coefficient of ${n+1}\choose{k-1}$ (number of ways of filling $n+1$ gaps with $k-1$ bars) discounts possibilities where bars are in the same gap? My formula is $$\frac{(n+1)^{k-1}}{(k-1)!}$$
As we have $n+1$ choices for position of each bar and the ordering of bars doesn't matter.
Moreover, how is the binomial coefficient ${n+1}\choose{k-1}$ $=$ ${n+k-1}\choose{n}$? It doesn't work for the case $ n= 7, k=4$?
Best Answer
Putting $k-1$ bars into $n+1$ gaps, putting $k-1$ balls into $n+1$ bins, and making a list of $n+1$ non-negative integers that sum to $k-1$: these are all equivalent problems, and you can draw a direct link between the solution to one and the solution to another.
But just doing bars in gaps, $(n+1)^{k-1}$ is the number of ways you can put the bars into gaps if it matters which bars are in which gap. You can confirm this with some (very small) test cases, for example write down all the ways $3$ numbered bars go in $2$ numbered gaps and all the ways $2$ numbered bars go in $3$ numbered gaps.
With stars and bars, the bars are a fictitious device in the first place. Draw just one of the possible ways of distributing the bars (with a number on each bar), showing where the stars are too, and see what result (grouping of stars you get). Now renumber the bars and see what groups of stars you get. Do the numbers on the bars make any difference?
So $(n+1)^{k-1}$ is too large. Can you fix this by dividing it by something? There are $(k-1)!$ ways to distribute the numbers when each of the first $k-1$ gaps is occupied by a bar. But there is only one way to put all the bars in the first gap. So you don’t have a nice relationship where every outcome you want to count is represented by exactly $M$ of the outcomes you have.
Faced with a dilemma like that, the best choice is to throw out everything and start over, trying to come up with a different way of attempting the problem.
I don’t even think of stars and bars as a process of “filling gaps.” I think of it as we have two kinds of objects, $k-1$ of one kind and $n$ of another, and I want to put them all in a row from left to right. If I only care what type of object is in each place in the row, there are $\binom{n+k-1}{k-1}$ ways to do this. Then I call the first kind of object a bar and the second kind a star and see what grouping of stars I get.