Permutation without Repetition

combinatorics

Definition

Permutation without Repetition

A permutation without repetition chooses all $n$ distinct elements and places them in order. Order matters, and every element is used exactly once.

For a finite set $X$ with $|X|=n$, it is an ordered tuple $(x_1,\dots ,x_n)$ in which every element of $X$ occurs exactly once.

Equivalently, the position map

$$\pi :\{1,\dots ,n\}\to X,\pi (i)=x_i,$$

is bijective.

Derivation from the Product Rule

Construct a permutation from left to right. 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 }n& :n-1\text{ elements used},& & 1\text{ choice remains}.\end{array}$$

The symbol $i$ merely names the current position. Before position $i$, the earlier positions $1,\dots ,i-1$ have already been filled. There are $i-1$ of them, and because repetition is forbidden, they have consumed $i-1$ distinct elements. The number still available is therefore

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

Every complete permutation follows one path through these stages. Each first-position choice has $n-1$ possible continuations at the second position; each of those has $n-2$ continuations at the third; and so on.

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

The product rule therefore multiplies the stage counts:

$$\begin{array}{rl}\prod _{i=1}^n(n-i+1)& =n(n-1)(n-2)\cdots 2\cdot 1\\ & =n!.\end{array}$$

Thus a set of $n$ distinct elements has exactly the factorial $n!$ permutations without repetition.

Example

Three elements

The set $X=\{1,2,3\}$ has $3!=6$ permutations without repetition:

$$(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1).$$