Variation with Repetition

combinatorics

Definition

Variation with Repetition

A variation with repetition chooses $k$ elements from $n$ available elements and places them in order. Order matters, and the same element may be chosen more than once.

For a finite set $X$ with $|X|=n$, it is an ordered tuple

$$(x_1,\dots ,x_k),x_i\in X.$$

Equivalently, the tuple defines an unrestricted position map

$$v:\{1,\dots ,k\}\to X,v(i)=x_i.$$

Unlike a variation without repetition, this map need not be injective. The number of variations with repetition is

$$n^k.$$

Derivation from the Product Rule

Construct a variation from left to right, stopping after $k$ positions. At every position, all $n$ elements remain available because an earlier choice does not remove an element from future choices:

$$\begin{array}{rl}\text{position }1& :n\text{ choices},\\ \text{position }2& :n\text{ choices},\\ \text{position }3& :n\text{ choices},\\ & ⋮\\ \text{position }k& :n\text{ choices}.\end{array}$$

Before position $i$, exactly $i-1$ choices have been made, but repetition keeps every element of $X$ legal. The number of choices at position $i$ is therefore still $|X|=n$.

Every complete variation follows one path through these $k$ stages. For $X=\{a,b\}$ and $k=3$, the complete paths are:

At every level, each partial tuple has exactly two continuations because both $a$ and $b$ remain available. In general, every level has $n$ choices. The product rule therefore gives

$$\underset{k\text{ factors}}{\underbrace{n\cdot n\cdots n}}=n^k.$$

Distinction from Permutation with Repetition

Warning

A variation with repetition chooses a value separately for each position, so the resulting multiplicities are not fixed in advance. A permutation with repetition instead starts from a multiset with fixed multiplicities and rearranges all of its occurrences.

Example

Four-digit codes

A four-digit code uses the ten digits $\{0,1,\dots ,9\}$. Order matters, repetitions are allowed, and leading zeros are permitted. For example, $0070$ is valid.

Hence the number of possible codes is

$$10^4=10000.$$