Stars with dividers

When items are identical and only the counts per bin matter, arrangements collapse from permutations into weak compositions. Placing k identical stars in a row and choosing positions for n - 1 bars splits the row into n bins, so the count is C(k + n - 1, n - 1). Distributing 10 identical orders among 3 desks gives C(12, 2) = 66 allocations.

Words you need

Combinations (n choose k): The number of ways to pick k items from n when order does not matter.e.g. 5 choose 2 = 10.
Permutation: An ordering of items where order matters.

Why it works

Every allocation corresponds to exactly one placement of n - 1 bars among k + n - 1 slots, and every bar placement decodes to one allocation.

Ways = C(k + n - 1, n - 1) = C(k + n - 1, k)

Spot it: Items are indistinguishable and bins are distinguishable.

Technique reference and sources

Lay the identical items in a row as stars. Drop n - 1 dividers into the gaps and ends to carve the row into n labeled bins. Counting allocations is counting divider placements.

When this method fits

Items are indistinguishable and bins are distinguishable.
You need the number of nonnegative integer solutions to x1 + ... + xn = k.
An interviewer asks for distributions, vote splits, or identical-goods allocations.
You want the count of multisets of size k drawn from n types.

Identify k and n. Count identical items k and distinct bins n. Check that items really are interchangeable.
Build the top number. Top = k + n - 1, the total star plus bar slots.
Pick the bottom number. Bottom = n - 1 (bar positions), or symmetrically k (star positions). Use the smaller one for mental math.
Evaluate the binomial. Compute C(top, bottom) with cancel-first arithmetic: C(12, 2) = 12 * 11 / 2 = 6 * 11 = 66.

Identical orders among desks: Distributing k identical items among n distinct bins gives C(k + n - 1, n - 1).

10 orders, 3 desks: C(12, 2) = 66
6 stickers, 2 friends: C(7, 1) = 7
4 treats, 3 flavors: C(6, 2) = 15

Each bin nonempty: If every bin must receive at least one item, hand one item to each bin first, then distribute the remaining k - n freely: C(k - 1, n - 1). Requires k >= n.

7 balls, 3 boxes, each nonempty: C(6, 2) = 15
5 votes, 4 candidates, each at least one: C(4, 3) = 4

Common traps

Using permutations P(k + n - 1, n - 1) because the slots look ordered. Bar positions form a set, not a sequence. Choosing divider slots is a combination: C(k + n - 1, n - 1).

Forgetting the minus one and computing C(k + n, n - 1). k stars need only n - 1 bars, so total slots are k + n - 1. For 10 orders and 3 desks the top is 12, not 13.

Applying stars and bars when items are distinguishable. For k distinct items independently assigned to n labeled bins, there are n^k assignments. For specified bin counts, use the multinomial coefficient k!/(x1!...xn!). Stars and bars needs identical items; check interchangeability first.

Another example: 7 identical balls into 3 boxes, none empty

Give one ball to each box first: 7 - 3 = 4 balls remain
Distribute the remaining 4 freely among 3 boxes: top 4 + 3 - 1 = 6, bottom 2
C(6, 2) = 6 * 5 / 2 = 3 * 5 = 15

Source notes

These explanations and questions are written for QuantArc. Links show the underlying mathematics and learning design.

Harvard Stat 110: Probability (Joe Blitzstein)
Free course site with videos and the open companion book Introduction to Probability; the topic spine for counting, Bayes, and linearity. Lesson examples and questions are original.

MIT OCW 6.042J: Mathematics for Computer Science
Course page checked: undergraduate discrete mathematics covering permutations and combinations plus counting principles. Topic spine for stars and bars, lattice paths, and derangements. Lesson examples and questions are original.

IES: Organizing Instruction and Study to Improve Student Learning
Supports worked examples, retrieval, explanations and spaced study. Does not establish QuantArc's exact lesson length, mastery threshold or review intervals.