Combinations with Repetition — Compute combinations with repetition - Finite Mathematics

SECTION 1

Historical Context & Motivation

Counting problems involving repeated selections arise naturally in commerce, science, and daily life. Long before formal combinatorics existed, merchants needed to know how many ways they could fill an order by choosing items from limited categories — say, selecting a dozen pastries from five varieties at a bakery. The mathematical machinery for answering such questions evolved gradually, drawing on contributions from Indian, Persian, and European mathematicians over more than a millennium. The concept we now call combinations with repetition (also known as multisets) formalizes the process of choosing k items from n types when each type may be selected more than once and order does not matter.

c. 300 BCE • Early Indian Combinatorics

Indian mathematicians such as those in the Jain tradition studied vikalpa (combinations), exploring how objects could be grouped in various ways, laying groundwork for systematic counting.

1321 • Levi ben Gershon

The French-Jewish mathematician Levi ben Gershon (Gersonides) provided early proofs related to permutations and combinations, formalizing the distinction between ordered and unordered selections.

1713 • Bernoulli's Ars Conjectandi

Jacob Bernoulli's posthumous work systematized binomial coefficients and their role in probability, providing the algebraic foundation upon which multiset coefficients would later be expressed.

1796 • Stars and Bars Technique

Euler's earlier partition work and subsequent contributions led to the elegant 'stars and bars' argument, later popularized by William Feller in the twentieth century, which reduces combinations with repetition to an ordinary binomial coefficient.

Modern • Applications Across Disciplines

Today, combinations with repetition appear in integer programming, polynomial enumeration, statistical mechanics (Bose–Einstein statistics), and algorithm design, making them indispensable across mathematics, physics, and computer science.

The central question this lesson addresses is deceptively simple: In how many ways can we choose k items from n types when repetition is allowed and order is irrelevant? The answer, expressed compactly through the multiset coefficient, is both elegant and broadly applicable. Mastering it equips you with a tool that appears repeatedly in discrete mathematics, probability theory, and optimization.

SECTION 2

Core Principles & Definitions

Before diving into formulas, it is essential to understand the conceptual landscape of counting problems. Four fundamental counting paradigms emerge from two binary choices: whether order matters and whether repetition is allowed. Combinations with repetition occupy the quadrant where order does not matter and repetition is allowed. A multiset is a generalization of a set that permits multiple instances of the same element — for instance, {a, a, b} is a multiset of size 3 drawn from {a, b}. The number of such multisets of size k chosen from n types is precisely the quantity we seek to compute.

Repetition Allowed

Each of the n types may be chosen as many times as desired. Selecting three apples from a fruit stand with apples, oranges, and bananas is perfectly valid.

Order Irrelevant

The selection {apple, apple, orange} is considered identical to {apple, orange, apple}. We care only about how many of each type are chosen, not the sequence in which they are chosen.

Stars and Bars Bijection

Every multiset of size k from n types corresponds uniquely to a binary string of k stars and n − 1 bars. This bijection is the key insight.

Reduction to Ordinary Combinations

Because a stars-and-bars string has k + n − 1 total positions, choosing the k star positions (or equivalently the n − 1 bar positions) reduces the problem to an ordinary binomial coefficient.

✦

KEY TAKEAWAY

Think of combinations with repetition like distributing k identical coins into n distinct jars. You do not care about the order in which the coins land — only how many end up in each jar. Each possible distribution corresponds to exactly one multiset. The 'stars and bars' argument converts this distribution problem into a simple problem of arranging two types of symbols in a row, which is just an ordinary combination.

SECTION 3

Visual Explanation — The Stars and Bars Bijection

The stars and bars technique is the most intuitive way to visualize combinations with repetition. Suppose we wish to choose k = 4 items from n = 3 types (say, apples, bananas, and cherries). We represent each chosen item as a star (★) and use n − 1 = 2 bars (|) as dividers between the types. The diagram below shows every possible arrangement of 4 stars and 2 bars, each corresponding to a distinct multiset.

Each row shows one arrangement of 4 stars (items chosen) and 2 bars (dividers between the 3 types). The tuple on the right indicates how many of each type are selected. There are C(6, 4) = 15 total multisets.

