Combinations with Repetition

How many ways can you choose 3 scoops of ice cream from 5 flavors? Repeating a flavor is allowed. This question is subtly different from ordinary Combinations. The objects being selected are no longer required to be distinct. It matters because many real counting problems fit this pattern. Examples include distributing identical candies to children. Another is choosing exponents in a monomial. Filling a shopping cart with repeatable items is another. These are not about picking distinct objects. Instead, they involve picking a multiset of objects from a fixed set of types. The big picture is simple. Once we allow repetition, the counting problem transforms. It becomes an equivalent problem of placing dividers among a row of markers. This bijection is so clean and so widely reused that it has its own name: stars and bars. This article gives the precise definition of a combination with repetition. It builds the stars-and-bars bijection carefully. It proves the resulting formula rigorously. It also works through nontrivial numerical examples. We also isolate exactly which hypothesis is doing the work. Two things matter: finiteness of the number of types, and genuinely unlimited repetition. We show what breaks when that assumption is dropped. Combinations with repetition sit inside a larger classification scheme for counting problems. This scheme is The Twelvefold Way. It organizes every basic counting problem by two features. One is whether the domain and codomain elements are distinguishable. The other is whether the map is required to be injective, surjective, or unrestricted. The stars-and-bars technique developed here has another use. It also gives the standard formula for counting the number of ways to write an integer as an ordered sum. This is a stepping stone toward a harder theory. That theory is the order-independent study of Integer Partitions.

Key takeaways
  • A combination with repetition is an unordered selection from a set where each element may be chosen more than once — formally, a multiset.
  • The number of size-rr multisets from an nn-element set is (n+r−1r)\binom{n+r-1}{r}, read "n plus r minus 1 choose r."
  • The proof is a bijection ("stars and bars") between multisets and binary strings of stars and bars, reducing the count to ordinary Combinations.
  • The formula requires n≥1n \ge 1 finite types and unlimited repetition of each type; dropping either hypothesis breaks the count.
  • The same integer (n+r−1r)\binom{n+r-1}{r} counts nonnegative integer solutions to x1+⋯+xn=rx_1+\cdots+x_n=r, linking combinatorics to Diophantine counting.
  • Key idea: unordered selection with repetition from nn types corresponds exactly to placing rr stars among n−1n-1 bars, turning a hard counting problem into ordinary binomial counting.

Where this lives today

Combinations with repetition are the combinatorial backbone of counting monomials: the number of degree-rr monomials in nn variables (needed when expanding (x1+⋯+xn)r(x_1+\cdots+x_n)^r via the multinomial theorem, or when counting basis elements of a graded polynomial ring in algebraic geometry) is exactly (n+r−1r)\binom{n+r-1}{r}. In statistics and machine learning, occupancy-style counting arises when distributing indistinguishable draws among categories, such as counting possible histograms with fixed total sample size in categorical/multinomial models. In computer science, the formula counts the number of ways to specify a multiset data structure of fixed size drawn from a fixed alphabet, relevant to hashing schemes and combinatorial generation algorithms (e.g., enumerating all such multisets in lexicographic order for exhaustive search). In cryptography and coding theory, weak compositions (nonnegative integer solutions to x1+⋯+xn=rx_1+\cdots+x_n=r) governed by this same formula appear when counting error patterns or symbol-weight distributions. In statistical mechanics, the Bose–Einstein counting of indistinguishable particles among energy levels is literally the stars-and-bars count, distinguishing it from Fermi–Dirac statistics (which forbids repetition, i.e., ordinary combinations) and Maxwell–Boltzmann statistics (which treats particles as distinguishable, i.e., counts sequences). This trichotomy is one motivating thread of The Twelvefold Way, and the unordered-sum viewpoint developed here is the natural on-ramp to the more intricate, order-independent theory of Integer Partitions.

Ask the tutor: Can you show me how the shift-substitution trick handles an upper-bound constraint like x1≤5x_1 \le 5, using inclusion–exclusion together with this formula?

DefinitionCombination with repetition

Let SS be a set with ∣S∣=n|S| = n finite types, and let r≥0r \ge 0 be an integer. A combination with repetition of size rr from SS (also called an rr-combination of a multiset over SS, or simply a multiset of size rr drawn from SS) is a function

