Definition:Permutation
Definition
A bijection $f: S \to S$ from a set $S$ to itself is called a permutation on (or of) $S$.
Permutation on $n$ Letters
Let $\N_k$ be used to denote the initial segment of natural numbers:
- $\N_k = \closedint 1 k = \set {1, 2, 3, \ldots, k}$
A permutation on $n$ letters is a permutation:
- $\pi: \N_n \to \N_n$
The usual symbols for denoting a general permutation are $\pi$ (not to be confused with the famous circumference over diameter), $\rho$ and $\sigma$.
Ordered Selection
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$.
Also known as
When the domain $S$ is an infinite set, a permutation $f: S \to S$ is often termed a transformation, but that term suffers from being used for various considerably vaguer concepts.
Examples
Arbitrary Example $1$
Let $A = \set {a_1, a_2, a_3, a_4}$.
Let $f: A \to A$ be the mapping defined as:
- $f = \set {\tuple {a_1, a_3}, \tuple {a_2, a_4}, \tuple {a_3, a_1}, \tuple {a_4, a_2} }$
Then $f$ is a permutation on $A$.
Arbitrary Example $2$
Let $A = \set {a_1, a_2, a_3}$.
Using two-row notation, a permutation on $A$ can be denoted:
- $f = \begin {pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end {pmatrix}$
This can also be denoted:
- $f = \set {\tuple {a_1, a_3}, \tuple {a_2, a_1}, \tuple {a_3, a_2} }$
Addition of Constant on $\Z$
Let $\Z$ denote the set of integers.
Let $a \in \Z$.
Let $f: \Z \to \Z$ denote the mapping defined as:
- $\forall x \in \Z: \map f x = x + a$
Then $f$ is a permutation on $\Z$.
Also see
- 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
- 1964: W.E. Deskins: Abstract Algebra ... (previous) ... (next): Exercise $1.3: \ 5$
- 1965: J.A. Green: Sets and Groups ... (previous) ... (next): $\S 3.6$. Products of bijective mappings. Permutations
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text I$: Algebraic Structures: $\S 5$: Composites and Inverses of Functions
- 1966: Richard A. Dean: Elements of Abstract Algebra ... (previous) ... (next): $\S 1.6$
- 1967: George McCarty: Topology: An Introduction with Application to Topological Groups ... (previous) ... (next): Chapter $\text{II}$: Groups: The Group Property
- 1967: George McCarty: Topology: An Introduction with Application to Topological Groups ... (previous) ... (next): Chapter $\text{II}$: Groups: Problem $\text{EE}$
- 1968: Ian D. Macdonald: The Theory of Groups ... (previous) ... (next): $\S 1$: Some examples of groups
- 1968: Ian D. Macdonald: The Theory of Groups ... (previous) ... (next): Appendix: Elementary set and number theory
- 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $2$: The Symmetric Groups: $\S 76$
- 1972: A.G. Howson: A Handbook of Terms used in Algebra and Analysis ... (previous) ... (next): $\S 2$: Sets and functions: Some special types of function
- 1974: Thomas W. Hungerford: Algebra ... (previous) ... (next): $\text{I}$: Groups: $\S 1$: Semigroups, Monoids and Groups
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Appendix $\text{A}.4$: Functions
- 1978: John S. Rose: A Course on Group Theory ... (previous) ... (next): $0$: Some Conventions and some Basic Facts
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 22$: Injections; bijections; inverse of a bijection: Definition $2$
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): $\S 3.2$: Groups; the axioms: Examples of groups $\text{(iii)}$
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $2$: Maps and relations on sets: Definition $2.17$
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): Appendix $\text{A}.11$: Permutations
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): permutation: 2.
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): permutation: 2.
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): permutation