Integer Solutions & Stars and Bars
How many ways are there to distribute $n$ identical candies among $r$ children? How many non-negative integer solutions does $x_1 + x_2 + \dots + x_r = n$ have? How many bouquets of size $n$ can you make from $r$ types of flowers when each type is unlimited? These problems all collapse into a single counting argument that Ross calls Theorem 6.1 of Chapter 1: stars and bars.
The Problem
Stars and bars (non-negative version). The number of distinct vectors $(x_1, x_2, \dots, x_r)$ where each $x_i$ is a non-negative integer and $x_1 + x_2 + \dots + x_r = n$ is
$\displaystyle \binom{n + r - 1}{r - 1} = \binom{n + r - 1}{n}.$
The two forms are equal by symmetry: $\binom{n+r-1}{r-1} = \binom{n+r-1}{(n+r-1)-(r-1)} = \binom{n+r-1}{n}$. Use whichever feels more natural for the problem.
Why It Works — The Stars-and-Bars Bijection
Picture $n$ identical stars in a row. We want to split them into $r$ groups, where the $i$-th group's size becomes $x_i$. To split $r$ groups we need $r - 1$ dividers. Place each divider somewhere among the stars (or at the ends, or between two adjacent dividers — empty groups are allowed because $x_i$ can be 0).
Concretely: write a sequence of $n$ stars and $r - 1$ bars. The total length is $n + r - 1$. Each such sequence determines a unique solution $(x_1, \dots, x_r)$: $x_i$ is the number of stars between the $(i-1)$-th and $i$-th bar (with bar 0 being the start and bar $r$ being the end). Conversely, every solution gives one sequence.
n = 5, r = 3, so 5 stars and 2 bars; total length 7.
★ ★ | ★ ★ ★ | => (2, 3, 0)
| ★ ★ ★ ★ ★ | => (0, 5, 0)
★ | | ★ ★ ★ ★ => (1, 0, 4)
| | ★ ★ ★ ★ ★ => (0, 0, 5)
Counting the sequences is easy: choose which $r - 1$ of the $n + r - 1$ positions are bars. The remaining positions are stars. That's exactly $\binom{n + r - 1}{r - 1}$. $\Box$
▶ Visual: Stars and Bars for $n = 5$, $r = 3$
Step through one bar placement to see how a sequence of 5 stars and 2 bars decodes to a solution of $x_1 + x_2 + x_3 = 5$.
Positive Integer Solutions
Stars and bars (positive version). The number of vectors $(x_1, x_2, \dots, x_r)$ where each $x_i$ is a positive integer and $x_1 + \dots + x_r = n$ (we need $n \ge r$) is
$\displaystyle \binom{n - 1}{r - 1}.$
Why. If every $x_i \ge 1$, we can pre-allocate one star to each group and then distribute the remaining $n - r$ stars freely among the $r$ groups (no minimum requirement on the leftovers). Substituting $y_i = x_i - 1$, the new problem is to count non-negative integer solutions of $y_1 + \dots + y_r = n - r$, which is $\binom{(n - r) + r - 1}{r - 1} = \binom{n - 1}{r - 1}.$ $\Box$
This variable-substitution trick $y_i = x_i - L_i$ converts any lower-bound constraint ($x_i \ge L_i$) into an unconstrained non-negative problem. It is a one-line tool you should never forget.
Worked Examples
Ross 1.6a — Investment portfolios
An investment of \$10{,}000 is to be made among 4 possible investments in increments of \$1{,}000. How many strategies are possible? How many if every investment receives at least \$1{,}000?
Let $x_i$ be the thousands invested in venture $i$, so $x_1 + x_2 + x_3 + x_4 = 10$.
- No minimum: non-negative solutions $= \binom{10 + 4 - 1}{4 - 1} = \binom{13}{3} = 286.$
- Each $x_i \ge 1$: positive solutions $= \binom{10 - 1}{4 - 1} = \binom{9}{3} = 84.$
Ross 1.6b — Counting integer solutions of an inequality
How many non-negative integer solutions does $x_1 + x_2 + x_3 + x_4 + x_5 \le 6$ have?
Introduce a slack variable $x_6 \ge 0$ so that $x_1 + \dots + x_5 + x_6 = 6$. Now count non-negative solutions of an equation: $\binom{6 + 6 - 1}{6 - 1} = \binom{11}{5} = 462.$
Worked: Multiset selection
How many ways are there to pick $n$ ice creams from $r$ flavours, with repetition allowed and order not mattering?
Let $x_i$ be the number of scoops of flavour $i$. Then $x_1 + \dots + x_r = n$ with $x_i \ge 0$, so the answer is $\binom{n + r - 1}{r - 1}$. This is sometimes written $\binom{r}{n}_{\text{multiset}}$ or $\left(\!\!\binom{r}{n}\!\!\right)$ in older texts.
Worked: Upper bounds via inclusion–exclusion
How many non-negative integer solutions does $x_1 + x_2 + x_3 = 12$ have, with each $x_i \le 6$?
Let $A_i$ be the set of solutions violating the bound on $x_i$ (i.e., $x_i \ge 7$). By inclusion–exclusion:
Total without bounds: $\binom{12 + 3 - 1}{3 - 1} = \binom{14}{2} = 91.$
$|A_i|$ — substitute $y_i = x_i - 7$: count non-negative solutions of $y_i + x_j + x_k = 5$, which is $\binom{5 + 3 - 1}{3 - 1} = \binom{7}{2} = 21$. There are 3 such $A_i$.
$|A_i \cap A_j|$ — both $x_i, x_j \ge 7$ means $y_i + y_j + x_k = 12 - 14 = -2$, impossible. So $|A_i \cap A_j| = 0$, and there are no triple intersections either.
Inclusion–exclusion: $91 - 3 \cdot 21 + 0 - 0 = 91 - 63 = 28.$
A Glimpse of Generating Functions
Stars and bars also drops out of the generating-function identity
$\dfrac{1}{(1 - x)^r} = \sum_{n=0}^{\infty} \binom{n + r - 1}{r - 1} x^n,$
which says: the coefficient of $x^n$ in $(1 - x)^{-r}$ is the number of ways to write $n$ as an ordered sum of $r$ non-negative integers. This is a special case of Newton's generalised binomial theorem we mentioned in Part 5. We'll meet generating functions in detail in a later series, but knowing they exist makes the formula feel less mysterious.
Computing Stars-and-Bars in Code
Once you have $\binom{n}{k}$ implemented (Part 4), stars-and-bars is one line away:
// Number of non-negative integer solutions of x_1 + ... + x_r = n.
long long star_bar_nonneg(int n, int r) {
return C(n + r - 1, r - 1);
}
// Number of strictly positive integer solutions of x_1 + ... + x_r = n.
long long star_bar_pos(int n, int r) {
if (n < r) return 0;
return C(n - 1, r - 1);
}
Common Mistakes
- Wrong formula direction. Remember: positive uses $n - 1$ and non-negative uses $n + r - 1$ on top. The non-negative version adds $r - 1$ extra slots; the positive version removes $r$ pre-allocated stars.
- Treating distinguishable items. Stars-and-bars is for identical items split into labelled groups. If items are distinct and groups are labelled, use multinomials (Part 6) or $r^n$ (basic counting).
- Ignoring upper bounds. Stars-and-bars by itself only enforces lower bounds (via substitution). Upper bounds need inclusion–exclusion on the “bad” events.
- Forgetting equality vs. inequality. $\le n$ becomes $= n$ after introducing one slack variable; do not skip that step.
Quick Recognition Table
| Problem shape | Tool |
|---|---|
| Distinct objects, ordered | $P(n, r)$ (Part 3) |
| Distinct objects, unordered | $\binom{n}{r}$ (Part 4) |
| Distinct objects into $k$ labelled groups of fixed sizes | $\binom{n}{n_1, \dots, n_k}$ (Part 6) |
| Identical objects into labelled groups, $x_i \ge 0$ | $\binom{n + r - 1}{r - 1}$ (this post) |
| Identical objects into labelled groups, $x_i \ge 1$ | $\binom{n - 1}{r - 1}$ (this post) |
| Bounds beyond simple positivity | Substitution + inclusion–exclusion |
Series Wrap-up
Across seven posts you have built every elementary counting tool from a single root: the multiplication rule. Permutations, combinations, the binomial theorem, multinomials, and stars-and-bars are all multiply, then maybe divide out a symmetry, then sometimes split into cases or subtract bad ones. Hold onto that mental hierarchy and almost every Ross Chapter 1 (and a fair chunk of Chapters 2–4) becomes mechanical.
Where to go next:
- Probability axioms (Ross Chapter 2). The classical definition $\Pr(E) = |E|/|S|$ is your reward for all this counting.
- Conditional probability (Ross Chapter 3). Bayes' theorem is built on the same combinatorics.
- Random variables and the binomial / multinomial / hypergeometric distributions (Ross Chapters 4–5). These distributions are your coefficients re-used as probabilities.
Practice Problems
- Ross 1.16. Determine the number of vectors $(x_1, \dots, x_n)$ such that each $x_i$ is a positive integer and $\sum_{i=1}^n x_i \le k$ where $k \ge n$.
- Ross 1.32. If 12 people are split into 3 committees of sizes 3, 4, and 5 respectively, how many ways are there?
- Ross 1.34. If 8 identical blackboards are to be divided among 4 schools so that each school receives at least one, how many ways are there?
- Practice — bounded. Count non-negative integer solutions of $x_1 + x_2 + x_3 + x_4 = 20$ with $x_i \le 8$ for all $i$.
- Practice — distributing books. 10 identical books are placed on 4 distinguishable shelves. How many ways if (a) any number per shelf, (b) at least one per shelf, (c) at most 4 per shelf?
- Practice — coin combinations. In how many ways can you pay \$1 using only nickels, dimes, and quarters? set up a linear equation and reduce
- LeetCode 518 — Coin Change II. Number of ways to make change — same flavour as stars-and-bars when coin values divide nicely; otherwise needs a generating-function DP.