Permutation

discrete-math

Definition

Permutation

A permutation of a set $X$ is a bijective function from $X$ to itself:

$$\pi :X\to X.$$

Thus every element of $X$ has exactly one image and exactly one preimage. A permutation may move elements, but it neither duplicates nor removes them.

Finite Sets

If $|X|=n$, then $X$ has $n!$ permutations, where $n!$ is the factorial. After ordering the elements of $X$ as $x_1,\dots ,x_n$, every permutation corresponds to the ordered arrangement

$$(\pi (x_1),\dots ,\pi (x_n)).$$

Example

A three-cycle

On $X=\{1,2,3\}$, define

$$\pi (1)=2,\pi (2)=3,\pi (3)=1.$$

This is a permutation because every element appears exactly once as an output. In cycle notation, it is written $(123)$.