Combinations with Repetition - Discrete Math

SECTION 1

Historical Context & Motivation

The problem of counting selections from a collection of objects—where the same object may be chosen more than once—has roots stretching back centuries. Ancient Indian mathematicians encountered such questions in the context of prosody, where Pingala and later scholars studied the number of ways to arrange syllabic patterns of fixed total length drawn from a small alphabet. The essential question is deceptively simple: if you have n types of items and wish to select k items where repetitions are allowed and order does not matter, how many distinct selections exist?

This question arises naturally in resource allocation, distributing identical objects into labeled bins, and polynomial enumeration. Although the ordinary binomial coefficient C(n, k) counts selections without repetition, the multiset coefficient generalizes this idea by permitting each type to be chosen any number of times. Understanding the historical evolution of this concept reveals how combinatorics matured from ad hoc counting arguments into a rigorous algebraic framework.

c. 200 BCE • Indian Prosodic Counting

Pingala and subsequent scholars in the Sanskrit tradition enumerate metrical patterns, encountering problems equivalent to multiset selection when counting combinations of syllable types.

1713 • Ars Conjectandi

Jacob Bernoulli's posthumous masterwork systematizes combinatorial reasoning, presenting tables of binomial coefficients and laying groundwork for the stars-and-bars technique.

1756 • Euler's Partitions

Leonhard Euler develops generating function methods for integer partitions, providing an analytic lens through which multiset counting can be studied via formal power series.

1852 • Stars and Bars Formalized

The combinatorial identity now known as the 'stars and bars' argument is articulated clearly in the works of European mathematicians, giving a bijective proof of the multiset coefficient formula.

20th C. • Modern Enumerative Combinatorics

Richard Stanley and others embed multiset coefficients within the broader framework of generating functions, species theory, and algebraic combinatorics, connecting them to symmetric functions and representation theory.

The central gap that combinations with repetition address is this: classical combinations C(n, k) require that each element be selected at most once, which models sampling without replacement. But many real-world problems—choosing scoops of ice cream from n flavors, distributing k identical scholarships among n departments, or enumerating monomials of a given degree—demand a counting tool that allows repetition. The multiset coefficient provides exactly this.

SECTION 2

Core Principles & Definitions

Before diving into formulas, it is essential to anchor the concept in precise definitions. A multiset (sometimes called a bag) is a generalization of a set in which elements may appear more than once. The multiplicity of each element is recorded, but—crucially—the order of selection does not matter. When we speak of combinations with repetition, we are counting the number of distinct multisets of size k drawn from a universe of n types.

Selection with Replacement

Each of the n types can be chosen any number of times. There is no upper bound on how many times a single type appears in the multiset of size k.

Order Does Not Matter

Unlike permutations with repetition, swapping the sequence of selected items produces the same multiset. The selection {A, A, B} is identical to {A, B, A} and {B, A, A}.

Stars-and-Bars Bijection

Every multiset of size k from n types corresponds bijectively to a binary string of k stars and n − 1 bars, converting the problem into an ordinary combination.

Equivalent to Integer Solutions

Counting multisets is equivalent to counting the number of non-negative integer solutions to x₁ + x₂ + ⋯ + xₙ = k, where xᵢ records how many times type i is chosen.

✦

KEY TAKEAWAY

Think of combinations with repetition like placing an order at a bakery with n varieties of pastries. You want to buy k pastries total, and you may pick the same variety multiple times. You don't care about the order in which the clerk puts them in the box—you only care about how many of each variety you end up with. The stars-and-bars trick is like writing tally marks (stars) for each pastry, separated by dividers (bars) between varieties. The number of ways to arrange those tally marks and dividers gives you the answer.

SECTION 3

Visual Explanation — Stars and Bars

The stars-and-bars method provides a powerful visual and bijective approach to counting combinations with repetition. Suppose we want to choose k = 5 items from n = 3 types. We represent the chosen items as 5 stars (★) and separate the types using n − 1 = 2 bars (|). Each arrangement of these 7 symbols encodes a unique multiset. The diagram below illustrates several such arrangements and their corresponding multisets.

Five rows illustrate different ways to distribute k = 5 items among n = 3 types using stars (★) and bars (|). Each arrangement corresponds to a unique multiset, and the total count is C(7, 5) = 21.

Each row in the diagram above represents a single binary string of length k + n − 1 = 7, composed of exactly 5 stars and 2 bars. The stars to the left of the first bar indicate how many items of Type A are chosen; stars between the two bars count Type B; and stars to the right of the second bar count Type C. Because every such binary string yields a distinct multiset and vice versa, the problem reduces to choosing which k of the k + n − 1 positions will hold stars. This is the stars-and-bars bijection, and it converts a seemingly complex multiset-counting problem into an ordinary combination.

