Definition:Permutation

Definition

Mapping

A bijection $f: S \to S$ from a set $S$ to itself is called a permutation on (or of) $S$.

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$.

This can denoted $P_{nr}$, ${}^r P_n$, ${}_r P_n$ or even (extra confusingly) ${}_n P_r$ (there is little consistency in the literature).

From this definition, it can be seen that a bijection $f: S \to S$ (as defined above) is an $n$-permutation.

From Number of Permutations it can be seen that:

• $P_{nr} = \dfrac {n!} {\left({n-r}\right)!}$
• $P_{nn} = n!$

Using the falling factorial symbol, this can also be expressed:

$P_{nr} = n^{\underline r}$

Also see

• Permutation on n Letters

Linguistic Note

As Don Knuth points out, 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

• W.E. Deskins: Abstract Algebra (1964): Exercise $1.3: \ 5$
• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 3.6$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 5$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 1.6$
• George McCarty: Topology: An Introduction with Application to Topological Groups (1967): Chapter $\text{II}$: Problem $\text{EE}$
• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.5$
• Ian D. Macdonald: The Theory of Groups (1968): Appendix
• George E. Andrews: Number Theory (1971): $\S 3.1$: Definition $3.1$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 76$
• Gary Chartrand: Introductory Graph Theory (1977): Appendix $\text{A}.4$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 22$
• John F. Humphreys: A Course in Group Theory (1996): $\S 2$: Definition $2.17$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.11$