Permutation

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 $r$ ordered outcomes from a permutation of $n$ elements is

$${}_nP_r \equiv {n!\over (n-r)!}=r!{n\choose r},$$ (1)

where $n!$ is $n$ Factorial and ${a\choose b}$ is a Binomial Coefficient. The total number of permutations for $n$ elements is given by $n!$.

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 ($\{1, 3, 4\}$, $\{2\}$), corresponding to the permutations ($1\to 3$, $3\to 4$, $4\to 1$) and ($2\to 2$), which combine to give $\{4, 2, 1, 3\}$.

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 $n$ objects is $[n!/e]$ where $[x]$ is the Nint function. A permutation of $n$ 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 $!n$.

Using

$$(x+y)^n=\sum_{r=0}^n {n\choose r}x^{n-r}y^r$$ (2)

with $x=y=1$ gives

$$2^n=\sum_{r=0}^n {n\choose r},$$ (3)

so the number of ways of choosing 0, 1, ..., or $n$ at a time is $2^n$.

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

$$\matrix{ & 1 & 2\cr & / & \cr 2 & 1 & \cr}$$ (4)

$$\matrix{ & 1 & & 2 & 3\cr & & & / & \cr & 1 & 3 & 2 & \cr... ...r & 2 & 3 & 1 & \cr & & &\backslash & \cr & 2 & & 1 & 3\cr}$$ (5)

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

$$L_1 = e-1=1.7182818\ldots$$ (6)

$$L_2 = e^2-2e=1.9524\ldots$$ (7)

$$L_3 = e^3-3e^2+{\textstyle{3\over 2}}e=1.9957\ldots,$$ (8)

where e is the base of the Natural Logarithm (Knuth 1973, Le Lionnais 1983).

See also Alternating Permutation, Binomial Coefficient, Circular Permutation, Combination, Complete Permutation, Derangement, Discordant Permutation, Eulerian Number, Linear Extension, Permutation Matrix, Subfactorial, Transposition

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