Stars and Bars

A common interview question asks: in how many ways can $n$ identical items be distributed among $k$ distinct groups (say, $n$ identical trade tickets assigned across $k$ traders, with any trader allowed to get zero)? Lining the $n$ items up as a row of stars, you need $k-1$ "bars" placed among them to mark the boundaries between groups — everything before the first bar goes to group 1, between the first and second bar to group 2, and so on. The count of arrangements is then just the number of ways to choose which $k-1$ of the $n+k-1$ total symbols (stars plus bars) are bars:

$$\binom{n+k-1}{k-1}.$$

For example, splitting $n=5$ identical trade tickets among $k=3$ traders (any trader can get zero) gives $\binom{5+3-1}{3-1} = \binom{7}{2} = 21$ possible ways to divide them up, a number that would be tedious to enumerate by hand but falls out immediately once the problem is reframed as arranging stars and bars.

The same idea answers a slightly different-looking question: how many ways can a fixed total, like 10 units of risk budget, be split among 4 desks if every desk must get at least one unit? That's solved by first handing each desk its mandatory 1 unit, leaving 6 units to distribute freely among 4 desks (zero allowed), which is again $\binom{6+4-1}{4-1} = \binom{9}{3} = 84$. This "give everyone the minimum first, then stars-and-bars the remainder" move is one of the most reused tricks in combinatorics interview questions, since it converts an awkward at-least-one constraint into the plain, no-constraint version of the same problem.