35
1.54407
7
2
35
1.54407
7
2
Combinations with replacement, also called multiset coefficients or "stars and bars" problems, count the number of ways to choose r items from n types when order does not matter and repetition is allowed. This is the fourth and final fundamental counting model in combinatorics, alongside combinations without replacement, permutations without replacement, and permutations with replacement.
Real-world examples of combinations with replacement are surprisingly common. Choosing 3 scoops of ice cream from 5 flavors (you can pick the same flavor multiple times, and the order of scoops doesn't matter) is a multiset problem. Distributing 10 identical balls into 4 distinct boxes, selecting items from a menu where you can order multiples of the same dish, or determining the number of terms in a polynomial expansion all reduce to this formula.
The formula uses an elegant trick: selecting r items from n types with replacement is equivalent to choosing r items from a set of (n + r - 1) items without replacement. This is proved using the stars and bars method, where we represent each selection as a sequence of r stars (items chosen) and (n - 1) bars (dividers between types), giving C(n + r - 1, r) total arrangements.
Our Combination with Replacement Calculator computes this multiset coefficient using the same robust log-space approach as our standard combinations calculator, handling both small exact values and large approximations seamlessly. It also shows the equivalent "n" value used in the underlying binomial coefficient, making the mathematical transformation transparent.
The multiset coefficient formula is:
$$\left(\!\binom{n}{r}\!\right) = \binom{n+r-1}{r} = \frac{(n+r-1)!}{r!(n-1)!}$$
This is derived from the stars and bars theorem. We arrange r identical stars and (n-1) bars in a line. The stars represent items chosen, and the bars separate the n types. The total number of symbols is n + r - 1, and we choose r positions for stars (or equivalently n - 1 positions for bars).
For computation, we evaluate C(n+r-1, r) using Stirling's approximation for large values:
$$\ln\binom{m}{r} \approx m\ln m - m - r\ln r + r - (m-r)\ln(m-r) + (m-r) + \text{correction terms}$$
where m = n + r - 1.
The result counts the number of distinct multisets of size r from n types. Unlike standard combinations, duplicates are allowed. For example, with n=3 types {A, B, C} and r=2: the multisets are {A,A}, {A,B}, {A,C}, {B,B}, {B,C}, {C,C} — giving C(4,2) = 6. Note that r can exceed n (you can choose more items than types), unlike standard combinations without replacement.
Inputs
Results
35 distinct ways to pick 3 scoops from 5 flavors (repetition allowed). Computed as C(7,3) = 35.
Inputs
Results
286 ways to distribute 10 identical coins among 4 distinct boxes. Equivalent to C(13,10) = 286.
Stars and bars is a combinatorial technique for counting distributions. To choose r items from n types, arrange r stars (items) and n-1 bars (dividers) in a line. Each arrangement corresponds to one selection. The total arrangements are C(n+r-1, r).
Standard combinations C(n,r) require r ≤ n and each item is used at most once. Combinations with replacement allow repetition and r can exceed n. The formula changes from C(n,r) to C(n+r-1,r) to account for the repeated selections.
Yes. Since items can be reused, you can choose more items than types. Choosing 10 donuts from 3 flavors is perfectly valid: C(12, 10) = 66 combinations.
A multiset is a generalization of a set that allows repeated elements. The multiset {A, A, B} has three elements where A appears twice. The multiset coefficient counts the number of distinct multisets of a given size from a given number of types.
They appear in polynomial expansion (the number of terms of degree r in n variables), integer partition problems, occupancy problems in probability (distributing identical objects into distinct bins), and counting solutions to equations like x₁ + x₂ + ... + xₙ = r where xᵢ ≥ 0.
Without replacement: combinations = C(n,r), permutations = P(n,r). With replacement: combinations = C(n+r-1,r), permutations = nʳ. The 'order matters' distinction separates permutations from combinations, and the 'replacement' distinction determines whether items can repeat.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
