Stars and Bars
Pillar: Set — "Bars partition a row of stars into groups. The number of bar-placement choices = the number of ways to split the SET of stars."
The Problem
You have \(n\) identical objects and \(k\) distinct bins. How many ways can you distribute the objects?
This shows up constantly. Distribute \(5\) apples among \(3\) children. Count integer solutions to \(x_1 + x_2 + x_3 = 10\) with each \(x_i \geq 0\). Determine how many ways to place \(8\) identical coins into \(4\) labeled jars. Every one of these is the same problem wearing a different outfit.
The key word is identical. If the objects were distinct, you'd assign each one independently — \(k^n\) total ways. But when the objects are interchangeable, only the group sizes matter, not which specific object lands where. That constraint collapses the count dramatically.
The Visual
Line up \(n\) stars in a row. Now insert \(k - 1\) bars among them to divide the row into \(k\) groups. Each group corresponds to one bin, and the number of stars in that group is the count assigned to that bin.
Take \(n = 6\) stars and \(k = 3\) bins. One arrangement:
This reads as \((2, 1, 3)\) — bin 1 gets \(2\), bin 2 gets \(1\), bin 3 gets \(3\).
Another arrangement:
This reads as \((0, 6, 0)\) — everything goes to bin 2.
And one more:
This reads as \((3, 0, 3)\) — bars can sit next to each other, creating empty bins.
Every distinct placement of \(k - 1\) bars among the stars gives a different distribution. The problem reduces to: how many ways can you place the bars?
Non-negative Constraint
The standard version: find the number of solutions to
Think of it as a row of \(n\) stars and \(k - 1\) bars — that's \(n + k - 1\) symbols total. You need to choose which \(k - 1\) positions (out of \(n + k - 1\)) are bars. The rest are stars.
Answer:
Proof. You have \(n + k - 1\) positions. Choose \(k - 1\) of them for bars. The remaining \(n\) positions are stars. Each choice uniquely determines a distribution \((x_1, x_2, \ldots, x_k)\) where \(x_i\) is the number of stars between bar \(i - 1\) and bar \(i\) (with imaginary bars at the endpoints). Conversely, every valid distribution maps to exactly one bar placement. It's a bijection between distributions and \((k-1)\)-element subsets of \([n + k - 1]\).
Equivalently, you can choose the \(n\) star positions instead of the \(k - 1\) bar positions: \(\binom{n+k-1}{n}\). Same number — it's the symmetry of binomial coefficients.
Positive Constraint
Now require each bin to get at least one object:
This only has solutions when \(n \geq k\) (you can't give each of \(k\) bins at least one object from fewer than \(k\) objects).
The standard trick: substitute \(y_i = x_i - 1\), so \(y_i \geq 0\). The equation becomes:
This is the non-negative version with \(n - k\) objects and \(k\) bins.
Answer:
There's a cleaner way to see this directly. If every bin must be non-empty, no two bars can be adjacent and no bar can sit at the endpoints. You're placing \(k - 1\) bars into the \(n - 1\) gaps between consecutive stars. Choose \(k - 1\) gaps from \(n - 1\): that's \(\binom{n-1}{k-1}\).
Worked Examples
Example 1: Apples to Children
Distribute \(5\) identical apples among \(3\) children (each child can get zero).
This is \(n = 5\), \(k = 3\), non-negative constraint.
To verify, enumerate a few: \((5,0,0), (4,1,0), (4,0,1), (3,2,0), (3,1,1), (3,0,2), \ldots\) There are exactly \(21\).
Example 2: Apples to Children, Each Gets at Least One
Same setup, but each child must get at least \(1\) apple.
This is \(n = 5\), \(k = 3\), positive constraint. Since \(5 \geq 3\):
The \(6\) distributions: \((1,1,3), (1,3,1), (3,1,1), (1,2,2), (2,1,2), (2,2,1)\).
Example 3: Integer Solutions
How many non-negative integer solutions does \(x_1 + x_2 + x_3 + x_4 = 10\) have?
Stars and bars with \(n = 10\), \(k = 4\):
Upper Bound Constraints (Preview)
What if each variable has an upper bound? For instance, \(x_1 + x_2 + x_3 = 10\) with \(0 \leq x_i \leq 5\).
Stars and bars alone gives \(\binom{12}{2} = 66\) without the upper bound. But some of those solutions violate \(x_i \leq 5\) — for example, \((10, 0, 0)\).
The fix is inclusion-exclusion. Let \(A_i\) be the set of solutions where \(x_i > 5\) (equivalently, \(x_i \geq 6\)). Substitute \(x_i' = x_i - 6\) to count \(|A_i|\) using stars and bars on the reduced total. Then subtract \(|A_1| + |A_2| + |A_3|\), add back \(|A_1 \cap A_2| + \ldots\), and so on.
This technique gets a full treatment in Chapter 6 (Inclusion-Exclusion). For now, recognize the pattern: stars and bars handles the base count, and inclusion-exclusion corrects for upper bounds.
Common Patterns
Stars and bars appears in disguise across many problem types. Once you recognize the structure, the solution is immediate.
Counting sequences with digit constraints. How many \(k\)-digit sequences have digits summing to \(n\)? If digits are non-negative integers with no upper bound, it's stars and bars. With upper bounds (digits \(0\)-\(9\)), layer on inclusion-exclusion.
Distributing coins. Place \(n\) identical coins into \(k\) labeled boxes — direct stars and bars.
Multiset selection. Choose \(n\) items from \(k\) types (with repetition allowed, order doesn't matter). Each "type" is a bin, each "item chosen" is a star. The answer is \(\binom{n+k-1}{k-1}\).
Counting paths on a grid. The number of lattice paths from \((0, 0)\) to \((a, b)\) using only right and up steps is \(\binom{a+b}{a}\). This is stars and bars: \(a\) right-steps and \(b\) up-steps form a sequence of \(a + b\) symbols where you choose \(a\) positions for right-steps.
The Code
Both functions rely on the nCr function with precomputed factorials and modular inverses from Ch5 L2. Make sure precomputeFactorials has been called with a large enough limit before using these.
long long starsAndBars(int totalObjects, int totalBins, long long mod) {
return nCr(totalObjects + totalBins - 1, totalBins - 1, mod);
}
long long starsAndBarsPositive(int totalObjects, int totalBins, long long mod) {
if (totalObjects < totalBins) return 0;
return nCr(totalObjects - 1, totalBins - 1, mod);
}
\(O(1)\) per call (after \(O(n)\) precomputation of factorials from Ch5 L2).
The functions are thin wrappers — the real work is in nCr. That's the point. Stars and bars is a reduction technique, not an algorithm. You recognize the structure, map it to a binomial coefficient, and compute.
For problems with upper bound constraints, you'll combine this with inclusion-exclusion:
long long starsAndBarsWithUpperBounds(int totalObjects, int totalBins,
vector<int>& upperBounds, long long mod) {
long long totalWays = 0;
for (int mask = 0; mask < (1 << totalBins); mask++) {
int reducedTotal = totalObjects;
int bitsSet = 0;
for (int bin = 0; bin < totalBins; bin++) {
if (mask & (1 << bin)) {
reducedTotal -= (upperBounds[bin] + 1);
bitsSet++;
}
}
if (reducedTotal < 0) continue;
long long ways = nCr(reducedTotal + totalBins - 1, totalBins - 1, mod);
if (bitsSet % 2 == 0) {
totalWays = (totalWays + ways) % mod;
} else {
totalWays = (totalWays - ways + mod) % mod;
}
}
return totalWays;
}
\(O(2^k \cdot 1)\) per call — exponential in \(k\), but \(k\) is typically small (under \(20\)) in problems that use this approach. When \(k\) is large and all upper bounds are equal, closed-form simplifications exist.
Common Mistakes
-
Swapping the two formulas. Non-negative uses \(\binom{n+k-1}{k-1}\), positive uses \(\binom{n-1}{k-1}\). Mixing them up is the most frequent error. Trace a small case (\(n = 3, k = 2\)) to confirm which formula you need.
-
Forgetting the \(n < k\) edge case. When every bin must get at least one and \(n < k\), the answer is \(0\), not a negative binomial coefficient. Always guard against this —
nCrwith a negative top argument gives garbage. -
Identical bins vs. distinct bins. Stars and bars counts distributions into distinct (labeled) bins. If the bins are identical (unlabeled), you need integer partitions instead — a completely different problem. The question "distribute apples among children" has distinct bins (each child is different). The question "split \(n\) into \(k\) parts" has identical bins.
Quick Recap
- Stars and bars converts "distribute \(n\) identical objects into \(k\) distinct bins" into a binomial coefficient.
- Non-negative (\(x_i \geq 0\)): \(\binom{n+k-1}{k-1}\) — choose positions for \(k - 1\) bars among \(n + k - 1\) symbols.
- Positive (\(x_i \geq 1\)): \(\binom{n-1}{k-1}\) — place bars in the \(n - 1\) gaps between stars.
- Upper bounds (\(x_i \leq c_i\)): combine stars and bars with inclusion-exclusion.
- The technique reduces to
nCr— use precomputed factorials from Ch5 L2.
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CSES — Distributing Apples | cses.fi/problemset/task/1716 | Easy | Direct stars and bars with non-negative constraint |
| SPOJ — MARBLES | spoj.com/problems/MARBLES | Easy | Stars and bars with positive constraint; choosing marbles from colors |
| LC 1641 — Count Sorted Vowel Strings | leetcode.com/problems/count-sorted-vowel-strings | Easy | Multiset selection = stars and bars with \(k = 5\) vowel types |
| CC — SANDWICH | codechef.com/problems/SANDWICH | Hard | Cut a sandwich of length \(N\) into pieces of size \(1\) to \(K\). The reduction: \(\lceil N/K \rceil\) pieces must each "give back" some length — distributing the excess is stars and bars. The nCr computation then requires Lucas + CRT for composite moduli (Ch5 L2) |