Stars and Bars for Integer Allocations

Why Stars and Bars Counts Allocations

When identical objects are assigned to named categories, an allocation is described by how many objects go to each category. If 11 identical training credits are assigned among four named skill areas, for example, the counts in the areas form a nonnegative integer solution to an equation. The objects are identical, but the categories are distinct: assigning six credits to Area A and five to Area B is a different allocation from assigning five to Area A and six to Area B.

Stars and bars turns each allocation into a simple arrangement. A star represents one object, and a bar separates one category from the next. The method is useful only when the categories are distinguishable and the objects being allocated are identical. If the objects themselves are distinct, counting allocations requires a different model.

Definition: For $N$ identical objects allocated among $k$ named categories, an allocation is represented by a vector of nonnegative integers $(x_1,\ldots,x_k)$ satisfying $x_1+\cdots+x_k=N$. The number of such allocations is the number of nonnegative integer solutions to that equation.

The Stars-and-Bars Formula

For $k$ categories, arrange $N$ stars in a row and insert $k-1$ bars to divide them into $k$ groups. The first group gives $x_1$, the next gives $x_2$, and so on through $x_k$. A group can be empty: adjacent bars, or a bar at an end, represent a category receiving zero objects.

Theorem: If $N$ is a nonnegative integer and $k$ is a positive integer, the number of nonnegative integer solutions to $x_1+\cdots+x_k=N$ is $$ \binom{N+k-1}{k-1}=\binom{N+k-1}{N}. $$

The total arrangement contains $N$ stars and $k-1$ bars, or $N+k-1$ positions. Choosing which $k-1$ positions contain bars determines the arrangement and therefore the allocation. This gives the binomial coefficient in the formula.

Represent the objects.
Write $N$ stars, one for each identical object.

Separate the categories.
Insert $k-1$ bars to create $k$ groups, allowing empty groups.

Choose the bar positions.
Choose $k-1$ positions from the $N+k-1$ total positions.

This argument is a one-to-one correspondence: each allocation gives exactly one stars-and-bars arrangement, and every such arrangement recovers exactly one allocation. For example, with five stars and three categories, the arrangement $*\,|\,**\,|\,**$ represents $(1,2,2)$, while $|\,***\,|\,**$ represents $(0,3,2)$.

Worked Example: Credits Assigned Across Five Skill Areas

A training program has 13 identical credits to assign among five named skill areas. A skill area may receive no credits. How many different allocation vectors are possible?

Method. Let $x_j$ be the number of credits assigned to skill area $j$, for $j=1,\ldots,5$. The credits are identical, the areas are distinct, and the only restriction is that all 13 credits are assigned. Thus the model is $$ x_1+x_2+x_3+x_4+x_5=13,\qquad x_j\geq 0\text{ and integer}. $$

There are $N=13$ stars and $k=5$ categories, so the number of allocations is $$ \binom{13+5-1}{5-1}=\binom{17}{4} =\frac{17\cdot16\cdot15\cdot14}{4\cdot3\cdot2\cdot1} =\frac{57120}{24}=2380. $$

Check. Each counted arrangement has exactly 13 stars and four bars, so it assigns all 13 credits to exactly five categories. Empty groups are allowed, as required. The answer is 2,380 allocations. The method avoids treating different arrangements of identical credits as distinct outcomes.

Positive Allocations and Minimum Requirements

The basic formula allows a category to receive zero. If every category must receive at least one object, subtract one from each category first. More generally, if category $j$ must receive at least $m_j$ objects, where each $m_j$ is a nonnegative integer, define $y_j=x_j-m_j$. Then $y_j\geq0$, and the equation has a reduced total.

Theorem: The number of integer solutions to $x_1+\cdots+x_k=N$ subject to $x_j\geq m_j$ for every $j$ is $$ \binom{N-\sum_{j=1}^k m_j+k-1}{k-1} $$ if $N-\sum_{j=1}^k m_j\geq0$. If $N-\sum_{j=1}^k m_j<0$, there are no solutions.

To justify the shift, write $y_j=x_j-m_j$. Then $x_j=y_j+m_j$, so $$ y_1+\cdots+y_k=N-\sum_{j=1}^k m_j. $$ The $y_j$ are nonnegative integers, so the stars-and-bars formula applies to the remaining total. If the remaining total is negative, the minimum requirements already demand more objects than are available.

Worked Example: Depot Minimums for Emergency Kits

