Counting Multisets: Stars and Bars

Stars and bars is simply a way to count selections where you're allowed to take the same thing more than once, like filling a box of donuts when you can pick three glazed. The name is literal: you draw each donut as a star and use bars as dividers between flavors. It's good for any problem about splitting identical things among groups, like cookies among children or servers among services. The answer $\binom{n + k - 1}{k - 1}$ looks odd, but its pieces are friendly: $n$ (how many donuts), $k$ (how many flavors), $k - 1$ (the number of dividers you need to split a row into $k$ sections) and $n + k - 1$ (donuts plus dividers, all the spots in the row). So it's just "choose where the dividers go." Once you see the picture, the formula writes itself.

Combinations count selections where order doesn't matter, but they assume you can't pick the same thing twice. A box of donuts breaks that: you can take three glazed if you want. A selection like that, with repeats allowed and order ignored, is called a multiset. So how do we count those?

The trick is to find a picture where the problem becomes one we already know. Write a choice of $n$ items from $k$ types as a row of $n$ stars and $k - 1$ bars. The stars before the first bar are flavor 1, the stars between the first and second bars are flavor 2, and so on. For example, ★★|★|||★★★ is 2 of flavor 1, 1 of flavor 2, none of flavors 3 and 4, and 3 of flavor 5. You only need $k - 1$ bars because bars are dividers: 4 walls make 5 sections.

Notice that every box of donuts gives exactly one row of symbols, and every row gives exactly one box. So counting boxes is the same as counting rows. A row has $n + k - 1$ positions, and it's fixed once you choose which of them hold bars, so the count is $\binom{n + k - 1}{k - 1}$. The repeats that broke combinations have disappeared into an ordinary choice of positions.

The same count gives the nonnegative integer solutions of $x_1 + x_2 + \cdots + x_k = n$. That's the same problem in different clothes: $x_i$ is how many donuts of flavor $i$ you took.

At least one of each. If every type has to show up, give each type one item first. That uses $k$ items and leaves $n - k$ to distribute freely, so there are $\binom{(n - k) + k - 1}{k - 1} = \binom{n - 1}{k - 1}$ positive solutions.

A common mistake. It's tempting to use $k$ bars for $k$ types, or to choose positions for the stars out of only $n$ spots. Neither works. You need one fewer bar than types, and the stars and bars share the $n + k - 1$ positions, which is where the $-1$ in the formula comes from.

Allocating identical resources, such as server instances among services or seats among parties, is a stars-and-bars count.