“Permutation”的概念、定义、习题解题方法及翻译-数学辞典

单词

Permutation

释义

Permutation

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

(1)

where

Factorial and

is a Binomial Coefficient. The total number of permutationsfor

elements is given by

A representation of a permutation as a product of Cycles is unique (up to the ordering ofthe 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 inLexicographic or Transposition Order. There is a correspondence between aPermutation 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 CompletePermutation) and the number of such permutations is given by the Subfactorial .

Using

(2)

with

gives

(3)

so the number of ways of choosing 0, 1, ..., or

at a time is

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

(4)

(5)

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

			(6)
			(7)
			(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, LinearExtension, 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 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. SequenceA000142/M1675in ``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.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。