Combinations with Repetition — Mathematics Knowledge System

Overview

An ordinary combination C(n,k) selects k distinct elements from a set of n, with no element chosen twice. A combination WITH repetition (also called a multiset coefficient) relaxes that rule: elements may be chosen more than once, and only the final count of each type matters, not the order in which they were picked. The classic image is an ice-cream counter with n flavors, where you order k scoops but may repeat a flavor — how many distinct orders are possible? The count is given by the 'stars and bars' formula C(n+k-1, k), and the technique underlies counting integer solutions to equations, sampling with replacement, and multiset enumeration throughout combinatorics.

Intuition

Think of choosing k scoops from n flavors as distributing k identical scoops among n flavor 'bins.' Line up the k scoops (stars) and use n-1 dividers (bars) to mark the boundaries between flavor bins: e.g. for 3 flavors and 5 scoops, the string ★★|★|★★ means 2 scoops of flavor 1, 1 of flavor 2, and 2 of flavor 3. Any arrangement of k stars and n-1 bars in a row corresponds to exactly one valid multiset, and vice versa. So the count of multisets equals the number of ways to arrange k stars and n-1 bars in a line of length k+n-1, which is just choosing which k (or n-1) of those positions hold stars (or bars): C(n+k-1, k).

Formal Definition

Definition

A k-combination with repetition from an n-element set is a multiset of size k drawn from that set — an unordered selection of k picks where each pick can be any of the n types, and repeats are allowed. The number of such multisets is denoted C(n+k-1, k) or sometimes written with double-parenthesis notation:

\left(\!\!\binom{n}{k}\!\!\right) = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k!\,(n-1)!}

Number of k-multisets from an n-element set

x_1 + x_2 + \cdots + x_n = k, \quad x_i \ge 0 \text{ integers}

Equivalent problem: nonnegative integer solutions

Derivation

Derive the stars-and-bars formula by encoding each multiset as a binary string and counting those strings with an ordinary combination.

\text{Represent flavor counts } x_1,\dots,x_n \ge 0 \text{ with } \sum x_i = k \text{ as a string of } k \text{ stars and } n-1 \text{ bars.}

x_i stars in a row, separated by n-1 dividers between the n flavor groups.

\text{The string has length } k + (n-1).

k stars plus n-1 bars.

\text{Choosing which } k \text{ of these } k+n-1 \text{ positions are stars determines the whole string.}

Once the star positions are fixed, the bars fill the remaining n-1 positions.

\binom{n+k-1}{k}

The number of such strings, hence the number of k-multisets from n types.

Proofs

Bijection between k-multisets of an n-set and nonnegative integer solutions of x_1+...+x_n=k

$\text{Given a multiset with } x_i \text{ copies of type } i, \text{ map it to the tuple } (x_1,\dots,x_n).$ (Every multiset of size k is completely described by how many times each of the n types appears.)
$\sum_{i=1}^{n} x_i = k, \qquad x_i \ge 0$ (The total number of picks across all types must equal k.)
$\text{This map is a bijection: distinct multisets give distinct tuples, and every valid tuple comes from some multiset.}$ (The tuple (x_1,...,x_n) uniquely reconstructs the multiset by including x_i copies of type i.)
$\text{Number of tuples} = \binom{n+k-1}{k} \text{ by stars and bars.}$ (Counting nonnegative integer solutions of a sum-k equation in n variables is the stars-and-bars combinatorial identity.)

Properties

Stars-and-bars formula

\left(\!\!\binom{n}{k}\!\!\right) = \binom{n+k-1}{k}

Symmetry with ordinary combinations

\binom{n+k-1}{k} = \binom{n+k-1}{n-1}

Boundary values

\left(\!\!\binom{n}{0}\!\!\right) = 1, \qquad \left(\!\!\binom{1}{k}\!\!\right) = 1 \text{ for all } k

Applications

Counting the number of ways to allocate k identical requests among n servers, or k identical tokens among n bins, is a direct stars-and-bars computation.

Worked Examples

n = 3 flavors, k = 5 scoops. Apply the stars-and-bars formula.
$\binom{3+5-1}{5} = \binom{7}{5} = \frac{7!}{5!\,2!} = \frac{42}{2} = 21$

Answer: 21 distinct 5-scoop orders.

Practice Problems

Difficulty 3/10

How many ways can you choose 2 scoops from 8 flavors, with repetition allowed and order irrelevant?

Difficulty 4/10

How many nonnegative integer solutions does a + b = 7 have?

Difficulty 6/10

A bakery sells 5 types of muffins. A customer buys a dozen (12) muffins, possibly repeating types, and doesn't care about order. How many distinct dozen-boxes are possible?

Common Mistakes

Common Mistake

Using the ordinary combination formula C(n,k) when repetition is allowed.

C(n,k) assumes no element repeats. When repeats are allowed and order doesn't matter, use the multiset formula C(n+k-1,k) instead.

Common Mistake

Confusing combinations with repetition (order doesn't matter) with sequences with repetition (order matters, counted by n^k).

If the picks are ordered (e.g. a sequence of k dice rolls from n faces), the count is n^k. Combinations with repetition apply only when the final unordered multiset is what's being counted.

Quiz

Summary

Combinations with repetition count unordered selections of k items from n types where repeats are allowed.
The stars-and-bars formula gives the count: C(n+k-1,k), derived by arranging k stars and n-1 bars in a row.
This is equivalent to counting nonnegative integer solutions of x_1+...+x_n=k.
Distinguish it from n^k (ordered sequences with repetition) and from C(n,k) (unordered, no repetition).

References

WebsiteWikipedia — Combination (Number of combinations with repetition)