Distributions & Stars and Bars

## What you need to know
- Stars and bars: nonnegative integer solutions of $x_1 + \cdots + x_k = n$ number $\binom{n+k-1}{k-1}$; positive solutions number $\binom{n-1}{k-1}$.
- Distributing $n$ identical objects into $k$ distinct boxes is the same count; a lower bound $x_i \ge a_i$ is removed by substituting $y_i = x_i - a_i$.
- Upper bounds ($x_i \le m$) are handled by inclusion-exclusion over which variables exceed $m$.
- Distinct objects into distinct boxes: $k^n$, not stars and bars.
- Identical objects into identical boxes (partitions) have no formula; list them.
- Compositions of $n$ into positive parts, any number of parts: $2^{n-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: digit sums equal to $k$, number of terms in an expansion, ways to pay a total with coins.
- Problems 18–24: a cap ("no child receives more than $4$") forcing inclusion-exclusion, or an identical-versus-distinct twist.
- Often the numerator or denominator of a probability.

## Standard approaches
1. Classify first (objects identical or distinct, boxes identical or distinct); only identical-into-distinct is stars and bars.
2. Shift variables to remove lower bounds, then apply $\binom{n+k-1}{k-1}$.
3. For upper bounds, count all, subtract cases with one variable too big, add back cases with two.
4. For small $n$ or identical boxes, list partitions from the largest part downward.
5. Verify with a tiny case you can enumerate.

## 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. Without caps there are $\binom{14}{2} = 91$ solutions. If $a \ge 6$, put $a' = a - 6$; then $a' + b + c = 6$ has $\binom{8}{2} = 28$ solutions, and likewise for $b$ and $c$: $3 \cdot 28 = 84$. If two variables are at least $6$, they already sum to $12$ and the third is $0$: $3$ solutions. All three is impossible. Inclusion-exclusion gives $91 - 84 + 3 = 10$. Check: the valid triples are permutations of $(5,5,2)$, $(5,4,3)$, $(4,4,4)$, that is $3 + 6 + 1 = 10$. Answer $\boxed{\textbf{(B)}\ 10}$.

## Pitfalls
- Using $\binom{n+k-1}{k-1}$ when the objects are distinct (should be $k^n$) or the boxes are identical.
- Mixing up $\binom{n-1}{k-1}$ (positive parts) with $\binom{n+k-1}{k-1}$ (nonnegative parts).
- Forgetting to add back the double overlaps after subtracting over-cap cases.
- Miscounting bars: $k$ boxes need $k - 1$ bars.

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)