The Combination with Repetition Formula
Combinations with repetition count the number of ways to select r items from n distinct objects when the same item may be chosen more than once. The order of selection does not matter, which distinguishes this from permutations. The formula applies the factorial function to account for all valid groupings.
C'(n,r) = (r + n − 1)! ÷ (r! × (n − 1)!)
n— Total number of distinct objects availabler— Size of each sample or number of items to choose!— Factorial operator (e.g., 5! = 5 × 4 × 3 × 2 × 1)
How Repetition Changes Combinations
When repetition is not allowed, you face fewer possibilities because each object can only be used once. Allowing repetition dramatically increases the number of valid combinations. For example, choosing 5 digits from 0–9 with repetition yields 2,002 combinations, whereas without repetition you would get only 252.
This difference grows rapidly as the sample size increases relative to the number of objects. Repetition is especially relevant when:
- Sampling with replacement from a population
- Creating passwords or codes where characters recur
- Selecting identical items from multiple stocks
- Designing experimental treatments with repeated factors
Worked Example: Five-Digit Combinations
Suppose you want to find all possible combinations of 5 digits selected from 0–9 with repetition allowed:
- Identify n and r: n = 10 (digits 0 through 9), r = 5 (selecting 5 digits)
- Apply the formula: C'(10,5) = (5 + 10 − 1)! ÷ (5! × (10 − 1)!)
- Simplify: 14! ÷ (5! × 9!) = 87,178,291,200 ÷ (120 × 362,880) = 87,178,291,200 ÷ 43,545,600 = 2,002
The answer is 2,002 unique combinations. Note that permutations with repetition for the same scenario would yield 100,000 because order matters in permutations.
Common Pitfalls and Practical Considerations
Pay attention to these key distinctions and computational issues when working with combinations that allow repetition.
- Confusing combinations and permutations — Combinations ignore order (A, B, C is the same as B, A, C), while permutations treat them as different. Always clarify whether your problem requires order. Many lottery and selection problems use combinations, but password generation uses permutations.
- Forgetting the n − 1 adjustment — The formula uses (n − 1)! in the denominator, not n!. This adjustment accounts for the extra freedom that repetition provides. Omitting it or using n! instead will give an incorrect result.
- Handling large factorials — When n and r are large, factorials grow enormous (20! ≈ 2.4 trillion). Use a calculator or logarithms to avoid overflow. Many programming languages offer built-in factorial or combinatorial functions to sidestep manual computation.
- Distinguishing identical from distinct objects — This formula assumes all n objects are distinct. If some objects are identical, you need a different approach that accounts for indistinguishability. Check your problem context carefully.
Real-World Applications
Combinations with repetition appear across diverse fields:
- Quality control: Selecting product batches where the same batch may be checked multiple times
- Menu design: Counting ways to order n dishes with r selections, where you can order the same dish twice
- Genetics: Determining allele combinations in inheritance problems with repeated genotypes
- Inventory allocation: Distributing r identical items across n storage locations
- Lottery design: Planning prize structures when repeat wins are possible