Definition:Permutation

From ProofWiki
Jump to navigation Jump to search

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

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