Skip to main content
AMC 12 focus

Stars and Bars

Counting the ways to split a quantity among distinct groups — a single picture that turns a hard counting problem into a simple binomial coefficient.

Stars and bars counts the number of solutions to x1+x2+⋯+xk=nx_1+x_2+\cdots+x_k = n in nonnegative integers. Picture nn identical stars in a row, and imagine inserting k−1k-1 bars among them to split the stars into kk groups (some possibly empty) — each arrangement of stars and bars corresponds to exactly one solution.

The two core formulas

Nonnegative integer solutions (xi≥0x_i \geq 0):

(n+k−1k−1)\binom{n+k-1}{k-1}

Positive integer solutions (xi≥1x_i \geq 1): first give each variable 1 “for free,” which uses up kk of the total, then distribute the rest with the nonnegative formula:

(n−1k−1)\binom{n-1}{k-1}

When there's an upper bound

If some variable also has an upper bound (say x1≤bx_1 \leq b), there's no clean closed form — instead, count all nonnegative solutions, then subtract the ones where x1≥b+1x_1 \geq b+1 (using the substitution x1′=x1−(b+1)x_1' = x_1-(b+1) to turn that into another stars-and-bars count), applying inclusion-exclusion if multiple variables have bounds.

Worked example

Problem: How many ways are there to distribute 10 identical candies among 4 children, if each child must get at least 1 candy?

Solution: This is the positive-solutions case with n=10,k=4n=10, k=4:

(10−14−1)=(93)=84\binom{10-1}{4-1} = \binom{9}{3} = 84

Practice problems

1.How many nonnegative integer solutions are there to x+y+z=6x+y+z=6?

2.How many ways can 15 identical books be distributed among 3 students so each gets at least 1?

3.How many nonnegative integer solutions are there to x+y=8x+y=8 with x≤5x \leq 5?

4.How many ways can 7 identical balls be placed into 3 distinct boxes, allowing empty boxes?

Permutations & CombinationsInclusion-Exclusion