Namespaces
Variants
Actions

Permutation

From Encyclopedia of Mathematics
Revision as of 17:16, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

of elements

A finite sequence of length in which all the elements are different, i.e. a permutation is an arrangement of elements without repetition. The number of permutations is .

Usually, one takes as the elements to be permuted the elements of the set ; a one-to-one mapping of onto itself defines the permutation . The mapping is also called a substitution of . Many problems related to the enumeration of permutations are formulated in terms of substitutions, such as, for example, the enumeration of permutations with various restrictions on the positions of the permuted elements (cf. e.g. [1], [2]). A permutation can be regarded as an ordered set consisting of elements if one assumes that precedes , .

Examples. 1) The pair forms an inversion in if for ; if is the number of permutations of elements with inversions, then

2) If is the number of permutations consisting of elements such that for even and for odd, then

Often a permutation is defined to be a bijective mapping of a finite set onto itself, i.e. a substitution (cf. also Permutation of a set).

References

[1] V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[2] J. Riordan, "An introduction to combinational analysis" , Wiley (1958)


Comments

See also Permutation group.

How to Cite This Entry:
Permutation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Permutation&oldid=48160
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article