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:

${}_n P_r$
${P_n}^r$
$p_{n r}$
${}^n P_r$

There is little consistency in the literature.

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


Also known as

A permutation as used in this context is also known as an arrangement or rearrangement.

The term ordered selection is also used when it is necessary to distinguish this concept precisely from that of a bijection from a set to itself.


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

${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
${}^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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Permutation/Ordered_Selection&oldid=596513"