The rearrangement of elements in a set into a One-to-One correspondence with itself, also called an
Arrangement or Order. The number of ways of obtaining
*ordered* outcomes from a permutation of elements is

(1) |

A representation of a permutation as a product of Cycles is unique (up to the ordering of the cycles). An example of a cyclic decomposition is (, ), corresponding to the permutations (, , ) and (), which combine to give .

Any permutation is also a product of Transpositions. Permutations are commonly denoted in Lexicographic or Transposition Order. There is a correspondence between a Permutation and a pair of Young Tableaux known as the Schensted Correspondence.

The number of wrong permutations of objects is where is the Nint function. A permutation of ordered objects in which no object is in its natural place is called a Derangement (or sometimes, a Complete Permutation) and the number of such permutations is given by the Subfactorial .

Using

(2) |

(3) |

The set of all permutations of a set of elements 1, ..., can be obtained using the following
recursive procedure

(4) |

(5) |

Let the set of Integers 1, 2, ..., be permuted and the resulting sequence be divided into
increasing Runs. As approaches Infinity, the average length of the th Run is denoted
. The first few values are

(6) | |||

(7) | |||

(8) |

where

**References**

Bogomolny, A. ``Graphs.'' http://www.cut-the-knot.com/do_you_know/permutation.html.

Conway, J. H. and Guy, R. K. ``Arrangement Numbers.'' In *The Book of Numbers.* New York: Springer-Verlag, p. 66, 1996.

Dickau, R. M. ``Permutation Diagrams.'' http://forum.swarthmore.edu/advanced/robertd/permutations.html.

Knuth, D. E. *The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed.* Reading, MA: Addison-Wesley, 1973.

Kraitchik, M. ``The Linear Permutations of Different Things.'' §10.1 in *Mathematical Recreations.*
New York: W. W. Norton, pp. 239-240, 1942.

Le Lionnais, F. *Les nombres remarquables.* Paris: Hermann, pp. 41-42, 1983.

Ruskey, F. ``Information on Permutations.'' http://sue.csc.uvic.ca/~cos/inf/perm/PermInfo.html.

Sloane, N. J. A. Sequence
A000142/M1675
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.
*The Encyclopedia of Integer Sequences.* San Diego: Academic Press, 1995.

© 1996-9

1999-05-26