A response team has nine identical emergency kits for four named depots. Depot A must receive at least two kits, and each of Depots B, C, and D must receive at least one. How many allocations meet these requirements?

Method. Let $x_A,x_B,x_C,x_D$ be the kit counts. The constraints are $$ x_A+x_B+x_C+x_D=9,\qquad x_A\geq2,\quad x_B,x_C,x_D\geq1. $$

First reserve the required minimums: two kits for A and one for each of the other three depots. This uses $2+1+1+1=5$ kits, leaving $9-5=4$. Define $y_A=x_A-2$, $y_B=x_B-1$, $y_C=x_C-1$, and $y_D=x_D-1$. These variables are nonnegative integers and satisfy $$ y_A+y_B+y_C+y_D=4. $$

There are four categories, so stars and bars gives $$ \binom{4+4-1}{4-1}=\binom{7}{3} =\frac{7\cdot6\cdot5}{3\cdot2\cdot1}=35. $$

Check. Every counted allocation first assigns the required five kits, then distributes the remaining four. The minimums are met, and all nine kits are accounted for. The answer is 35 allocations. The method avoids subtracting the same minimum from every depot when Depot A has a different requirement.

Worked Example: Different Minimums Across Five Regions

A hypothetical program allocates 18 identical service vouchers among five named regions. Region 1 must receive at least three vouchers, Region 2 at least two, Region 3 at least one, and Region 5 at least two. Region 4 has no minimum. How many allocations are possible?

Method. Let $x_1,\ldots,x_5$ be the voucher counts. The model is $$ x_1+x_2+x_3+x_4+x_5=18, $$ with minimums $3,2,1,0,2$, respectively. Their sum is $3+2+1+0+2=8$, so $18-8=10$ vouchers remain after meeting all minimums.

Set $y_1=x_1-3$, $y_2=x_2-2$, $y_3=x_3-1$, $y_4=x_4$, and $y_5=x_5-2$. The transformed equation is $$ y_1+y_2+y_3+y_4+y_5=10,\qquad y_j\geq0. $$

There are five categories and a remaining total of 10, giving $$ \binom{10+5-1}{5-1}=\binom{14}{4} =\frac{14\cdot13\cdot12\cdot11}{4\cdot3\cdot2\cdot1} =\frac{24024}{24}=1001. $$

Check. Adding the reserved minimums to any solution for the $y_j$ gives a valid original allocation, and subtracting them recovers that solution uniquely. The answer is 1,001 allocations. The method avoids overlooking the two-voucher minimum for Region 5.

Common Mistakes and Limits of the Formula

The most frequent error is using the wrong number of separators. With $k$ categories, there are $k-1$ bars, not $k$. Therefore the total number of positions is $N+k-1$, not $N+k$.

For example, for 13 objects in five categories, a wrong calculation might use $\binom{18}{5}$, as if there were five bars among 18 positions. That counts arrangements with five bars and therefore creates six groups. The correct arrangement has 13 stars and four bars, giving $\binom{17}{4}=2380$.

Another common error is to use the nonnegative formula without shifting when every category must be positive. For $N$ objects in $k$ categories with each category positive, set $y_j=x_j-1$. The residual total is $N-k$, so when $N\geq k$, the count is $$ \binom{N-k+k-1}{k-1}=\binom{N-1}{k-1}. $$ When $N<k$, there are no allocations satisfying the positive requirement. Upper bounds, such as requiring a category to receive at most four objects, are not handled by this direct formula; they add restrictions beyond nonnegative lower bounds.

Key takeaway: First identify whether the objects are identical and the categories are named. Then write the integer equation, check whether zero is allowed in each category, shift by any required minimums, and apply $\binom{R+k-1}{k-1}$ to the remaining total $R$.

Check Your Understanding

For each problem, model the allocation before applying the formula.

Eight identical vouchers are assigned among three named departments, and a department may receive none. How many allocation vectors are possible? (Answer: 45)
Ten identical devices are assigned among four named sites, with at least one device at every site. How many allocations are possible? (Answer: 84)
Count the nonnegative integer solutions to $a+b+c+d=13$, subject to $a\geq2$, $b\geq0$, $c\geq3$, and $d\geq1$. (Answer: 120)
Twenty identical award points are divided among six named teams, with every team receiving a positive number. How many allocations are possible? (Answer: 11,628)
Four named regions receive 14 identical supply units. Region 1 must receive at least four, Region 2 at least two, Region 3 at least one, and Region 4 may receive zero. How many allocations satisfy these conditions? (Answer: 120)

What You'll Learn