Stars and bars: counting distributions of identical objects
The stars and bars theorem is a classic counting tool for problems where you distribute
indistinguishable objects among distinguishable bins. A typical question is:
“In how many ways can we distribute \(n\) identical cookies among \(k\) different kids?”
If you let \(x_i\) be the number of cookies given to kid \(i\), then every distribution corresponds to an integer solution
of the equation
\[
x_1+x_2+\cdots+x_k = n.
\]
The answer depends on whether empty bins are allowed.
Non-negative solutions: empty bins allowed
If each \(x_i\ge 0\), the theorem says the number of solutions is
\[
\binom{n+k-1}{k-1}.
\]
The “stars and bars” picture explains why. Represent the \(n\) identical objects as \(n\) stars in a row. To split them into
\(k\) bins, you insert \(k-1\) vertical dividers (bars) somewhere among the stars, including possibly at the ends or with multiple
bars adjacent (which corresponds to zero objects in a bin). Altogether there are \(n+(k-1)\) symbols, and choosing which
\(k-1\) positions are bars uniquely determines the distribution. That is exactly the binomial coefficient \(\binom{n+k-1}{k-1}\).
Positive solutions: no empty bins
If you require \(x_i\ge 1\), then every bin must receive at least one object, so there are no solutions unless \(n\ge k\).
A convenient method is the substitution \(y_i=x_i-1\). Then \(y_i\ge 0\) and
\[
(y_1+1)+\cdots+(y_k+1)=n \quad\Longrightarrow\quad y_1+\cdots+y_k = n-k.
\]
Now it becomes a non-negative stars-and-bars problem with \(n-k\) stars and \(k-1\) bars, giving
\[
\binom{(n-k)+k-1}{k-1}=\binom{n-1}{k-1}.
\]
In other words, “positive” distributions are counted by the same theorem after removing one guaranteed object from each bin.
What this calculator shows
This tool computes the appropriate binomial coefficient and shows step-by-step reasoning: the equation model, the number of stars
and bars, and the final combination \(\binom{N}{K}\). It also draws a schematic stars-and-bars layout and a bar chart of one sample
distribution \((x_1,\dots,x_k)\). The visualization is not used to compute the answer; it exists to connect the formula to a concrete
picture and to highlight how each gap between bars corresponds to a bin count.
University extension: upper limits and constraints
Stars and bars works cleanly for “\(\ge 0\)” or “\(\ge 1\)” constraints, but real problems often include upper limits such as
\(x_i\le u_i\). Those cases typically require inclusion–exclusion or generating functions,
because you must subtract distributions that exceed the limits. Seeing the unrestricted count first is still valuable:
it provides a baseline and helps you understand which constraints actually change the count and why.