m:S→Z≥0,∑s∈Sm(s)=r,m : S \to \mathbb{Z}_{\ge 0}, \qquad \sum_{s \in S} m(s) = r,

where m(s)m(s) records how many times element ss is selected. Two such selections are considered the same combination with repetition if and only if they have the same multiplicity function mm; in particular, order of selection is irrelevant and no upper bound is placed on any m(s)m(s) other than m(s)≤rm(s) \le r. Equivalently, writing S={a1,…,an}S = \{a_1, \dots, a_n\}, a combination with repetition of size rr is an unordered list

ai1,ai2,…,air,1≤i1≤i2≤⋯≤ir≤n,a_{i_1}, a_{i_2}, \dots, a_{i_r}, \qquad 1 \le i_1 \le i_2 \le \cdots \le i_r \le n,

i.e. a weakly increasing sequence of rr indices from {1,…,n}\{1,\dots,n\}.

Intuition

Ordinary combinations forbid repeats: choosing 3 people from a committee of 5 gives (53)\binom{5}{3} possibilities, and no person can be counted twice. Combinations with repetition remove that restriction. If you are filling a bag with 3 pieces of fruit chosen from apple, banana, cherry, mango, kiwi (5 types), then "apple, apple, banana" is a perfectly legal bag distinct from "apple, banana, banana." The object being counted is really a vector of nonnegative integers (m1,…,mn)(m_1, \dots, m_n) recording how many of each type you took, subject only to the total summing to rr. The key trick for counting these vectors is to encode each one as a string of symbols. Picture rr identical stars ⋆\star representing the rr items chosen, and imagine partitioning them into nn groups (one group per type) using n−1n-1 bars ∣|. The number of stars before the first bar is m1m_1, between the first and second bar is m2m_2, and so on. This turns an abstract multiset-counting problem into the very concrete problem of arranging a string of rr stars and n−1n-1 bars, which is a standard binomial-coefficient count.

Figure
Stars and bars: choosing 3 scoops from 5 flavors, e.g. (2,0,1,0,0)
Encoding $m=(2,0,1,0,0)$ as a stars-and-bars string flavors: V C S M P ★ ★ | (none) | ★ | (none) | (none) string: ★ ★ | | ★ | |   (2 stars, 4 bars, length 3+5-1=7)

Notice the string above has exactly r=3r = 3 stars (total scoops) and n−1=4n-1 = 4 bars (separating 5 flavor groups), for a total length of n+r−1=7n+r-1 = 7 symbols. Any such string determines a unique multiplicity vector, and any multiplicity vector determines a unique string: this is precisely the bijection the theorem below makes rigorous.

TheoremStars and bars formula for combinations with repetition

Let n≥1n \ge 1 and r≥0r \ge 0 be integers. The number of combinations with repetition of size rr chosen from a set of nn distinct types — equivalently, the number of functions m:{1,…,n}→Z≥0m : \{1,\dots,n\} \to \mathbb{Z}_{\ge 0} with ∑i=1nm(i)=r\sum_{i=1}^n m(i) = r — equals

(n+r−1r)=(n+r−1n−1).\binom{n+r-1}{r} = \binom{n+r-1}{n-1}.
Proof

We exhibit an explicit bijection Φ\Phi (proof technique: bijective proof) between the set

Mn,r={(m1,…,mn)∈Z≥0n:∑i=1nmi=r}M_{n,r} = \left\{ (m_1,\dots,m_n) \in \mathbb{Z}_{\ge 0}^n : \sum_{i=1}^n m_i = r \right\}

and the set Bn,rB_{n,r} of binary strings of length n+r−1n+r-1 containing exactly rr copies of the symbol ⋆\star (star) and n−1n-1 copies of the symbol ∣| (bar).

Construction of Φ\Phi. Given (m1,…,mn)∈Mn,r(m_1,\dots,m_n) \in M_{n,r}, define the string

Φ(m1,…,mn)=⋆⋯⋆⏟m1 ∣ ⋆⋯⋆⏟m2 ∣ ⋯ ∣ ⋆⋯⋆⏟mn.\Phi(m_1,\dots,m_n) = \underbrace{\star\cdots\star}_{m_1}\,|\,\underbrace{\star\cdots\star}_{m_2}\,|\,\cdots\,|\,\underbrace{\star\cdots\star}_{m_n}.

