Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Count Combinations with Repetition

When you pick several items from a few kinds and a kind may be picked again, a selection is fixed by how many of each kind you take. Write it as stars for the items and bars between the kinds, and count the ways to place the bars.

Recognize the task

You choose several items from a few kinds, a kind can be chosen more than once, and only how many of each kind matters: donuts from a shop, scoops of ice cream, identical coins into labeled boxes, whole-number solutions of x+y+z=7x + y + z = 7. Test: can the result be written as a count per kind?
This count is the weak composition (stars and bars) in the combinations lesson.

Two ways to do it

Stars and barsusual
(n+r−1r)=(n+r−1n−1)\binom{n + r - 1}{r} = \binom{n + r - 1}{n - 1}
rr stars for the items and n−1n - 1 bars between the kinds (weak composition).
At least one of each kindno empty kind
(r−1n−1)\binom{r - 1}{n - 1}
Give one of each kind first and choose the rest freely, or use the strong composition formula directly.

Steps

StepOn 4 donuts from 3 kinds
1Check that kinds repeat and order does not matter. Two glazed, one jam and one plain is one box, however you list it.unordered, repetition allowed
2Read the number of kinds and the number of picks. nn counts the kinds, rr counts the items you take.n=3n = 3 kinds, r=4r = 4 donuts
3Write each choice as stars and bars. Put rr stars in a row and split them into the kinds with n−1n - 1 bars: ⋆⋆∣⋆∣⋆\star\star \mid \star \mid \star means 2,1,12, 1, 1.44 stars, 22 bars, 66 symbols
4Choose the places of the stars. Every choice of places among the n+r−1n + r - 1 symbols gives exactly one box.(64)=(62)=15\binom{6}{4} = \binom{6}{2} = 15

Worked examples

Example 1 · ice cream scoops

basic
33 scoops from 55 flavors, repeats allowed
n=5n = 5, r=3r = 3
(5+3−13)=(73)\binom{5 + 3 - 1}{3} = \binom{7}{3}
stars and bars
3535 cups

Example 2 · whole-number solutions

equation
x+y+z+w=6x + y + z + w = 6, all ≥0\ge 0
66 units into 44 variables
(6+4−14−1)=(93)\binom{6 + 4 - 1}{4 - 1} = \binom{9}{3}
66 stars, 33 bars
8484 solutions

Example 3 · at least one of each

shift first
99 donuts from 44 kinds, each kind at least once
lower bound on every kind
give one of each: 55 left to choose
removes the lower bound
(5+4−15)=(85)\binom{5 + 4 - 1}{5} = \binom{8}{5}
free choice of the rest
5656 boxes
Move the stars and bars yourself in the weak composition tool; the at-least-one case is in the strong composition tool.

See it happen

A box of donuts is fixed by how many of each kind it holds, so line the donuts up by kind and draw a bar where one kind ends and the next begins. With 33 kinds you need 22 bars. Every box becomes a row of 44 stars and 22 bars, and every such row is a box. Counting the rows means choosing which 22 of the 66 places hold bars.

Common mistakes

Using plain combinations

✗ 44 donuts from 33 kinds: (34)=0\binom{3}{4} = 0
✓ kinds repeat: (3+4−14)=15\binom{3 + 4 - 1}{4} = 15

Using n to the r

✗ 44 donuts from 33 kinds: 34=813^4 = 81 boxes
✓ 8181 counts ordered picks; a box ignores order: 1515

Swapping kinds and items

✗ 33 scoops from 55 flavors: (3+5−15)=21\binom{3 + 5 - 1}{5} = 21
✓ n=5n = 5 flavors, r=3r = 3 scoops: (73)=35\binom{7}{3} = 35