Combinations with Repetition
The Big Question
How many ways can you choose $k$ items from $n$ types when you're allowed to pick the same type more than once and the order doesn't matter?
Formal Definition
A combination with repetition (also called a multiset coefficient) counts the number of ways to choose $k$ elements from a set of $n$ types where:
- Repetition IS allowed — you can select the same item multiple times
- Order does NOT matter — selecting {A, A, B} is the same as {A, B, A}
The formula is:
$$\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1} = \frac{(n + k - 1)!}{k!\,(n - 1)!}$$
where $n$ = number of types available, $k$ = number of items to choose.
Comparison Table
| Order Matters | Order Doesn't Matter | |
|---|---|---|
| No Repetition | Permutation $P(n,k) = \frac{n!}{(n-k)!}$ | Combination $\binom{n}{k}$ |
| With Repetition | $n^k$ | $\binom{n+k-1}{k}$ ← We are here! |