Stars and bars
Also known as: balls and urns, sticks and stones
Stars and bars is a counting technique for distributing identical objects into distinct groups. Representing the objects as stars and the dividers between groups as bars turns the problem into a straightforward combination count.
The setup: you have n identical items to hand out among k distinct recipients, and you want the number of ways to do it. Draw the items as n stars in a row, then insert k − 1 bars to split the row into k sections; the first section is recipient 1's share, the second is recipient 2's, and so on. Every arrangement of stars and bars corresponds to exactly one distribution, so counting arrangements counts distributions.
When recipients may receive nothing, you are arranging n + k − 1 symbols and choosing which k − 1 of those positions are bars, giving C(n + k − 1, k − 1). Distributing 7 identical candies among 3 children is C(7 + 3 − 1, 3 − 1) = C(9, 2) = 36. If every recipient must get at least one item, hand out one item to each first, then distribute the remaining n − k freely: C(n − 1, k − 1). For 7 candies among 3 children with none left empty, that is C(6, 2) = 15.
Equivalently, stars and bars counts the non-negative integer solutions to x₁ + x₂ + ... + x_k = n — the same formula, stated algebraically. Lower bounds other than 1 are handled by subtracting them out first; upper bounds require inclusion-exclusion on top of the basic count.
The critical condition is that the objects are identical and the groups are distinct. If the objects are distinguishable, each one independently chooses a group and the answer is kⁿ instead. Misreading which side is identical is the most common error on these problems.
Stars and bars is standard AMC competition material. It appears explicitly in AMC 10/12 counting and probability work and shows up on the AMC 8 through bijection problems, where the whole point is recognizing that an unfamiliar arrangement is really the same object as a known one.
Key takeaways
- Stars and bars counts ways to distribute identical objects into distinct groups by arranging n stars and k − 1 dividing bars.
- With empty groups allowed, the count is C(n + k − 1, k − 1); requiring at least one per group gives C(n − 1, k − 1).
- It is equivalent to counting non-negative integer solutions of x₁ + x₂ + ... + x_k = n.
- The method requires identical objects and distinct groups — distinguishable objects give kⁿ instead.
- Upper bounds on group sizes need inclusion-exclusion layered on top of the basic formula.