SECTION 4

Mathematical Framework

The stars-and-bars argument leads directly to a closed-form expression for the number of combinations with repetition. We formalize this via the multiset coefficient, which counts the number of multisets of cardinality k from a set of n types.

MULTISET COEFFICIENT

((n choose k)) = C(n + k − 1, k) = (n + k − 1)! / (k! · (n − 1)!)

n = number of distinct types available; k = number of items to select (with repetition allowed); n + k − 1 = total positions in the stars-and-bars string; the notation ((n choose k)) denotes the multiset coefficient, read as 'n multichoose k.'

To derive this, observe that each multiset of size k from n types corresponds to a non-negative integer solution of x₁ + x₂ + ⋯ + xₙ = k. We encode each solution as a binary string of k stars and n − 1 bars, yielding a string of total length k + n − 1. The number of such strings is C(k + n − 1, k), which equivalently equals C(k + n − 1, n − 1) by symmetry of the binomial coefficient.

EQUIVALENT FORMS

C(n + k − 1, k) = C(n + k − 1, n − 1)

Choosing which positions are stars is equivalent to choosing which positions are bars. Both expressions count the same set of multisets.

GENERATING FUNCTION

∑_{k=0}^{∞} ((n choose k)) x^k = 1 / (1 − x)^n

The ordinary generating function for the multiset coefficients with n types is the n-th power of the geometric series 1/(1 − x). Each factor (1 + x + x² + ⋯) corresponds to one type contributing 0, 1, 2, … copies.

ℹ

Connection to Negative Binomial Coefficients

The multiset coefficient is sometimes written using the negative binomial identity: C(n + k − 1, k) = (−1)^k C(−n, k). This identity connects multiset counting to the generalized binomial theorem and to the coefficients appearing in the Taylor expansion of (1 − x)⁻ⁿ.

SECTION 5

Taxonomy of Counting Problems

Combinations with repetition occupy one cell in a broader 2 × 2 taxonomy of counting problems defined by two binary choices: is order relevant, and is repetition allowed? Understanding where each counting formula lives in this taxonomy prevents one of the most common errors in combinatorics—applying the wrong formula. The diagram and table below classify the four fundamental counting paradigms and their formulas.

The 2 × 2 taxonomy of counting selections. The highlighted cell (bottom-right) corresponds to combinations with repetition, whose formula is C(n + k − 1, k).

Order?	Repetition?	Name	Formula	Example (n=5, k=3)
Yes	No	Permutation	P(n, k) = n!/(n−k)!	60
Yes	Yes	Perm. w/ Rep.	nᵏ	125
No	No	Combination	C(n, k) = n!/(k!(n−k)!)	10
No	Yes	Combination w/ Rep.	C(n+k−1, k)	35

The four fundamental counting formulas with computed values for n = 5, k = 3.

Notice that for a fixed n and k, the combination with repetition count (35) exceeds the ordinary combination count (10) because repetition expands the pool of available selections. Conversely, it is smaller than the permutation with repetition count (125) because ignoring order collapses many arrangements into a single multiset. Keeping this ordering of magnitudes in mind—C(n, k) ≤ C(n + k − 1, k) ≤ n^k—serves as a useful sanity check when solving problems.

SECTION 6

Worked Example

A coffee shop offers 4 varieties of muffin: blueberry, chocolate, cranberry, and lemon poppy seed. A customer wants to buy 6 muffins and may choose the same variety more than once. How many distinct selections are possible?

Selecting 6 Muffins from 4 Varieties

1
Step 1 — Identify the Counting Model

The customer cares only about how many of each variety they get, not the order in which the clerk bags them. Repetition is allowed (they may buy 6 blueberry if they wish). This matches the combination with repetition model with n = 4 types and k = 6 items.

n = 4, k = 6
2
Step 2 — Write the Stars-and-Bars Setup

We need a string of 6 stars (one per muffin selected) and n − 1 = 3 bars (to separate 4 varieties). The total string length is 6 + 3 = 9. For example, ★★|★★★||★ encodes {2 blueberry, 3 chocolate, 0 cranberry, 1 lemon poppy seed}.

String length = k + n − 1 = 9
3
Step 3 — Apply the Formula

The number of such strings is C(9, 6), since we choose 6 of the 9 positions for stars (or equivalently, 3 positions for bars). We compute:

