# Definition:Permutation

## Contents

## 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 $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 Permutation on Sets

Let $A = \set {a_1, a_2, a_3, a_4}$.

Let $f \subseteq {A \times B}$ 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$.

### 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): $\S 5$ - 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): $\text{II}$: The Group Property - 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