Definition:Permutation/Ordered Selection

From ProofWiki
Jump to navigation Jump to search

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$


In two-row notation on the permutations on $3$ letters:

$\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


In two-row notation on the permutations on $4$ letters:

$\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).


Sources