This string has n−1n-1 bars, one placed after each block except the last, and its total number of stars is ∑i=1nmi=r\sum_{i=1}^n m_i = r by hypothesis. Hence the string has length r+(n−1)=n+r−1r + (n-1) = n+r-1 and lies in Bn,rB_{n,r}, so Φ\Phi is well defined as a map Mn,r→Bn,rM_{n,r} \to B_{n,r}.

Φ\Phi is injective. Suppose (m1,…,mn)≠(m1′,…,mn′)(m_1,\dots,m_n) \ne (m_1',\dots,m_n') are two distinct elements of Mn,rM_{n,r}. Let jj be the smallest index with mj≠mj′m_j \ne m_j'; WLOG mj<mj′m_j < m_j'. In Φ(m1,…,mn)\Phi(m_1,\dots,m_n), reading left to right, the bar that terminates block jj (the jj-th bar) is preceded by exactly m1+⋯+mjm_1+\cdots+m_j stars since the start of the string, while in Φ(m1′,…,mn′)\Phi(m_1',\dots,m_n') the jj-th bar is preceded by m1+⋯+mj−1+mj′m_1+\cdots+m_{j-1}+m_j' stars (using mi=mi′m_i=m_i' for i<ji<j). Since mj≠mj′m_j \ne m_j', these counts differ, so the jj-th bar occupies a different position in the two strings. Hence Φ(m1,…,mn)≠Φ(m1′,…,mn′)\Phi(m_1,\dots,m_n) \ne \Phi(m_1',\dots,m_n'), proving injectivity.

Φ\Phi is surjective. Let w∈Bn,rw \in B_{n,r} be any string of rr stars and n−1n-1 bars. The n−1n-1 bars divide ww into exactly nn maximal runs of consecutive stars, read left to right (a run may be empty, e.g. two adjacent bars, or a bar at the very start or end, produces an empty run). Formally: let p1<p2<⋯<pn−1p_1 < p_2 < \cdots < p_{n-1} be the positions of the bars in ww; set p0=0p_0 = 0 and pn=n+r−1+1=n+rp_n = n+r-1+1 = n+r; define mim_i to be the number of star-symbols strictly between position pi−1p_{i-1} and position pip_i, for i=1,…,ni=1,\dots,n (with the convention that positions are 1,…,n+r−11,\dots,n+r-1 and p0=0,pn=n+rp_0=0, p_n = n+r are sentinels). Each mi≥0m_i \ge 0, and since every symbol of ww is either one of the n−1n-1 bars or one of the rr stars, and the stars are exactly partitioned among the nn runs, we get ∑i=1nmi=r\sum_{i=1}^n m_i = r. Thus (m1,…,mn)∈Mn,r(m_1,\dots,m_n) \in M_{n,r}, and by construction Φ(m1,…,mn)=w\Phi(m_1,\dots,m_n) = w. This proves surjectivity. Since Φ:Mn,r→Bn,r\Phi : M_{n,r} \to B_{n,r} is a bijection, ∣Mn,r∣=∣Bn,r∣|M_{n,r}| = |B_{n,r}|.

Counting Bn,rB_{n,r}. A string in Bn,rB_{n,r} is determined uniquely by choosing which rr of its n+r−1n+r-1 positions hold a star (the remaining n−1−n-1- positions automatically hold bars). By the definition of the binomial coefficient as the number of rr-element subsets of an (n+r−1)(n+r-1)-element set, Combinations gives

∣Bn,r∣=(n+r−1r).|B_{n,r}| = \binom{n+r-1}{r}.

Combining the two displayed equalities, ∣Mn,r∣=(n+r−1r)|M_{n,r}| = \binom{n+r-1}{r}. Since Mn,rM_{n,r} is exactly the set of multiplicity vectors of size-rr combinations with repetition from an nn-element set (as in the definition above), the theorem is proved. Finally (n+r−1r)=(n+r−1n−1)\binom{n+r-1}{r} = \binom{n+r-1}{n-1} by the symmetry identity for binomial coefficients, (Nk)=(NN−k)\binom{N}{k} = \binom{N}{N-k} with N=n+r−1N = n+r-1, k=rk=r. ■\blacksquare