Notice the bijection at work: every distinct arrangement of 4 stars and 2 bars encodes a unique selection. The stars to the left of the first bar count apples, the stars between the two bars count bananas, and the stars to the right of the second bar count cherries. Because we are merely rearranging k + n − 1 = 6 symbols (choosing which 4 of the 6 positions will be stars), the count equals the ordinary binomial coefficient C(6, 4) = 15. This bijective argument is the conceptual heart of the formula we derive in the next section.

SECTION 4

Mathematical Framework

We now formalize the stars-and-bars intuition into a precise formula. Let n denote the number of types (categories) available, and let k denote the number of items we wish to select (with repetition allowed, order irrelevant). A selection is equivalent to a solution in nonnegative integers of the equation x₁ + x₂ + ⋯ + xₙ = k, where xᵢ represents the number of times type i is chosen.

NONNEGATIVE INTEGER EQUATION

x₁ + x₂ + ⋯ + xₙ = k, xᵢ ≥ 0

Each nonnegative integer solution corresponds to one multiset. The variable xᵢ records how many copies of type i appear in the selection.

Using the stars-and-bars bijection, each solution maps to an arrangement of k stars and n − 1 bars in a row of length k + n − 1. Choosing the positions for the stars (or equivalently, the bars) yields the following closed-form expression.

MULTISET COEFFICIENT (COMBINATIONS WITH REPETITION)

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

n = number of types, k = number of items chosen, C(a, b) = a! / (b!(a − b)!) is the ordinary binomial coefficient.

An equivalent way to write the formula is C(n + k − 1, n − 1), since C(m, j) = C(m, m − j). Choose whichever form makes computation simpler. When k is small, it is often easier to use C(n + k − 1, k); when n is small, C(n + k − 1, n − 1) involves smaller factorials.

EQUIVALENT FORM

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

Both expressions count the same quantity. Use the form that minimizes the bottom argument for computational efficiency.

⚠

Common Pitfall

Do not confuse combinations with repetition C(n + k − 1, k) with ordinary combinations without repetition C(n, k). The latter requires n ≥ k because each element can be chosen at most once; the former allows k to exceed n freely. For example, C(3 + 10 − 1, 10) = C(12, 10) = 66 is perfectly well-defined even though k = 10 far exceeds n = 3.

SECTION 5

The Four Counting Paradigms at a Glance

Combinations with repetition sit within a family of four counting models. Keeping them straight is essential: a single misidentification of the problem type can produce a dramatically wrong answer. The table and diagram below provide a systematic comparison, with combinations with repetition highlighted.

Model	Order Matters?	Repetition?	Formula
Permutations without repetition	Yes	No	P(n, k) = n! / (n − k)!
Permutations with repetition	Yes	Yes	nᵏ
Combinations without repetition	No	No	C(n, k) = n! / (k!(n − k)!)
Combinations with repetition	No	Yes	C(n + k − 1, k)

The four fundamental counting paradigms for selecting k items from n.

A decision tree for identifying the correct counting formula. Start at the top and answer two yes/no questions. Combinations with repetition is the model where order does not matter and repetition is allowed, yielding C(n + k − 1, k).

When solving a counting problem, begin by determining whether the selections are ordered or unordered, and whether each element can be chosen more than once. These two questions immediately narrow you to one of the four models. The most common error students make is confusing the 'with repetition' and 'without repetition' cases — a mistake that introduces a factor of (n − 1)! into the numerator or denominator, often changing the answer by orders of magnitude.

SECTION 6

Worked Example

A coffee shop offers 5 types of donuts: glazed, chocolate, maple, blueberry, and cinnamon. A customer wants to purchase a box of 8 donuts. How many different boxes can be assembled if repetition of types is allowed and the arrangement in the box does not matter?

Selecting 8 Donuts from 5 Types

1
Step 1 — Identify the model

The customer can choose the same type of donut more than once (repetition allowed), and a box of {glazed, glazed, chocolate} is the same as {chocolate, glazed, glazed} (order irrelevant). This is a combination with repetition problem.

Model: Combinations with repetition
2
Step 2 — Assign parameters

The number of types is n = 5 (the five donut flavors). The number of items to choose is k = 8 (the eight donuts in the box).

n = 5, k = 8
3
Step 3 — Apply the formula

Substitute into C(n + k − 1, k):

C(5 + 8 − 1, 8) = C(12, 8)
4
Step 4 — Simplify using the symmetry property

Since C(12, 8) = C(12, 4), we can compute with the smaller bottom argument: C(12, 4) = 12! / (4! × 8!).

