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:
- ${}_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
- Number of Permutations, where it is shown that:
- ${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
- ${}^n P_n = n!$
- Definition:Falling Factorial, where it can be seen that ${}^n P_r = n^{\underline r}$
- 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
- 1953: L. Harwood Clarke: A Note Book in Pure Mathematics ... (previous) ... (next): $\text I$. Algebra: Permutations and Combinations
- 1964: A.M. Yaglom and I.M. Yaglom: Challenging Mathematical Problems With Elementary Solutions: Volume $\text { I }$ ... (previous) ... (next): Problems
- 1965: J.A. Green: Sets and Groups ... (previous) ... (next): $\S 3.6$. Products of bijective mappings. Permutations
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-1}$ Permutations and Combinations: Definition $\text {3-1}$
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 22$: Injections; bijections; inverse of a bijection: Note
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): Glossary
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $9$: Permutations
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.5$: Permutations and Factorials
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): Glossary
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): permutation