C(9, 6) = C(9, 3)
4
Step 4 — Evaluate the Binomial Coefficient

C(9, 3) = 9! / (3! × 6!) = (9 × 8 × 7) / (3 × 2 × 1) = 504 / 6 = 84. Using the symmetry C(9, 6) = C(9, 3) simplifies the arithmetic, since 3 < 6.

84 distinct selections
5
Step 5 — Verify with a Sanity Check

As a sanity check, the ordinary combination C(4, 6) is undefined (you can't choose 6 distinct items from 4 without repetition), confirming that the classical combination formula does not apply here. Meanwhile, permutations with repetition would yield 4⁶ = 4096, which is much larger because it counts ordered sequences—far more than our unordered multisets. Our answer of 84 sits in a plausible range.

✓ Answer is reasonable: C(4, 6) undefined < 84 < 4⁶ = 4096

SECTION 7

Strengths, Limitations & Common Pitfalls

The multiset coefficient formula is elegant and powerful, but its correct application hinges on verifying that the problem's assumptions genuinely match the model. The table below summarizes the strengths of the formula alongside its inherent limitations and the most frequent student errors.

Strengths	Limitations / Pitfalls
Closed-form formula: C(n + k − 1, k) gives an exact count efficiently even for large n and k.	Assumes unlimited supply: if the number of copies of each type is bounded, a constrained version (inclusion–exclusion or generating functions) is required instead.
Bijective proof via stars-and-bars makes the formula intuitive and easy to remember.	Students often confuse n and k: n is the number of types (bins), not the total items selected.
Naturally extends to generating functions and polynomial coefficient extraction, unifying many counting problems.	Does not apply when items within a type are distinguishable—that scenario requires a different model (e.g., labeled distributions).
Equivalent to counting lattice paths and non-negative integer solutions, providing cross-topic connections.	Forgetting the '−1' in n − 1 bars is a common arithmetic error that produces an off-by-one mistake in the formula.

Strengths and common pitfalls of the multiset coefficient formula.

✦

DECISION CHECKLIST

Before applying C(n + k − 1, k), verify three conditions: (1) selections are unordered, (2) each type has unlimited availability, and (3) items of the same type are indistinguishable. If any condition fails, you need a different counting technique—permutations for ordered selections, inclusion–exclusion for bounded supplies, or labeled distributions for distinguishable items.

SECTION 8

Connections to Advanced Theory

The multiset coefficient is not an isolated formula; it is a gateway to several advanced topics in algebra and combinatorics. Understanding these connections deepens your mathematical fluency and equips you to tackle more complex enumeration problems. The table below contrasts the introductory version of the concept with its more advanced generalizations.

Introductory Concept	Advanced Generalization
C(n + k − 1, k) counts multisets of size k from n unlimited types.	Restricted compositions: when each type has a maximum count cᵢ, use inclusion–exclusion or the coefficient of xᵏ in ∏(1 + x + ⋯ + $x^{cᵢ}$ ).
Stars-and-bars encodes solutions to x₁ + ⋯ + xₙ = k with xᵢ ≥ 0.	For xᵢ ≥ aᵢ (positive lower bounds), substitute yᵢ = xᵢ − aᵢ to reduce to the standard form, then apply the multiset coefficient to the transformed equation.
Generating function 1/(1 − x)ⁿ enumerates multisets.	Pólya enumeration theory uses cycle index polynomials and Burnside's lemma to count multisets up to symmetry (e.g., necklaces of beads).
Multiset coefficient equals a single binomial coefficient.	The multinomial coefficient n!/(k₁!k₂!⋯kₘ!) generalizes to distributing distinguishable objects into groups, connecting to the multinomial theorem.

How combinations with repetition connect to more advanced counting techniques.

In abstract algebra, the multiset coefficient appears as the dimension of the space of homogeneous polynomials of degree k in n variables: each monomial x₁^a₁x₂^a₂⋯xₙ^aₙ with a₁ + a₂ + ⋯ + aₙ = k corresponds to a multiset of exponent choices. This perspective links combinatorics to commutative algebra, algebraic geometry (Hilbert functions), and representation theory (symmetric tensors). If you continue into graduate-level combinatorics, you will encounter the theory of symmetric functions, where the complete homogeneous symmetric polynomial hₖ is precisely the generating function for multisets.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why the number of combinations with repetition C(n + k − 1, k) is always at least as large as the number of combinations without repetition C(n, k), assuming n ≥ k. What structural feature of multisets accounts for this inequality?

Show answer

Every ordinary combination (a subset of size k from n elements) is also a valid multiset—it is simply a multiset in which no element has multiplicity greater than 1. Therefore the set of all multisets of size k from n types is a superset of the set of all ordinary k-subsets. This containment guarantees C(n + k − 1, k) ≥ C(n, k). The additional multisets that are not ordinary subsets are precisely those in which at least one type appears more than once, and these extra selections inflate the count.

Question 2: BASIC CALCULATION

A frozen yogurt shop has 6 toppings. A customer chooses 4 toppings for their bowl, and they may repeat toppings (e.g., extra sprinkles). How many distinct topping selections exist?

Show answer

This is a combination with repetition where n = 6 (types of toppings) and k = 4 (toppings selected). Apply the formula: C(n + k − 1, k) = C(6 + 4 − 1, 4) = C(9, 4). Evaluating: C(9, 4) = 9!/(4! × 5!) = (9 × 8 × 7 × 6)/(4 × 3 × 2 × 1) = 3024/24 = 126. There are 126 distinct topping selections.

Question 3: INTERMEDIATE

How many non-negative integer solutions does the equation x₁ + x₂ + x₃ + x₄ = 10 have? Then, how many solutions exist if we additionally require x₁ ≥ 2 and x₃ ≥ 1?

Show answer

For the unconstrained problem, we distribute 10 identical units among 4 variables: C(10 + 4 − 1, 10) = C(13, 10) = C(13, 3) = 286. For the constrained version, substitute y₁ = x₁ − 2 (so y₁ ≥ 0) and y₃ = x₃ − 1 (so y₃ ≥ 0), and keep y₂ = x₂, y₄ = x₄. The equation becomes y₁ + y₂ + y₃ + y₄ = 10 − 2 − 1 = 7, which has C(7 + 4 − 1, 7) = C(10, 7) = C(10, 3) = 120 non-negative integer solutions.

Question 4: APPLIED

A venture capital firm has $15 million to invest in equal $1 million increments across 5 technology sectors (AI, biotech, clean energy, cybersecurity, fintech). Each sector must receive at least $1 million. In how many distinct ways can the firm allocate its budget?

Show answer

Model this as distributing k = 15 identical units among n = 5 bins with each bin receiving at least 1. Substitute yᵢ = xᵢ − 1 for each sector so yᵢ ≥ 0 and y₁ + y₂ + y₃ + y₄ + y₅ = 15 − 5 = 10. The number of solutions is C(10 + 5 − 1, 10) = C(14, 10) = C(14, 4) = (14 × 13 × 12 × 11)/(4 × 3 × 2 × 1) = 24024/24 = 1001. There are 1,001 distinct allocation strategies.

Question 5: CRITICAL THINKING

Prove that the number of monomials of total degree exactly d in n variables equals C(n + d − 1, d). Then use this result to count the dimension of the vector space of homogeneous polynomials of degree 4 in 3 variables.

Show answer

A monomial of total degree d in variables x₁, …, xₙ has the form x₁^{a₁}x₂^{a₂}⋯xₙ^{aₙ} where each aᵢ ≥ 0 and a₁ + a₂ + ⋯ + aₙ = d. Each such monomial is uniquely determined by the exponent tuple (a₁, …, aₙ), which is a multiset of size d from n types—or equivalently, a non-negative integer solution to a₁ + ⋯ + aₙ = d. By the stars-and-bars theorem, the count is C(n + d − 1, d). For degree d = 4 in n = 3 variables: C(3 + 4 − 1, 4) = C(6, 4) = C(6, 2) = 15. The vector space of homogeneous degree-4 polynomials in three variables is 15-dimensional, spanned by monomials such as x₁⁴, x₁³x₂, x₁²x₂x₃, x₂²x₃², etc.

SUMMARY

Lesson Summary

Summary

Combinations with repetition count the number of multisets of size k drawn from n types, where order does not matter and each type may be selected any number of times. The stars-and-bars bijection reduces this to counting binary strings of k stars and n − 1 bars, yielding the multiset coefficient formula: C(n + k − 1, k). This formula is equivalently the number of non-negative integer solutions to x₁ + x₂ + ⋯ + xₙ = k.

Key applications include resource allocation, counting monomials in polynomial rings, and distributing identical objects into labeled bins. Remember the three prerequisites for applying the formula: selections must be unordered, types must have unlimited supply, and items of the same type must be indistinguishable. When lower bounds are imposed, a simple variable substitution reduces the constrained problem to the standard form. The generating function viewpoint—expanding 1/(1 − x)ⁿ—provides a unifying algebraic perspective that connects to symmetric functions and Pólya enumeration theory in more advanced courses.