Stars and Bars is the habit of counting nonnegative integer solutions and distributions by separators and objects. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
The number of ways to write $n$ as an ordered sum of $k$ nonnegative integers equals the number of ways to place $k-1$ dividers among $n$ identical objects.
Why It Works
1
Picture $n$ identical stars in a row; you must split them into $k$ ordered groups, where group $i$ has size $x_i$.
2
Inserting $k - 1$ bars into the line of stars creates exactly $k$ groups, and bars may be adjacent (allowing empty groups, i.e. $x_i = 0$).
3
So each solution corresponds to one arrangement of $n$ stars and $k - 1$ bars in a row of $n + k - 1$ symbols.
4
Choosing which $k - 1$ of those $n + k - 1$ positions are bars gives $\binom{n + k - 1}{k - 1}$.
Worked Examples
Example 1
How many nonnegative integer solutions does $x_1 + x_2 + x_3 + x_4 = 10$ have?
1
Here $n = 10$ (the total) and $k = 4$ (the number of variables).
Bad solutions have $x_1 \ge 8$; set $x_1 = x_1' + 8$ so $x_1' + x_2 + x_3 + x_4 = 12$, giving $\binom{12 + 4 - 1}{4 - 1} = \binom{15}{3} = \dfrac{15 \cdot 14 \cdot 13}{6} = 455$.
4
Subtract: $1771 - 455 = 1316$.
Answer:
$1316$
Going Deeper
The same model handles every variant by a substitution: lower bounds $x_i \ge c_i$ shift each variable down (subtract $\sum c_i$ from $n$), and upper bounds $x_i \le u_i$ are removed by inclusion-exclusion (subtract the cases where a capped variable overshoots). The inequality version $x_1 + \cdots + x_k \le n$ just adds a slack variable $x_{k+1} \ge 0$, giving $\binom{n+k}{k}$.
Stars and bars is the standard model for distributing identical objects into distinct boxes: candies to children, indistinguishable balls into urns, exponents in a monomial of fixed degree, or the number of degree-$n$ terms in $k$ variables. It shows up constantly on AIME distribution and 'how many solutions' problems.
Pitfall: the objects must be identical and the boxes distinct, and empty boxes must be allowed (otherwise substitute to a positive problem first). Using $\binom{n+k-1}{k-1}$ for distinguishable objects, or forgetting to handle upper bounds with inclusion-exclusion, are the two classic errors — and watch the index, it is $k-1$ bars, not $k$.
Spot the Signal
Look for problems where the key step is counting nonnegative integer solutions and distributions by separators and objects.
You can describe the hard part as counting nonnegative integer solutions and distributions by separators and objects, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the counting object that calls for stars and bars, then rewrite the givens around it.
Name the relation that makes Stars and Bars legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Stars and Bars just because the surface looks familiar; verify the required condition first.
Applying Stars and Bars because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let stars and bars reveal the counting structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is counting nonnegative integer solutions and distributions by separators and objects.