C(12, 4) = (12 × 11 × 10 × 9) / (4 × 3 × 2 × 1)
5
Step 5 — Compute

Numerator: 12 × 11 = 132; 132 × 10 = 1320; 1320 × 9 = 11880. Denominator: 4! = 24. Dividing: 11880 / 24 = 495.

495 different boxes

💡

Sanity Check

With ordinary combinations (no repetition), choosing 8 items from 5 would be impossible since 8 > 5. The fact that C(12, 8) = 495 is well-defined and much larger than C(5, 5) = 1 confirms that repetition dramatically expands the number of possible selections.

SECTION 7

Strengths, Limitations, and Common Pitfalls

The multiset coefficient is a powerful and elegant tool, but like any formula, it applies only when its assumptions are met. Understanding both its strengths and its boundaries prevents misapplication and sharpens your problem-solving intuition.

Strengths	Limitations
Handles k > n gracefully — you can choose more items than there are types.	Assumes unlimited supply of each type. If type i has a maximum count, the formula does not apply directly.
Reduces to a single binomial coefficient — easy to compute even for large values.	Does not distinguish items within the same type. If identical-looking items are actually distinct, use permutations.
Bijection to stars and bars provides strong visual and conceptual clarity.	If order matters, you must use permutations with repetition (nᵏ) instead.
Connects directly to polynomial coefficient counting and partition theory.	Adding lower bounds (xᵢ ≥ aᵢ > 0) requires a change of variable before applying the formula.

Strengths and limitations of the multiset coefficient formula.

✦

WHEN TO USE — AND WHEN NOT TO

Use C(n + k − 1, k) only when three conditions hold simultaneously: (1) order is irrelevant, (2) repetition is allowed, and (3) there is no upper bound on how many times any single type can appear. If any condition fails, you need a different model — ordinary combinations for condition 2, permutations for condition 1, or inclusion-exclusion / generating functions for condition 3.

SECTION 8

Connections to Advanced Theory

The multiset coefficient is not an isolated formula — it sits at the intersection of several deep areas of mathematics. Understanding these connections enriches your perspective and equips you for more advanced coursework in combinatorics, algebra, and probability.

Area	Connection to Combinations with Repetition
Generating Functions	The coefficient of xᵏ in (1 − x)⁻ⁿ = Σ C(n + k − 1, k) xᵏ is precisely the multiset coefficient. This identity connects multisets to the theory of formal power series.
Integer Partitions	The number of ways to write k as an ordered sum of n nonneg. integers (compositions into n parts allowing zeros) equals C(n + k − 1, k). Removing the order constraint yields the harder problem of unrestricted partitions.
Polynomial Enumeration	The number of monomials of total degree k in n variables equals C(n + k − 1, k). Each monomial x₁^{a₁} · x₂^{a₂} · ⋯ · xₙ^{aₙ} with Σaᵢ = k corresponds to a multiset.
Bose–Einstein Statistics	In quantum physics, the number of ways to distribute k identical bosons among n energy states is C(n + k − 1, k). Indistinguishable particles in indistinguishable-order placements is precisely the multiset model.
Inclusion–Exclusion with Upper Bounds	When type i has a maximum count cᵢ, the unrestricted C(n + k − 1, k) serves as the base count, and inclusion–exclusion subtracts violations. The multiset coefficient is thus the starting point for constrained counting.

Advanced areas connected to the multiset coefficient.

As you continue into courses on combinatorics, probability, or abstract algebra, you will encounter the multiset coefficient in increasingly sophisticated settings. In particular, the generating-function perspective — viewing (1 − x)⁻ⁿ as the 'mother function' of all multiset counts — is a remarkably powerful technique that unifies a wide range of enumeration problems under a single algebraic framework.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why the formula for combinations with repetition uses C(n + k − 1, k) rather than C(n, k). What role do the extra n − 1 positions play in the stars-and-bars argument?

Show answer

In ordinary combinations without repetition, we choose k items from a pool of n distinct items, giving C(n, k). With repetition, we are instead arranging k identical stars and n − 1 bars in a row of length k + n − 1. The n − 1 bars serve as dividers that partition the k stars into n groups, one group per type. Because we need n − 1 dividers to create n groups (just as n − 1 fences create n fields), the total number of positions expands from n to n + k − 1. The formula C(n + k − 1, k) counts the number of ways to place k stars into these n + k − 1 positions, which is equivalent to choosing a multiset of size k from n types.

