Variation without Repetition

combinatorics

Definition

Variation without Repetition

A variation without repetition chooses $k$ different elements from $n$ available elements and places them in order. Order matters, so $(a,b)$ and $(b,a)$ are different selections, and no element may occur twice.

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

$$(x_1,\dots ,x_k),x_i\in X,i\ne j⟹x_i\ne x_j.$$

Equivalently, the tuple defines an injective position map

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

The number of such ordered selections is

$$V(n,k)=n(n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!},0\le k\le n.$$

This generalises a permutation without repetition: a variation may use any $k\le n$ elements, while a permutation is the special case $k=n$, in which every element is used.

Derivation from the Product Rule

Construct a variation from left to right, stopping after $k$ positions. The first few positions reveal the pattern directly:

$$\begin{array}{rlrl}\text{position }1& :0\text{ elements used},& & n\text{ choices remain},\\ \text{position }2& :1\text{ element used},& & n-1\text{ choices remain},\\ \text{position }3& :2\text{ elements used},& & n-2\text{ choices remain},\\ & ⋮& & \\ \text{position }k& :k-1\text{ elements used},& & n-k+1\text{ choices remain}.\end{array}$$

The symbol $i$ names the current position. Before position $i$, the earlier positions $1,\dots ,i-1$ have been filled, so $i-1$ distinct elements are no longer available. The number of legal choices is therefore

$$n-(i-1)=n-i+1.$$

Every complete variation follows one path through these $k$ stages. Each first-position choice has $n-1$ continuations at the second position; each of those has $n-2$ continuations at the third; and the construction stops after position $k$.

For $X=\{a,b,c\}$ and $k=2$, the complete paths are:

The product rule multiplies the stage counts:

$$\begin{array}{rl}V(n,k)& =\prod _{i=1}^k(n-i+1)\\ & =n(n-1)\cdots (n-k+1).\end{array}$$

Expanding $n!$ separates the unused tail,

$$n!=n(n-1)\cdots (n-k+1)(n-k)!,$$

so division by $(n-k)!$ leaves exactly the first $k$ factors:

$$V(n,k)=\frac{n!}{(n-k)!}.$$

From Combination and Permutation to Variation

A variation without repetition is a combination without repetition together with an ordering of its selected elements. It can therefore be constructed in two stages. First, choose an unordered $k$-element subset in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways. Then arrange its $k$ elements in $k!$ ways.

For $X=\{a,b,c\}$ and $k=2$, the construction forms the following paths:

In general, the first stage has $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ branches and every branch has $k!$ continuations.

The product rule gives

$$V(n,k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)k!=\frac{n!}{(n-k)!}.$$

Conversely, forgetting the order of a variation returns its underlying combination. Every combination has exactly $k!$ variations above it, one for each ordering of its elements.

Boundary Cases

When $k=n$, every element is used and the variation is a permutation without repetition, so $V(n,n)=n!$. When $k=0$, there is one empty tuple, so $V(n,0)=1$.

Example

Awarding three medals

Eight runners compete for gold, silver, and bronze. The positions are ordered, and one runner cannot receive two medals.

Algebraically,

$$V(8,3)=\frac{8!}{5!}=8\cdot 7\cdot 6=336.$$