∎
CorollaryRecurrence form

For n≥1n \ge 1, r≥1r \ge 1, the number C(n,r):=(n+r−1r)C(n,r) := \binom{n+r-1}{r} of size-rr combinations with repetition from nn types satisfies

C(n,r)=C(n−1,r)+C(n,r−1),C(1,r)=1,C(n,0)=1.C(n,r) = C(n-1,r) + C(n,r-1), \qquad C(1,r) = 1, \qquad C(n,0)=1.

This follows immediately from Pascal's rule (Nr)=(N−1r)+(N−1r−1)\binom{N}{r} = \binom{N-1}{r} + \binom{N-1}{r-1} applied with N=n+r−1N = n+r-1, since C(n−1,r)=(n+r−2r)C(n-1,r) = \binom{n+r-2}{r} and C(n,r−1)=(n+r−2r−1)C(n,r-1) = \binom{n+r-2}{r-1}, and (n+r−2r)+(n+r−2r−1)=(n+r−1r)\binom{n+r-2}{r} + \binom{n+r-2}{r-1} = \binom{n+r-1}{r} by Pascal's identity, part of Binomial Coefficient Identities.

Worked examples

Example 1: A snack order with an odd number of types. A vending kiosk sells n=7n = 7 distinct snack items. A customer buys a bag of r=4r = 4 snacks, and may repeat items (e.g. 2 bags of chips and 2 candy bars). How many distinct bags are possible? By the theorem, the count is

(n+r−1r)=(7+4−14)=(104).\binom{n+r-1}{r} = \binom{7+4-1}{4} = \binom{10}{4}.

Compute (104)=10⋅9⋅8⋅74!=504024=210\binom{10}{4} = \dfrac{10 \cdot 9 \cdot 8 \cdot 7}{4!} = \dfrac{5040}{24} = 210. So there are exactly 210210 distinct snack bags. Sanity check via the recurrence in the corollary: C(7,4)=C(6,4)+C(7,3)C(7,4) = C(6,4) + C(7,3). We can compute C(6,4)=(94)=126C(6,4) = \binom{9}{4} = 126 and C(7,3)=(93)=84C(7,3) = \binom{9}{3} = 84; indeed 126+84=210126 + 84 = 210, matching. This double computation confirms the arithmetic is self-consistent.

Example 2: Integer solutions with a shifted lower bound. Find the number of integer solutions to

x1+x2+x3+x4+x5=23,x1≥2, x2≥0, x3≥1, x4≥0, x5≥3.x_1 + x_2 + x_3 + x_4 + x_5 = 23, \qquad x_1 \ge 2,\ x_2 \ge 0,\ x_3 \ge 1,\ x_4 \ge 0,\ x_5 \ge 3.

This is a disguised combinations-with-repetition problem: substitute y1=x1−2≥0y_1 = x_1 - 2 \ge 0, y2=x2≥0y_2 = x_2 \ge 0, y3=x3−1≥0y_3 = x_3 - 1 \ge 0, y4=x4≥0y_4 = x_4 \ge 0, y5=x5−3≥0y_5 = x_5 - 3 \ge 0. The equation becomes

y1+y2+y3+y4+y5=23−2−0−1−0−3=17,y_1+y_2+y_3+y_4+y_5 = 23 - 2 - 0 - 1 - 0 - 3 = 17,

a sum of 55 nonnegative integers equal to 1717. By the theorem (with n=5n=5 "slots," r=17r=17 "units"), the number of nonnegative solutions (y1,…,y5)(y_1,\dots,y_5) — which biject exactly with the multiplicity vectors M5,17M_{5,17} constructed in the proof — is

(5+17−117)=(2117)=(214).\binom{5+17-1}{17} = \binom{21}{17} = \binom{21}{4}.

Compute (214)=21⋅20⋅19⋅1824=14364024=5985\binom{21}{4} = \dfrac{21\cdot 20\cdot 19\cdot 18}{24} = \dfrac{143640}{24} = 5985. Since the substitution yi=xi−ciy_i = x_i - c_i is a bijection between solutions in xx's and solutions in yy's (it is invertible, xi=yi+cix_i = y_i + c_i), the original system also has exactly 59855985 integer solutions.

