Stars and Bars

n items into k bins with nonnegative counts gives n + k - 1k - 1.

The idea

Stars and bars counts the ways to distribute $n$ identical items among $k$ distinguishable recipients, where each recipient may receive any number of items, including none. Because the items are identical, an outcome is just a list of $k$ counts summing to $n$, and such lists are awkward to count directly.

Instead, encode each outcome as a row of symbols. Write the $n$ items as stars and insert $k - 1$ bars: the stars before the first bar go to the first recipient, the stars between the first and second bars to the second, and so on, with the stars after the last bar going to the last recipient. Two adjacent bars mean the recipient between them receives nothing. The row $\star\,\star \mid \star \mid \star\,\star$ records the distribution two, one, two.

Every distribution corresponds to exactly one row and every row to exactly one distribution, so counting the rows counts the distributions. A row has $n + k - 1$ positions and is determined by choosing which $k - 1$ of them hold the bars, so the number of distributions is $\binom{n + k - 1}{k - 1}.$

Ways to work on it

• Walkthrough. Count the ways to share identical items by encoding each split as stars and bars.
• Practice. Count distributions with small numbers of items and bins.
• Hardest. Count the ways to distribute identical items in a single step.

Not sure where to start? Take the ten-question placement test.