Definition:Combination with Repetition

Definition

Let $S$ be a (finite) set with $n$ elements.

A $k$ combination of $S$ with repetition is a multiset with $k$ elements selected from $S$.

Also known as

Some sources give this as combination with repetitions, but the philosophical position of $\mathsf{Pr} \infty \mathsf{fWiki}$ is that the singular form repetition is more grammatically flexible, in that it allows for a singular repetition, or indeed, no repetition at all.

Example

Let $S = \left\{ {a, b, c, d, e}\right\}$ be a set with $5$ elements.

The $3$-combinations of $S$ with repetition are:

$aaa, aab, aac, aad, aae,$

$abb, abc, abd, abe, acc,$

$acd, ace, add, ade, aee,$

$bbb, bbc, bbd, bbe, bcc,$

$bcd, bce, bdd, bde, bee,$

$ccc, ccd, cce, cdd, cde,$

$cee, ddd, dde, dee, eee$

Also see

• Definition:Combination

• Results about combinations with repetition can be found here.

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $60$