Combinatorics (Stars & Bars)

1. Introduction

A huge family of AMC 10/12 counting problems boils down to the same question: in how many ways can we split a total into parts? How many ways to distribute $10$ identical candies among $4$ kids; how many nonnegative solutions to $x_1 + x_2 + x_3 = 12$; how many monomials of degree $n$ in three variables. The single technique that answers all of these is stars and bars.

The idea is beautifully visual. Represent the total as a row of identical stars, and use bars to chop the row into groups. Because the stars are indistinguishable, the only thing that matters is where the bars go — and counting bar placements is just a binomial coefficient. Once you internalize this picture, an entire category of problems collapses to "choose where the dividers go."

Stars and bars rarely travels alone at the contest level. The moment variables get upper bounds (a child can have at most $5$ candies), naive stars and bars overcounts, and we patch it with inclusion–exclusion. This article builds the method from the ground up — the basic count, the positive-solution shift, lower and upper bounds, the inclusion–exclusion machinery, and disguised appearances — with worked contest examples throughout.

2. Core Concepts

Concept 1 — The Stars and Bars Picture

Suppose we want nonnegative integer solutions to $x_1 + x_2 + \cdots + x_k = n$. Lay down $n$ identical stars ($\star$) in a row. To divide them into $k$ groups, insert $k-1$ bars ($\mid$). For example, with $n = 5$ and $k = 3$, $\star\star \mid \star \mid \star\star \quad\longleftrightarrow\quad (x_1,x_2,x_3) = (2,1,2).$ Every arrangement of $n$ stars and $k-1$ bars gives exactly one solution, and vice versa.

Concept 2 — Nonnegative Solutions (The Fundamental Count)

Stars and Bars Theorem (nonnegative). The number of solutions to $x_1 + \cdots + x_k = n$ with each $x_i \geq 0$ is $\binom{n+k-1}{k-1} = \binom{n+k-1}{n}.$ We are arranging $n + (k-1)$ symbols and choosing which $k-1$ of them are bars.

Concept 3 — Positive Solutions (Nonempty Boxes)

If each $x_i \geq 1$, give every variable one star up front by substituting $y_i = x_i - 1 \geq 0$. Then $y_1 + \cdots + y_k = n - k$, so the count is $\binom{n-1}{k-1}.$ Equivalently: place one item in each box first, then distribute the remainder freely.

Concept 4 — Lower Bounds by Shifting

A lower bound $x_i \geq c_i$ is handled by the same shift: set $y_i = x_i - c_i \geq 0$ and reduce the total by $\sum c_i$. The count becomes $\binom{n - \sum c_i + k - 1}{k - 1}$ when $n - \sum c_i \geq 0$; otherwise there are no solutions.

Concept 5 — Upper Bounds Require Inclusion–Exclusion

An upper bound $x_i \leq c$ cannot be removed by a simple shift. Instead, let $A_i$ be the set of solutions where $x_i \geq c+1$. Subtract $|A_i|$, add back $|A_i \cap A_j|$, and so on. This is inclusion–exclusion.

Concept 6 — The Inclusion–Exclusion Principle

Inclusion–Exclusion Principle. For finite sets $A_1, \ldots, A_r$, $\left|\bigcup_{i=1}^{r} A_i\right| = \sum |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<\ell}|A_i\cap A_j\cap A_\ell| - \cdots.$ For bounded stars-and-bars, we count all solutions, subtract violations, add back double violations, etc.

Concept 7 — The Slack Variable Trick ("At Most")

The number of nonnegative solutions to $x_1 + \cdots + x_k \leq n$ equals the number of solutions to $x_1 + \cdots + x_k + x_{k+1} = n$ with $x_{k+1} \geq 0$, which is $\binom{n+k}{k}.$ The slack variable $x_{k+1}$ absorbs whatever is "left over."

Concept 8 — Violation Counting for One Upper Bound

If $x_i \leq c$ and we want solutions where $x_i \geq c+1$, substitute $x_i' = x_i - (c+1) \geq 0$ and reduce the total by $c+1$. The violation count is $\binom{n - (c+1) + k - 1}{k - 1}$ when $n \geq c+1$; otherwise $0$.

Concept 9 — When Stars and Bars Applies

Stars and bars requires identical objects in distinct boxes. Distinct objects need $n!$-style counts or the multiplication principle. Identical objects in identical boxes (partitions) is a harder topic not covered here.

Concept 10 — Multinomial Coefficients

The number of ways to arrange $n$ objects where type $i$ appears $n_i$ times (with $\sum n_i = n$) is the multinomial coefficient $\binom{n}{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1!\, n_2!\, \cdots\, n_k!}.$ This is stars and bars in disguise: choosing positions for each type of star.

Concept 11 — Monomials of Fixed Degree

The number of monomials $x_1^{a_1} \cdots x_k^{a_k}$ with $a_1 + \cdots + a_k = n$ and each $a_i \geq 0$ is exactly $\binom{n+k-1}{k-1}$ — distribute $n$ degree units among $k$ variables.

Concept 12 — Dice Sums as Bounded Distributions

Rolling $k$ dice that sum to $n$ is equivalent to positive solutions to $x_1 + \cdots + x_k = n$ with $1 \leq x_i \leq 6$. Shift to nonnegative $y_i = x_i - 1$ with $0 \leq y_i \leq 5$, then apply stars and bars plus inclusion–exclusion.