CounterexampleWhy "unlimited repetition" (no upper bound per type) is needed

The theorem assumes each type may be repeated with no cap other than the total rr. Drop this and let each type be usable at most once more than once is disallowed beyond a fixed cap — concretely, suppose n=3n=3 types but each type may be selected at most 1 time (so effectively repetition is banned), while we still ask for size-r=2r=2 selections. The stars-and-bars count would claim (3+2−12)=(42)=6\binom{3+2-1}{2} = \binom{4}{2} = 6 selections. But with the cap mi≤1m_i \le 1 enforced, the only valid multiplicity vectors summing to 22 with each entry in {0,1}\{0,1\} are (1,1,0),(1,0,1),(0,1,1)(1,1,0), (1,0,1), (0,1,1) — exactly 33, not 66. The bijection Φ\Phi in the proof is still injective and its image still consists of valid star-bar strings, but three of the six strings — such as ⋆⋆∣∣\star\star|| , corresponding to m=(2,0,0)m=(2,0,0) — decode to multiplicity vectors that violate the cap mi≤1m_i \le 1 and are therefore not legitimate elements of the capped counting problem. Surjectivity onto the capped set fails: the formula (n+r−1r)\binom{n+r-1}{r} overcounts whenever an artificial upper bound on multiplicities is imposed. (Counting selections with individual caps requires inclusion–exclusion or generating functions, a strictly harder problem than the uncapped case handled here.)

Scope, edge cases & common traps

SituationCorrect formula / remark
r=0r = 0Exactly 11 combination (the empty selection); (n−10)=1\binom{n-1}{0}=1 for any n≥1n\ge1, consistent.
n=1n = 1Exactly 11 combination for every rr (must pick the single type rr times); (rr)=1\binom{r}{r}=1.
Order matters, repetition allowedUse nrn^r (sequences), not (n+r−1r)\binom{n+r-1}{r}.
Order irrelevant, repetition forbiddenUse ordinary (nr)\binom{n}{r}, requires r≤nr \le n.
Per-type upper bounds imposedFormula overcounts; needs inclusion–exclusion (see counterexample).
n=0n = 0, r>0r > 0No types available, 00 selections; formula's derivation assumed n≥1n\ge1 and should not be applied.

The mathematician behind it

Origins · 1 minWilliam Feller and how this was discovered
WF
William Feller
1906–1970 · Probability theory and combinatorial enumeration, mid-20th century

William Feller was a Croatian-American mathematician whose towering two-volume text An Introduction to Probability Theory and Its Applications popularized the phrase "stars and bars" for this counting technique and placed combinations-with-repetition squarely within the toolkit of discrete probability. Feller's broader legacy lies in making rigorous, combinatorially-grounded probability accessible to generations of scientists — the stars-and-bars device appears there as a workhorse for counting occupancy problems (balls into boxes) that recur constantly in statistical mechanics and queueing theory.

History
- 1636 — Marin Mersenne and contemporaries study combinatorial counts of musical note arrangements, an early precursor to multiset enumeration.
- 1713 — Jacob Bernoulli's posthumously published Ars Conjectandi systematizes combinations and permutations, the direct ancestor of the "without repetition" case.
- 1866 — Eugène Catalan and contemporaries formalize composition-counting (ordered sums), a close cousin of the stars-and-bars count.
- 1950 — William Feller's probability text disseminates the "stars and bars" name and technique to a broad mathematical and scientific audience.
- 1979 — Richard Stanley's Enumerative Combinatorics situates combinations with repetition inside the unifying framework later popularized as the Twelvefold Way.
How is a combination with repetition different from an ordinary combination?

An ordinary combination selects rr distinct objects from nn available objects, so no object can appear more than once and r≤nr \le n is required for the count to be nonzero. A combination with repetition instead allows any object to be chosen zero, one, or many times, up to the total budget of rr selections, and there is no requirement that r≤nr \le n. Formally, ordinary combinations count rr-element subsets of an nn-set, giving (nr)\binom{n}{r}, while combinations with repetition count size-rr multisets drawn from an nn-element universe, giving (n+r−1r)\binom{n+r-1}{r}. The repetition version is always at least as large as the non-repetition version whenever both are defined for the same n,rn, r.

