Skip to main content

Stars and Bars, Distributions, and Integer Solutions

What This Concept Is​

Stars and bars is a bijective encoding for distribution problems. It counts the number of nonnegative integer solutions to

$$x_1 + x_2 + \cdots + x_k = n, \quad x_i \ge 0$$

by representing each unit as a star ($\star$) and each separator between variables as a bar ($|$). A solution is encoded as a string of $n$ stars and $k-1$ bars; the positions of the bars determine the group sizes. Any arrangement of $n$ stars and $k-1$ bars is a valid encoding, so the count is

$$\binom{n + k - 1}{k - 1} ;=; \binom{n + k - 1}{n}.$$

Positive variant. If the problem requires $x_i \ge 1$ (each variable strictly positive), substitute $y_i = x_i - 1 \ge 0$. The equation becomes $y_1 + \cdots + y_k = n - k$, giving

$$\binom{n - 1}{k - 1}.$$

Upper-bound variants. If some $x_i$ has an upper bound (e.g., $x_1 \le 3$), inclusion-exclusion is used to subtract the forbidden overflows: count all solutions, subtract those with $x_1 \ge 4$ (substitute $y_1 = x_1 - 4$), etc.

The beauty of stars and bars is that it converts "distribute identical units among distinguishable groups" -- an abstract question -- into a concrete object (a string of $\star$s and bars), whose count is a single binomial coefficient.

Bijection, not formula. The exactness matters: every distribution produces exactly one string, and every string produces exactly one distribution. There is no overcounting and no undercounting to repair. When a problem looks like stars and bars but has a subtle symmetry you have not yet removed, the string picture makes the symmetry easy to spot -- you can see directly whether two strings represent the same distribution.

Why It Matters Here​

Many "distribution" problems are really disguised integer-solution problems:

  • distribute $n$ identical balls into $k$ boxes
  • allocate $n$ hours across $k$ tasks
  • assign $n$ identical tokens, points, or resources to $k$ agents
  • count multisets of size $n$ drawn from $k$ types
  • count monomials of degree $n$ in $k$ variables

This is one of the cleanest examples of counting by bijection. If you can articulate "identical units going to distinguishable targets," stars and bars is almost always the right tool. It also prepares you for generating-function thinking in the next cluster: $\binom{n+k-1}{k-1}$ is exactly the coefficient of $x^n$ in $1/(1-x)^k$.

The formula is also your first encounter with a binomial coefficient that depends on both a "data" parameter ($n$) and a "container" parameter ($k$). Asymptotically, $\binom{n+k-1}{k-1}$ grows like $n^{k-1}/(k-1)!$ for fixed $k$, which is the standard polynomial growth rate you will see later in algorithm analyses that count "resource-limited configurations."

Concrete Examples​

Example 1: basic distribution. How many nonnegative integer solutions satisfy $x_1 + x_2 + x_3 = 7$?

Encode as $7$ stars and $2$ bars arranged in a row. Any arrangement is valid; there are $7 + 2 = 9$ symbols in total, and we choose which $2$ positions hold bars:

$$\binom{9}{2} = 36.$$

Example encoding: $\star\star | \star\star\star | \star\star$ corresponds to $(2, 3, 2)$. The bijection is exact.

Example 2: positive lower bound. Count nonnegative integer solutions to $x_1 + x_2 + x_3 + x_4 = 10$ with each $x_i \ge 2$.

Substitute $y_i = x_i - 2$, giving $y_1 + y_2 + y_3 + y_4 = 10 - 8 = 2$, with $y_i \ge 0$. By stars and bars:

$$\binom{2 + 3}{3} = \binom{5}{3} = 10.$$

Sanity-check: the only solutions are those where the excess $2$ is distributed among four slots -- exactly the partitions $(2,0,0,0), (1,1,0,0)$ and their orderings, which total $\binom{4}{1} + \binom{4}{2} = 4 + 6 = 10$. ✓

Example 3: with an upper bound (inclusion-exclusion). Count nonnegative integer solutions to $x_1 + x_2 + x_3 = 10$ with $x_1 \le 4$.

Total (no upper bound): $\binom{12}{2} = 66$. Forbidden set: $x_1 \ge 5$. Substitute $z_1 = x_1 - 5$, giving $z_1 + x_2 + x_3 = 5$ with $z_1 \ge 0$; count is $\binom{7}{2} = 21$. Answer: $66 - 21 = 45$.

Example 4: combinations with repetition. How many ways can one choose $5$ doughnuts from a shop offering $4$ flavors, if repeats are allowed and order does not matter?

This is asking for the number of size-$5$ multisets from a $4$-element set. Let $x_i$ = number of doughnuts of flavor $i$. Then $x_1 + x_2 + x_3 + x_4 = 5$ with $x_i \ge 0$. By stars and bars, $\binom{5 + 3}{3} = \binom{8}{3} = 56$.

In general, the number of size-$n$ multisets drawn from a $k$-element set is $\binom{n + k - 1}{k - 1}$. This is the "fourth cell" of the permutation/combination matrix from concept 2 (unordered, with repetition).

