Counting / Stars And Bars
Least You Need to Know: Stars and Bars
Stars and bars counts ways to distribute identical objects into distinct boxes by turning the problem into positions for separators.
Least you need to know
- Use stars and bars when identical objects go into distinct boxes.
- For nonnegative solutions to
x1 + ... + xk = n, the count isC(n+k-1, k-1). - Minimum requirements are handled by subtracting them first.
- Distinct objects usually call for permutations or functions, not stars and bars.
- The bars mark boundaries between boxes.
Key notation
- ★ — one identical object
- | — separator between boxes
- C(n,r) — binomial coefficient
Worked example
- To count nonnegative solutions to
x+y+z=5, draw 5 stars and 2 bars.\n- You choose the 2 bar positions among5+2=7total slots.\n- So the count isC(7,2)=21.
Common mistakes
- Students often use the formula when the objects are distinct.
- Students forget to subtract lower bounds before applying the formula.
- Students sometimes choose stars instead of bar positions, which is fine only if done consistently.
How to recognize it
- The variables are counts of identical items.
- The problem asks for nonnegative or positive integer solutions.
- You can model the outcome by separators between groups.
Next recommended lesson
Try Least You Need to Know: Inclusion-Exclusion next for a nearby refresher.
Least You Need to Know: Inclusion-ExclusionRelated lessons
Keep going with nearby lessons in the same topic.