Why is the formula (n+r−1r)\binom{n+r-1}{r} and not something simpler like nr/r!n^r/r!?

It might seem tempting to "remove order" from the nrn^r ordered sequences by dividing by r!r!, but this overcorrects: sequences with repeated entries have fewer than r!r! distinct orderings, so dividing every sequence's count by the same r!r! undercounts multisets that contain repeats and would not even give an integer in general. The correct approach abandons sequences entirely and instead encodes each multiset directly as a stars-and-bars string, which is inherently unordered by construction. This is why the rigorous bijective proof, rather than a naive counting shortcut, is essential here.

Does the stars-and-bars formula require r≤nr \le n?

No, and this is one of its most important contrasts with ordinary combinations. Since types can repeat, you can select rr items even when rr far exceeds nn; for instance, choosing 100100 scoops of ice cream from 33 flavors is perfectly sensible, with count (3+100−1100)=(102100)=(1022)=5151\binom{3+100-1}{100} = \binom{102}{100} = \binom{102}{2} = 5151. Ordinary combinations (nr)\binom{n}{r} vanish once r>nr>n because you cannot pick more distinct objects than exist, but multisets face no such obstruction since repetition supplies the extra volume.

How does this relate to counting integer solutions of linear equations?

Every combination with repetition of size rr from nn types corresponds exactly to a nonnegative integer solution (m1,…,mn)(m_1,\dots,m_n) of m1+⋯+mn=rm_1+\cdots+m_n = r, as shown in the proof's set Mn,rM_{n,r}. So "count the multisets" and "count the nonnegative integer solutions to a sum-equals-rr equation" are literally the same problem, just described in different vocabulary. This translation is extremely useful: problems phrased as inequalities like xi≥cix_i \ge c_i can be shifted by substitution into the standard nonnegative form and then solved directly with (n+r−1r)\binom{n+r-1}{r}, as illustrated in Worked Example 2.

What happens at the boundary cases r=0r=0 or n=1n=1?

Both boundary cases are consistent with the formula and worth checking by hand. When r=0r=0, there is exactly one combination — choosing nothing — and (n+0−10)=(n−10)=1\binom{n+0-1}{0} = \binom{n-1}{0} = 1 for every n≥1n \ge 1, matching. When n=1n=1, there is only one type available, so the unique multiset of size rr is "take that one type rr times," and indeed (1+r−1r)=(rr)=1\binom{1+r-1}{r} = \binom{r}{r} = 1. These sanity checks are a good habit whenever applying the formula to a new problem.

Can this technique be extended to count multisets with a fixed number of distinct types actually used?

Yes, though it requires an extra layer of reasoning beyond the basic theorem. If you require that all nn types appear at least once (i.e., every mi≥1m_i \ge 1), first set yi=mi−1≥0y_i = m_i - 1 \ge 0 so that ∑yi=r−n\sum y_i = r - n, then apply the theorem to get ((r−n)+n−1r−n)=(r−1r−n)=(r−1n−1)\binom{(r-n)+n-1}{r-n} = \binom{r-1}{r-n} = \binom{r-1}{n-1}, valid when r≥nr \ge n. More refined questions — such as counting multisets using exactly kk distinct types out of nn — combine this shift trick with an additional choice of which kk types are used, i.e. (nk)(r−1k−1)\binom{n}{k}\binom{r-1}{k-1}.

How does this fit into the Twelvefold Way?

The Twelvefold Way classifies counting problems by three binary choices: whether the domain (the rr selections) is distinguishable, whether the codomain (the nn types) is distinguishable, and what property the assignment must satisfy (arbitrary, injective, or surjective). Combinations with repetition sit in the cell where selections are indistinguishable from each other, types are distinguishable, and the map is arbitrary (any type can serve any number of selections) — this cell's count is exactly (n+r−1r)\binom{n+r-1}{r}. Seeing this placement clarifies why ordinary combinations, permutations, and set partitions all sit as neighboring cells governed by the same organizing logic.

Before this

Where this leads