Combinations With Repetition

Count the number of ways to choose k items from n distinct types when repetition is allowed and order does not matter. Includes the stars-and-bars picture, the equivalence with non-negative integer solutions to a linear equation, and the substitution trick for lower-bound constraints.

Step 1 of 157%

Tutorial

Combinations With Repetition

A combination with repetition (also called a multiset selection) is a way to choose kk items from nn distinct types when each type may be picked any number of times and the order in which the items are chosen does not matter.

The number of such selections is

(n+k−1k)=(n+k−1)!k! (n−1)!.\binom{n+k-1}{k} = \dfrac{(n+k-1)!}{k!\,(n-1)!}.

For example, suppose we want k=3k=3 scoops of ice cream from n=2n=2 flavors (vanilla VV and chocolate CC), where flavors may repeat. The formula gives

(2+3−13)=(43)=4.\binom{2+3-1}{3} = \binom{4}{3} = 4.

The four selections are

VVV,VVC,VCC,CCC.VVV,\quad VVC,\quad VCC,\quad CCC.

Ordinary combinations (nk)\binom{n}{k} require all chosen items to be distinct. Combinations with repetition allow repeats, so they count strictly more selections whenever k≥2.k \geq 2.

↑ ↓ navigate · Enter open · Esc close · ⌘K/Ctrl K toggle