# Definition:Permutation/Ordered Selection

## Definition

Let $S$ be a set of $n$ elements.

Let $r \in \N: r \le n$.

An $r$-permutation of $S$ is an ordered selection of $r$ elements of $S$.

From this definition, it can be seen that a bijection $f: S \to S$ (defined as a mapping) is an $n$-permutation.

## Notation

The number of $r$-permutations from a set of cardinality $n$ is denoted variously:

$P_{n r}$
${}^r P_n$
${}_r P_n$
${}_n P_r$ (extra confusingly)

There is little consistency in the literature).

On $\mathsf{Pr} \infty \mathsf{fWiki}$ the notation of choice is ${}^r P_n$.

## Also known as

A permutation as used in this context is also known as a rearrangement.

## Examples

### $2$ from $3$

There are $6$ permutations of $2$ objects taken $3$ at a time:

$a \, b \quad a \, c \quad b \, a \quad b \, c \quad c \, a \quad c \, b$

### $3$ from $3$

There are $6$ permutations of $3$ objects taken $3$ at a time:

$a \, b \, c \quad a \, c \, b \quad b \, a \, c \quad b \, c \, a \quad c \, a \, b \quad c \, b \, a$
$\dbinom {1 \ 2 \ 3} { 1 \ 2 \ 3}, \dbinom {1 \ 2 \ 3} { 1 \ 3 \ 2}, \dbinom {1 \ 2 \ 3} { 2 \ 1 \ 3}, \dbinom {1 \ 2 \ 3} { 2 \ 3 \ 1}, \dbinom {1 \ 2 \ 3} { 3 \ 1 \ 2}, \dbinom {1 \ 2 \ 3} { 3 \ 2 \ 1}$

### $4$ from $4$

There are $24$ permutations of $4$ objects taken $4$ at a time

$\begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_1 & a_2 & a_3 & a_4 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_1 & a_2 & a_4 & a_3 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_1 & a_3 & a_2 & a_4 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_1 & a_3 & a_4 & a_2 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_1 & a_4 & a_2 & a_4 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_1 & a_4 & a_3 & a_2 \end{pmatrix},$
$\begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_2 & a_1 & a_3 & a_4 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_2 & a_1 & a_4 & a_3 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_2 & a_3 & a_1 & a_4 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_2 & a_3 & a_4 & a_1 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_2 & a_4 & a_1 & a_3 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_2 & a_4 & a_3 & a_1 \end{pmatrix},$
$\begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_3 & a_1 & a_2 & a_4 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_3 & a_1 & a_4 & a_2 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_3 & a_2 & a_1 & a_4 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_3 & a_2 & a_4 & a_1 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_3 & a_4 & a_1 & a_2 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_3 & a_4 & a_2 & a_1 \end{pmatrix},$
$\begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_1 & a_2 & a_3 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_1 & a_3 & a_2 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_2 & a_1 & a_3 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_2 & a_3 & a_1 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_3 & a_1 & a_2 \end{pmatrix}, \begin{pmatrix} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_3 & a_2 & a_1 \end{pmatrix}$

## Also see

${}^r P_n = \dfrac {n!} {\left({n - r}\right)!}$
${}^n P_n = n!$
• Results about permutations can be found here.

## Linguistic Note

The word permutation to mean a bijection from a set to itself is historical, from when the term was reserved for finite sets.

As Don Knuth points out in The Art of Computer Programming: Volume 1: Fundamental Algorithms, Vaughan Pratt has made the suggestion that, because permutations are so important in the field of computer science, they be called perms:

As soon as Pratt's convention is established, textbooks of computer science will become somewhat shorter (and perhaps less expensive).