1
The selection is a count per type
Choosing 5 doughnuts from 3 kinds is choosing how many of each: a solution of x₁ + x₂ + x₃ = 5 in non-negative integers.
Lesson · Combinatorics and Counting · Repetition
Combinations with Repetition
Choosing r items from n types with repetition allowed and order irrelevant. The count is C(n+r−1, r), and the reason is a bijection with arrangements of stars and bars.
unordered, repetition allowed: C(n + r − 1, r)
equivalently x₁ + x₂ + … + xₙ = r with xᵢ ≥ 0
stars = the r items, bars = the n−1 dividers between types
with xᵢ ≥ 1 instead: C(r − 1, n − 1)
The fourth rule
Core ideas
What this lesson establishes
The last of the four counting rules, and the only one whose formula is not obvious from the statement.
2
Stars and bars encodes that solution
Write r stars and n − 1 bars; the bars split the stars into n groups. Every arrangement is a selection and conversely.
3
Positivity shifts the problem
Requiring each xᵢ ≥ 1 is the same problem with r − n items to distribute freely, so the count is C(r−1, n−1).
The material
Stars and bars
The bijection, the formula, and the variants.
Theorem · Combinations with repetition
The number of ways to choose r items from n types, with repetition allowed and order irrelevant, is C(n + r − 1, r).
Encode a selection as a row of r stars and n − 1 bars: the stars before the first bar are the items of type 1, those between the first and second bar are type 2, and so on. Empty groups are allowed and represent types not chosen.
This is a bijection. Every selection gives exactly one such row, and every row of r stars and n − 1 bars gives exactly one selection.
A row is an arrangement of r + n − 1 symbols of which r are stars, so there are C(n + r − 1, r) of them.
□
Example · Doughnuts
Five doughnuts from three kinds: C(3 + 5 − 1, 5) = C(7,5) = 21. The selection "two glazed, none jam, three chocolate" is the row ** | | ***.
The picture is worth keeping. n types need n − 1 bars, not n, because the bars go between the groups. Using n bars is the standard error and gives C(n+r, r).
Theorem · Non-negative integer solutions
The number of solutions of x₁ + ⋯ + x_n = r in non-negative integers is C(n + r − 1, r) — the same count, since a solution is exactly a selection.
Theorem · Positive integer solutions
The number of solutions with every xᵢ ≥ 1 is C(r − 1, n − 1).
Give each variable 1 up front, leaving r − n units to distribute freely among n variables. That is the non-negative problem with r − n in place of r, so the count is C(n + (r−n) − 1, r−n) = C(r−1, r−n), which equals C(r−1, n−1) by symmetry.
□
The substitution trick generalises. A constraint xᵢ ≥ c is handled by pre-assigning c units to that variable and solving the reduced problem; an upper bound xᵢ ≤ c is harder and needs the inclusion and exclusion of “The Inclusion-Exclusion Principle”.
The four rules, together
order matters order does not
repetition forbidden P(n, r) C(n, r)
repetition allowed nʳ C(n + r − 1, r)
Every basic counting problem in this course is one of these four. The arithmetic differs by orders of magnitude — at n = 5, r = 3 the four give 60, 10, 125 and 35 — so classifying correctly matters far more than computing carefully.
Interactive
The four counting rules
Enumerated while enumeration is possible
Method
Recognising a stars-and-bars problem
Look for identical items distributed among distinct types.
1
Check the items are interchangeable
Five identical doughnuts, r indistinguishable units. If the items are distinct, this is not the right formula.
2
Check the types are distinct
Three named kinds, n labelled boxes. Identical boxes give a much harder problem that this course does not cover.
3
Translate to an equation
x₁ + ⋯ + x_n = r with the constraints stated. This form makes the substitutions visible.
4
Handle lower bounds by substitution
xᵢ ≥ c becomes yᵢ = xᵢ − c ≥ 0 with the total reduced by c. Upper bounds need “The Inclusion-Exclusion Principle”.
Stars and bars
Score 0 / 0Choose the answer you can justify.
A bounded distribution
Solutions of x₁ + x₂ + x₃ = 12 with xᵢ ≥ 2 for each i.
Substitute yᵢ = xᵢ − 2, so each yᵢ ≥ 0 and
y₁ + y₂ + y₃ = 12 − 6 = 6
Non-negative solutions: C(3 + 6 − 1, 6) = C(8, 6) = 28
Check the extremes:
y = (6,0,0) ⟹ x = (8,2,2) ✓ all ≥ 2
y = (2,2,2) ⟹ x = (4,4,4) ✓
Without the constraint: C(3 + 12 − 1, 12) = C(14,12) = 91
Lower bounds are free: pre-assign and shrink the total. Upper bounds are not — counting the solutions with xᵢ ≤ 5 requires subtracting the violating cases and adding back the double violations, which is exactly “The Inclusion-Exclusion Principle”.
Common mistakes
1
Using n bars instead of n − 1The bars separate the groups, so there is one fewer of them than there are types. The picture makes it obvious; the formula does not.
2
Applying it to distinguishable itemsStars and bars needs the items interchangeable. Distributing distinct objects into boxes is the multinomial count of “Permutations with Repetition”.
3
Trying to handle an upper bound by substitutionLower bounds shift cleanly; upper bounds require subtracting the violations, which is inclusion and exclusion.
Check your understanding
✓
Finish when you can translate between the three phrasings.
Take "how many ways to put 8 identical balls into 4 labelled boxes", restate it as an equation and as a stars-and-bars diagram, and compute. All three descriptions are the same problem, and recognising that is the point.
Note: The complementary problem — identical balls into identical boxes — is counted by partition numbers, which have no closed form and grow subexponentially. Labelling the boxes is what makes this lesson's problem tractable.