Distributions & Stars and Bars

What you need to know

• Stars and bars (also called balls and urns). The equation $x_1+x_2+\dots+x_k = n$ has $\binom{n+k-1}{k-1}$ solutions in whole numbers that are zero or positive, and $\binom{n-1}{k-1}$ if every $x_i$ is at least $1$. Why: line up $n$ stars and $k-1$ bars. The bars cut the stars into $k$ groups ($\star\star|\star|\star\star$ means $2+1+2$), so you choose which $k-1$ of the $n+k-1$ spots are bars. Example: $x+y+z = 5$ has $\binom72 = 21$ solutions, or $\binom42 = 6$ with each at least $1$.
• Identical objects to different people (or boxes) is the same count: $x_i$ is what person $i$ gets. If person $i$ must get at least $a_i$, give them $a_i$ first. (In symbols, use $y_i = x_i - a_i$, which only has to be zero or positive.) Example: $10$ identical candies to $3$ kids, at least $2$ each: hand out $6$, then share the other $4$ in $\binom62 = 15$ ways.
• Upper limits ($x_i$ at most $m$) need inclusion-exclusion (PIE): subtract the solutions with some variable over $m$, then add back the overlaps. See the worked example.
• Different objects into different boxes is not stars and bars. Each of the $n$ objects picks a box: $k^n$ ways. Example: $4$ different books to $3$ kids: $3^4 = 81$ ways.
• Identical objects into identical boxes (partitions) have no formula; list them, largest part first. Example: $5$ splits into parts in $7$ ways: $5$, $4+1$, $3+2$, $3+1+1$, $2+2+1$, $2+1+1+1$, $1+1+1+1+1$.
• Ordered sums. $n$ can be written as an ordered sum of positive whole numbers (any number of parts) in $2^{n-1}$ ways. Why: in $1+1+\dots+1$, each of the $n-1$ plus signs either stays or is erased. Example: $4$ has $2^3 = 8$, such as $3+1$, $1+3$, and $1+2+1$.

How AMC 10 tests it

• Problems 10–18: "How many ways can $10$ identical candies be given to $4$ children if each gets at least one?"
• Equations in disguise: numbers whose digits add up to a given total, the number of terms in an expansion, ways to pay an amount with coins.
• Problems 18–24: a cap ("no child receives more than $4$") that forces PIE, or a twist about identical versus different objects.
• Often the top or bottom of a probability fraction.

Standard approaches

1. Sort first: identical or different objects? Identical or different boxes? Only identical objects into different boxes is stars and bars.
2. Shift variables to remove lower limits, then use $\binom{n+k-1}{k-1}$.
3. For upper limits, count all, subtract the cases with one variable too big, add back the cases with two, subtract the cases with three, and so on. Stop when that many variables cannot all be too big at once.
4. For small $n$ or identical boxes, list the partitions from the largest part down.
5. Check on a tiny case you can list.

Worked example

How many ordered triples $(a, b, c)$ of nonnegative integers satisfy $a + b + c = 12$ with $a \le 5$, $b \le 5$, and $c \le 5$?

(A) $7$ (B) $10$ (C) $19$ (D) $28$ (E) $91$

Solution. "Nonnegative" means zero or positive.

Step 1: ignore the limits. With $12$ stars and $2$ bars: $\binom{14}{2} = 91$ solutions.

Step 2: subtract the too-big cases. If $a \ge 6$, write $a = a'+6$, with $a'$ zero or positive. Then $a'+b+c = 6$, which has $\binom82 = 28$ solutions. The same holds for $b$ and for $c$, so subtract $3\cdot28 = 84$.

Step 3: add back the overlaps. A solution with two variables at least $6$ was subtracted twice. If $a\ge6$ and $b\ge6$, then $a = b = 6$ and $c = 0$: one solution for each of the $3$ pairs, so add back $3$. All three is impossible.

Step 4: combine. $91-84+3 = 10$.

Check. The triples are the orderings of $(5,5,2)$, $(5,4,3)$, and $(4,4,4)$: $3+6+1 = 10$.

The answer is $\boxed{\textbf{(B)}\ 10}$.

Pitfalls

• Using $\binom{n+k-1}{k-1}$ when the objects are different (the answer is $k^n$) or the boxes are identical (list the partitions).
• Mixing up $\binom{n-1}{k-1}$ (every part at least $1$) with $\binom{n+k-1}{k-1}$ (parts can be $0$): $6$ versus $21$ for $x+y+z = 5$.
• Forgetting to add back the double overlaps after subtracting the over-the-limit cases (here that gives $7$, choice (A)).
• Miscounting bars: $k$ boxes need $k-1$ bars, not $k$.

Traps that recur

• Distributing the five 2's without requiring every factor to exceed 1, which counts factors equal to 1 and overcounts badly. (2020 AMC 10B #25)
• Forgetting that dice cannot show 0 and counting solutions to a sum of 10 over 7 nonnegative variables, or worrying about the upper bound 6 when it cannot bind. (2018 AMC 10A #11)
• Dropping the constant 1 from the count (treating the exponents as summing to exactly N with no slack), which gives C(N-1, 3) and no matching choice. (2016 AMC 10A #20)
• Treating the six cookies as distinguishable and answering 3^6 = 729, choice (E). (2003 AMC 10A #21)