Combinations with Repetition | Stars & Bars

Combinations with repetition, also called multiset coefficients or the stars and bars formula, count the number of ways to select r items from n distinct types when you can pick the same type more than once and the order of selection does not matter. The key insight is that this is equivalent to a completely different problem: arranging r identical stars and (n−1) identical bars in a row of n+r−1 positions.

• ›All four combinatorial variants in one view, C̄(n,r) with repetition, C(n,r) without, P(n,r) permutations, and nʳ, so you can compare directly.
• ›Stars & Bars visualization, sample arrangements show exactly how stars ★ and bars | correspond to real selections, making the abstract formula tangible.
• ›r can exceed n, unlike standard combinations, you can choose more items than there are types (e.g., 5 scoops from 3 flavors, all 5 could be the same flavor).
• ›Multiset listing, for small inputs, every multiset is enumerated and shown labelled A, B, C, … so you can verify the count by inspection.
• ›BigInt exact arithmetic, uses the efficient multiplicative formula, not full factorial computation, for accurate results at any scale.
• ›Step-by-step simplification, see how the (n−1)! factor cancels from the numerator, leaving just r terms to multiply and divide.

1. 1
   Identify n and r: n = the number of distinct item types (flavors, colors, categories). r = how many items you are choosing. Remember: r is allowed to be larger than n.
2. 2
   Enter values and calculate: Type n and r, then press Calculate or hit Enter. All four combinatorial values appear immediately for direct comparison.
3. 3
   Read the Stars & Bars visual: For small inputs (n ≤ 8, r ≤ 12), sample arrangements appear showing how stars (items) and bars (dividers) correspond to specific multiset distributions.
4. 4
   Expand for details: Click "Show Step-by-Step" to trace through the formula derivation. For C̄(n,r) ≤ 200, click "List All Multisets" to enumerate every possible selection.
5. 5
   Try presets: Use the preset buttons for classic real-world scenarios: ice cream scoops, dice outcomes, pizza toppings, coin distributions, and colored marble draws.

Most people encounter combinations through the standard formula C(n, r) = n!/(r!(n−r)!), where every item can be chosen at most once. But many real counting problems allow the same item to appear multiple times in a selection, the number of scoops at an ice cream parlor, the outcomes when rolling several dice, distributing identical objects into bins, or counting polynomial terms. These are all multiset problems, and they require the combinations-with-repetition formula.

The Stars and Bars Method, A Visual Proof

The formula C̄(n, r) = C(n+r−1, r) comes from a beautiful visual argument known as the Stars and Bars method, introduced by William Feller. Imagine you want to select r items from n types. Represent each chosen item as a star ★, and use n−1 vertical bars | to separate the n types. For example, with n=3 types and r=5 items:

Each unique selection corresponds to exactly one arrangement of r stars and n−1 bars in a row of n+r−1 positions. Choosing which r positions hold stars (the rest hold bars) gives us C(n+r−1, r) arrangements, the exact count of distinct multisets.

The Distributing Objects Problem

The formula C̄(n, r) also counts the number of non-negative integer solutions to: x₁ + x₂ + x₃ + … + xₙ = r, where each xᵢ represents how many of the r items go into bin i. This “distributing identical objects into distinct bins” framing appears in probability theory (occupancy problems), information theory (code words), and combinatorial optimization.

When to Use Which Formula

Real-World Applications

Generating Functions Connection

The generating function for C̄(n, r) is the coefficient of xʳ in the expansion of 1/(1−x)ⁿ = Σ C(n+r−1, r) xʳ. This connection to power series makes multiset coefficients central to analytic combinatorics and the study of integer partitions. When n=2, the formula gives C̄(2,r) = r+1, which matches the triangular arrangement in Pascal's triangle.

Comparison: With vs. Without Repetition

Notice that when r = n, C(n,n) = 1, only one way to choose all items without repetition. But C̄(n,n) can be enormous because each item can be repeated any number of times.