Question 2: BASIC CALCULATION

An ice cream parlor offers 6 flavors. A customer orders a sundae with 3 scoops, and scoops of the same flavor are allowed. How many distinct sundaes are possible (order of scoops does not matter)?

Show answer

This is a combination with repetition: n = 6 flavors, k = 3 scoops. Apply the formula: C(n + k − 1, k) = C(6 + 3 − 1, 3) = C(8, 3). Computing: C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 336 / 6 = 56. There are 56 distinct sundaes. Note that C(6, 3) = 20 would be the answer only if the customer could not repeat any flavor, so repetition adds 36 additional possibilities.

Question 3: INTERMEDIATE

How many nonnegative integer solutions are there to the equation x₁ + x₂ + x₃ + x₄ = 10?

Show answer

Each nonnegative integer solution (x₁, x₂, x₃, x₄) corresponds to a multiset of size k = 10 chosen from n = 4 types (where xᵢ represents the count of type i). Using the multiset formula: C(n + k − 1, k) = C(4 + 10 − 1, 10) = C(13, 10). By symmetry, C(13, 10) = C(13, 3) = (13 × 12 × 11) / (3 × 2 × 1) = 1716 / 6 = 286. There are 286 nonnegative integer solutions. This equivalence between distributing identical objects and solving linear Diophantine equations is one of the most powerful applications of the stars-and-bars method.

Question 4: APPLIED

A small investment firm wants to allocate $20 million among 4 sectors (technology, healthcare, energy, and finance), in whole millions of dollars. Each sector must receive at least $2 million. How many distinct allocations are possible?

Show answer

Since each sector must receive at least $2 million, we perform a change of variable: let yᵢ = xᵢ − 2 for each sector i, where xᵢ is the amount (in millions) allocated to sector i. Then each yᵢ ≥ 0, and the constraint x₁ + x₂ + x₃ + x₄ = 20 becomes y₁ + y₂ + y₃ + y₄ = 20 − 4(2) = 12. This is now a standard multiset problem with n = 4 types and k = 12 items. The number of solutions is C(4 + 12 − 1, 12) = C(15, 12) = C(15, 3) = (15 × 14 × 13) / (3 × 2 × 1) = 2730 / 6 = 455. There are 455 distinct allocations. The change-of-variable technique generalizes: for lower bounds aᵢ on each variable, replace k with k − Σaᵢ.

Question 5: CRITICAL THINKING

Prove that the number of monomials of total degree exactly d in n variables equals C(n + d − 1, d), and use this result to determine how many terms appear in the expansion of (x + y + z)⁷ before like terms are combined.

Show answer

A monomial of total degree d in variables x₁, x₂, …, xₙ has the form x₁^{a₁} x₂^{a₂} ⋯ xₙ^{aₙ} where each aᵢ ≥ 0 and a₁ + a₂ + ⋯ + aₙ = d. The exponent vector (a₁, …, aₙ) is a nonneg. integer solution to this equation, and distinct exponent vectors produce distinct monomials. By the stars-and-bars bijection, the number of such vectors is C(n + d − 1, d). For (x + y + z)⁷, we have n = 3 variables and d = 7. After like terms are combined, each distinct monomial

x^a

y^b

z^c

with a + b + c = 7 appears exactly once (with its multinomial coefficient). The number of such distinct monomials is C(3 + 7 − 1, 7) = C(9, 7) = C(9, 2) = 36. Note: before combining like terms, the multinomial theorem tells us there are 3⁷ = 2187 individual product terms in the expansion, but they collapse into exactly 36 distinct monomials, each with coefficient 7!/(a!b!c!).

SUMMARY

Lesson Summary

Summary

Combinations with repetition count the number of ways to select k items from n types when each type may be chosen multiple times and order does not matter. The central formula is the multiset coefficient: C(n + k − 1, k) = (n + k − 1)! / (k!(n − 1)!). This result arises from the stars and bars bijection, which maps each multiset to an arrangement of k stars and n − 1 bars, reducing the problem to an ordinary binomial coefficient.

Key applications include counting nonnegative integer solutions to x₁ + x₂ + ⋯ + xₙ = k, enumerating monomials of a given degree, and modeling Bose–Einstein distributions in physics. When lower bounds are imposed on each variable, perform a change of variable to convert to an unrestricted problem. Always verify that the three assumptions — no order, repetition allowed, no upper bounds — are satisfied before applying the formula.