Stars and Bars

Stars and bars (also "balls in bins") counts the number of ways to distribute $n$ identical objects into $k$ distinct bins. Intuition: Line up $n$ stars (the objects) and insert $k-1$ bars (dividers) among them. Everything to the left of the first bar goes in bin 1, between bars 1 and 2 goes in bin 2, and so on. The total number of symbols is $n + k - 1$, and you choose where to place the $k-1$ bars. Formula (non-negative bins): $$\binom{n + k - 1}{k - 1}$$ Concrete example: Distribute 5 identical candies among 3 children. We need to place $k-1 = 2$ bars among $n + k - 1 = 7$ positions: $$\binom{7}{2} = 21 \text{ ways}$$ One distribution: $\star\star | \star \star \star |$ means child 1 gets 2, child 2 gets 3, child 3 gets 0. Variant (positive bins): If each bin must have at least 1 object, pre-place one object in each bin. Then distribute the remaining $n-k$ among $k$ bins: $$\binom{n - 1}{k - 1}$$ When to use: "How many non-negative integer solutions does $x_1 + x_2 + \cdots + x_k = n$ have?" This is the same problem in disguise. Also: distributing identical items, counting multisets, and partitioning integers with an upper bound on parts (with inclusion-exclusion). Alternative approach: Stars and bars is itself a fundamental technique. Many occupancy and distribution problems reduce to it.