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.
The 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 is `C(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
Tiny worked example
- To count nonnegative solutions to `x+y+z=5`, draw 5 stars and 2 bars.\n- You choose the 2 bar positions among `5+2=7` total slots.\n- So the count is `C(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 this kind of problem
- 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.