Stars and bars is the counting trick in combinatorics for splitting identical things into labelled groups. It turns a question about sums into a question about where to put dividers, and the answer is a single binomial coefficient. The formula is one line. The work is deciding whether a problem fits it.
The two formulas
You have identical objects and labelled boxes. How many ways can you place the objects, if a box may be empty?
Equivalently, this counts the solutions of in non-negative integers. If every box must hold at least one object, the count is
Example: split identical sweets between children, empty hands allowed. That is ways. If every child must get at least one, it is .
Where the formula comes from
Draw the objects as stars in a row. To split them into boxes, you place bars among the stars. The stars before the first bar go in box one, the stars between the first and second bar go in box two, and so on. Two bars may sit next to each other, which gives an empty box.
For and , two stars then a bar then one star then a bar then two stars means box sizes . Each arrangement of stars and bars in a row of symbols is one distribution, and each distribution is one arrangement. You choose which of the places are bars, and that is .
For the "at least one" version, put one object in every box first. That leaves objects to distribute freely among boxes, which gives .
The shift trick for minimums
The "at least one" step is a special case of something you will use constantly. If , write and the new variable is free to be . The equation loses from its right side and the count follows.
Example: with every variable at least . Set and so on. Then in non-negative integers, which has solutions.
Upper limits, and the first trap
Stars and bars has no way to say "at most". When a variable is capped, count everything and subtract the violations. This is where inclusion-exclusion comes in: you add the counts of the bad cases and correct for the overlaps.
Example: with each of at most . Count all non-negative solutions: . Now subtract those where some variable is at least . If , set , leaving with solutions. There are three variables, so subtract . Now look at two variables that are both at least . Then both equal and the third is , which is one solution for each of the pairs. Those were subtracted twice, so add back . The answer is
You can confirm it with no formula. The only ways to write as three numbers up to are the permutations of , and , and those number .
A digit problem with a cap hidden in it
How many four-digit numbers have digit sum ? The thousands digit is at least , so write it as . Then in non-negative integers, giving . No digit can exceed because the sum is only , so no cap is violated.
Now ask for digit sum . The equation becomes , which has solutions. This time the cap bites in one place: means the leading digit would be . That is one bad solution, with the other three digits zero. The answer is .
Check whether the right-hand side is large enough for a cap to matter. When it is below the cap there is nothing to fix.
When it applies, and when it does not
Reach for stars and bars when you see:
- Identical objects into distinct boxes. Sweets, coins, balls, extra points.
- Non-negative integer solutions of a linear equation, with or without lower bounds.
- Multisets. Choosing items from types with repetition allowed has outcomes. The number of monomials of degree in three variables is .
- Compositions. Writing as an ordered sum of positive parts is the "at least one" formula.
It does not apply when the objects are distinct, because then each object chooses a box on its own and the count is . It does not apply when the boxes are identical either, since that is a partition problem with no closed formula. And if the constraint is something other than a sum, stars and bars alone will not do.
Choosing positions
The bars picture is one case of a wider habit: count by choosing positions instead of values. The same thinking proves Pascal's identity, and it is behind the counting argument for , where you decide for each item whether it is in or out.
To practise, make up four problems with caps and minimums mixed, and for each one write down what the substitution is before you write any binomial coefficient. If you cannot say it in one line, the problem is not yet a stars and bars problem. The constructive counting technique page has the wider habit, and the problem archive has more.
Related guides
- How a double counting proof is actually builtDouble counting proofs are always the same three steps, and only one of them is hard. The skeleton, five worked examples, and where they go wrong.
- Constructive vs complementary counting: which one to reach forTwo ways to count the same set, and one question that tells you which is cheaper. The signals, the worked pair, and the trap where the obvious tell lies to you.
- Generating functions: turning a counting problem into a productGenerating functions explained as a method: one factor per constraint, multiply, read the coefficient. The dictionary, and how to extract by hand.
- Chicken McNugget theorem: the proof and the formulaFor coprime a and b the largest total you cannot make is ab - a - b. The proof, the count of unmakeable totals, and what breaks with three sizes.
- Inclusion-exclusion principle in competition mathHow inclusion-exclusion counts a union, why the signs work, and four problem types it solves: divisibility, derangements, surjections and totients.
Techniques in this guide
- Constructive Counting & OvercountingBuild the object step by step, then divide by what you repeated.
Train it on Lemma
Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your level