Common Confusion / Misconceptions​

  • Applying the formula to positive variables without substitution. If the problem requires $x_i \ge 1$, you must first subtract $1$ from each before using $\binom{n+k-1}{k-1}$. Forgetting this gives a strictly wrong count.
  • Using stars and bars on distinguishable objects. The method counts distributions of identical units. Distributing $n$ distinct balls into $k$ distinguishable boxes is the product rule: $k^n$. Do not confuse the two.
  • Distinguishable vs indistinguishable recipients. Stars and bars assumes distinguishable groups. If the recipients are also identical (e.g., splitting $n$ candies among unnamed children where only the multiset of group sizes matters), you instead count integer partitions -- a harder problem without a closed form.
  • Confusing "solutions to an equation" with "solutions to an inequality." $x_1 + \cdots + x_k \le n$ with $x_i \ge 0$ becomes an equality problem by adding a slack variable $x_{k+1}$; then $\binom{n+k}{k}$.
  • Off-by-one on bars. The count is $\binom{n + k - 1}{k - 1}$ because there are $k - 1$ separators between $k$ groups, not $k$. Writing $\binom{n+k}{k}$ (off by one) is the most common error on this page; sanity-check on $k = 2, n = 2$ (should be $3$, not $6$).

How To Use It​

Use stars and bars when:

  1. the objects being distributed are identical
  2. the recipients are distinguishable
  3. the outcome is equivalent to "how many of each type" (an integer count per recipient)

Procedure:

  1. translate the word problem into an equation $x_1 + \cdots + x_k = n$.
  2. identify lower bounds on each $x_i$ and substitute $y_i = x_i - L_i$ to reset to zero.
  3. recompute the new total $n' = n - \sum L_i$; if $n' < 0$, there are no solutions.
  4. decide whether upper bounds apply; if so, use inclusion-exclusion on the overflow events.
  5. compute $\binom{n' + k - 1}{k - 1}$.
  6. verify on a small instance by direct enumeration (e.g., check $n=2, k=2$ gives $\binom{3}{1} = 3$: $(0,2), (1,1), (2,0)$). ✓
  7. if the recipients are also identical, switch techniques -- you need partitions, not stars and bars.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: the number of ways to split input size $n$ across $k$ recursive subproblems (e.g., in multi-way merge planning) is a stars-and-bars count. Bin-packing and knapsack instance spaces size the same way.
  • Semester 3 data structures: multiset data structures (counting Bloom filters, count-min sketch) use stars-and-bars reasoning to size their state spaces.
  • Semester 4 databases: result-size estimation for GROUP BY on categorical attributes uses stars and bars to bound the number of distinct grouping outcomes.
  • Semester 5 OS: distributing $n$ identical memory pages across $k$ NUMA nodes, or $n$ I/O completions across $k$ queues, is stars and bars. Fairness analyses use the positive variant to enforce a minimum per queue.
  • Semester 6 distributed systems: replica-placement plans that distribute $n$ shards across $k$ racks with minimum-per-rack constraints solve a bounded stars-and-bars count.
  • Generating functions (next cluster): $\binom{n+k-1}{k-1}$ is $[x^n],(1-x)^{-k}$; the whole of cluster 3 reinterprets stars and bars as coefficient extraction.
  • Semester 2 algorithms (dynamic programming): counting the number of compositions of $n$ with parts in a fixed set is a bounded stars-and-bars variant computed in $O(n \cdot k)$ by the coin-change DP.
  • Machine learning / statistics: the size of the simplex of $k$-dimensional discrete probability distributions with integer granularity $n$ is $\binom{n+k-1}{k-1}$. This controls the state-space size in EM and discrete-latent models.

Check Yourself​

  1. Why does $x_1 + x_2 + x_3 = 7$ produce $7$ stars and $2$ bars? Why $k-1$ and not $k$?
  2. How do you handle the condition $x_i \ge 2$? Write the substitution explicitly.
  3. Why is this method a bijection rather than a formula trick? Describe the inverse map.
  4. How does stars and bars change when the recipients become indistinguishable?
  5. Translate "$x_1 + x_2 + x_3 \le 10$ with $x_i \ge 0$" into an equality problem and count it.
  6. How does the count change if you restrict $x_i \in {0, 1}$? Why does stars and bars fail, and what replaces it?
  7. For the identity $\binom{n+k-1}{k-1} = \binom{n+k-1}{n}$, give both the algebraic and combinatorial justifications.

Mini Drill or Application​

Solve and justify:

  1. $x_1 + x_2 + x_3 + x_4 = 10$ with $x_i \ge 0$.
  2. $x_1 + x_2 + x_3 + x_4 = 10$ with $x_i \ge 1$.
  3. Number of ways to distribute $12$ identical candies to $5$ children if each gets at least $2$.
  4. Number of degree-$4$ monomials in $3$ variables $x, y, z$ (e.g., $x^4, x^3y, x^2y^2, \ldots$). (Hint: $a + b + c = 4$.)
  5. Number of solutions to $x_1 + x_2 + x_3 = 10$ with $x_1 \le 3$ and $x_2 \le 4$ (inclusion-exclusion over two upper bounds).
  6. Number of ways to allocate $20$ identical tokens across $6$ distinguishable players with each player receiving at least $1$ and at most $5$ tokens.
  7. Given $n$ identical items and $k$ distinguishable bins, count the distributions in which bin $1$ has strictly more items than bin $2$. (Hint: set up a bijection with unrestricted distributions of $n - 1$ items.)

Read This Only If Stuck​