1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.