I've come across the Stars and Bars theorem on Brilliant.
It states that the number of ways you can put n items in k urns is as follows:
$$ n+k-1 \choose k-1$$
I understand where this equation comes from in this example. But I noticed it looks exactly like the Combinations with Repetition equation:
$$ \left( {n \choose k }\right) = {n+k-1 \choose k} $$
Does that mean that Stars and Bars is actually just a special case of Combinations with Repetition?
Best Answer
They are equivalent.
Suppose you know how to do combinations with repetitions, and you have the classic stars-and-bars problem. You have $n$ stars and $k-1$ bars to put among them, in the $n-1$ positions between the stars, the position before all stars, or the position after all stars. That means making $k-1$ choices among $n+1$ positions with repetitions allowed, which gives $$\left(\binom{n+1}{k-1}\right) = \binom{n+k-1}{k-1},$$ the stars-and-bars formula.
Alternatively, pick which urns the items go into, allowing repetitions, so you are making $n$ choices among $k$ items, with repetitions, yielding $\bigl(\binom{k}{n}\bigr) = \binom{k+n-1}{n}=\binom{n+k-1}{k-1}$ again.
Conversely, suppose you know the stars and bars formula, and you want to make $k$ choices, repetitions allowed, among $n$ possibilities. Take $n$ urns, labeled like your objects, and $k$ counters. Putting a counter in an urn is the same as selecting the corresponding item. Making the selection is then the same as the number of ways of putting $k$ counters in $n$ urns with repetitions allowed, so the formula for $\left(\binom{n}{k}\right)$ becomes, using stars and bars (note that the roles of $k$ and $n$ are reversed here from your formula, as we have $n$ urns and $k$ counters): $$\binom{k+n-1}{n-1} = \binom{n+k-1}{k}$$ which is the formula for combinations with repetitions.