Lemma › Guides › Stars and bars: counting solutions, with the traps
Guide

Stars and bars: counting solutions, with the traps

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 nn identical objects and kk labelled boxes. How many ways can you place the objects, if a box may be empty?

(n+k−1k−1).\binom{n + k - 1}{k - 1}.

Equivalently, this counts the solutions of x1+x2+⋯+xk=nx_1 + x_2 + \dots + x_k = n in non-negative integers. If every box must hold at least one object, the count is

(n−1k−1).\binom{n - 1}{k - 1}.

Example: split 1010 identical sweets between 44 children, empty hands allowed. That is (133)=286\binom{13}{3} = 286 ways. If every child must get at least one, it is (93)=84\binom{9}{3} = 84.

Where the formula comes from

Draw the nn objects as stars in a row. To split them into kk boxes, you place k−1k - 1 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 n=5n = 5 and k=3k = 3, two stars then a bar then one star then a bar then two stars means box sizes 2,1,22, 1, 2. Each arrangement of nn stars and k−1k - 1 bars in a row of n+k−1n + k - 1 symbols is one distribution, and each distribution is one arrangement. You choose which k−1k - 1 of the n+k−1n + k - 1 places are bars, and that is (n+k−1k−1)\binom{n+k-1}{k-1}.

For the "at least one" version, put one object in every box first. That leaves n−kn - k objects to distribute freely among kk boxes, which gives ((n−k)+k−1k−1)=(n−1k−1)\binom{(n-k) + k - 1}{k - 1} = \binom{n-1}{k-1}.

The shift trick for minimums

The "at least one" step is a special case of something you will use constantly. If x1≥2x_1 \ge 2, write x1=2+y1x_1 = 2 + y_1 and the new variable is free to be 00. The equation loses 22 from its right side and the count follows.

Example: x+y+z=8x + y + z = 8 with every variable at least 22. Set x=2+x′x = 2 + x' and so on. Then x′+y′+z′=2x' + y' + z' = 2 in non-negative integers, which has (42)=6\binom{4}{2} = 6 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: x+y+z=12x + y + z = 12 with each of x,y,zx, y, z at most 55. Count all non-negative solutions: (142)=91\binom{14}{2} = 91. Now subtract those where some variable is at least 66. If x≥6x \ge 6, set x=6+x′x = 6 + x', leaving x′+y+z=6x' + y + z = 6 with (82)=28\binom{8}{2} = 28 solutions. There are three variables, so subtract 3⋅28=843 \cdot 28 = 84. Now look at two variables that are both at least 66. Then both equal 66 and the third is 00, which is one solution for each of the 33 pairs. Those were subtracted twice, so add back 33. The answer is

91−84+3=10.91 - 84 + 3 = 10.

You can confirm it with no formula. The only ways to write 1212 as three numbers up to 55 are the permutations of (5,5,2)(5, 5, 2), (5,4,3)(5, 4, 3) and (4,4,4)(4, 4, 4), and those number 3+6+1=103 + 6 + 1 = 10.

A digit problem with a cap hidden in it

How many four-digit numbers have digit sum 99? The thousands digit is at least 11, so write it as 1+x11 + x_1. Then x1+x2+x3+x4=8x_1 + x_2 + x_3 + x_4 = 8 in non-negative integers, giving (113)=165\binom{11}{3} = 165. No digit can exceed 99 because the sum is only 99, so no cap is violated.

Now ask for digit sum 1010. The equation becomes x1+x2+x3+x4=9x_1 + x_2 + x_3 + x_4 = 9, which has (123)=220\binom{12}{3} = 220 solutions. This time the cap bites in one place: x1=9x_1 = 9 means the leading digit would be 1010. That is one bad solution, with the other three digits zero. The answer is 219219.

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:

It does not apply when the objects are distinct, because then each object chooses a box on its own and the count is knk^n. 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 2n2^n, 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

Techniques in this guide

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