= Stars and bars
{disambiguate=combinatorics}
{wiki}
= Stars and bars
{synonym}
<Stars and bars> counts <tuples> of <nonnegative integers> with a prescribed <sum>. For <integers> $N\geq0$ and $k\geq1$, its statement is
$$
\#\{(x_1,\ldots,x_k):x_i\geq0,\ x_1+\cdots+x_k=N\}
=\binom{N+k-1}{k-1}.
$$
Such a <tuple> is a <weak composition of an integer>. Think of $k$ labelled bins: $x_1$ counts identical objects in the first bin, $x_2$ in the second, and so on. Bin names distinguish positions even when counts agree. <Stars and bars> counts these count <tuples>; assigning individually distinct objects requires additional information. https://math.mit.edu/~fgotti/docs/Courses/C.%20Combinatorial%20Analysis/6.%20Compositions/Compositions.pdf[Felix Gotti, MIT 18.211, Lecture 6: Compositions, Proposition 1 and Example 3]{ref}
\b[Computed example.] With $N=5$ and $k=3$, the number of <weak compositions of an integer> is $\binom72=21$. The string `••|•|••` encodes $(2,1,2)$: two dots before the first bar, one between the bars, and two after the second. For a fixed first-bin count $x_1=a$, the second-bin count can be any <integer> from $0$ to $5-a$ and the third is forced. Thus the direct count is $6+5+4+3+2+1=21$.
\Image[/stars-and-bars-three-bin-allocation.png]
{title=<Stars and bars> for five identical objects and three labelled bins: ordinary splits, adjacent bars, and bars at either end}
Adjacent bars encode an empty middle bin: `••||•••` gives $(2,0,3)$. A bar at the left end encodes an empty first bin, as in `|••|•••` for $(0,2,3)$; a bar at the right end encodes an empty third bin, as in `••|•••|` for $(2,3,0)$. These are valid <weak compositions of an integer>. For $N=0$ every count is zero, and for $k=1$ the unique <tuple> is $(N)$, consistent with $\binom{N}{0}=1$.
\b[Proof outline.] Replace each count $x_i$ by that many dots and separate successive groups with $k-1$ bars. Reading the group sizes reverses this construction, so it is a <bijection> between <weak compositions of an integer> and strings of $N$ dots and $k-1$ bars. Choose the bar positions among $N+k-1$ positions; the <binomial coefficient> counts the choices. The beauty is that empty bins need no separate cases: end bars and adjacent bars encode them automatically.
If every bin must be nonempty, the <tuples> are <compositions of an integer>, and their count is $\binom{N-1}{k-1}$ for $N\geq k\geq1$; for $N<k$ there are none. Subtract one from every count, setting $y_i=x_i-1$. This is a <bijection> to <weak compositions of an integer> of $N-k$, so <stars and bars> gives $\binom{(N-k)+k-1}{k-1}=\binom{N-1}{k-1}$. For five objects and three bins, this is $\binom42=6$, with the six positive <tuples>
$$
(3,1,1),\ (1,3,1),\ (1,1,3),\ (2,2,1),\ (2,1,2),\ (1,2,2).
$$
For instance, $(2,1,2)$ shifts to $(1,0,1)$, whose <sum> is $2=5-3$. Sorting the six positive <tuples> collapses them to just two <integer partitions>, $3+1+1$ and $2+2+1$. Thus named bins and unordered summands answer different questions.
<Stars and bars> is useful for allocating identical resources or enumerating <integer> solutions without listing them individually. Prescribed lower bounds can be subtracted just like the nonempty-bin requirement. Upper bounds require removing forbidden <tuples>; the existing <bounded weak compositions> article applies the <inclusion-exclusion principle> to those violations.
Back to article page
