Namespaces
Variants
Actions

Difference between revisions of "Permutation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
''of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722701.png" /> elements''
+
<!--
 +
p0722701.png
 +
$#A+1 = 31 n = 0
 +
$#C+1 = 31 : ~/encyclopedia/old_files/data/P072/P.0702270 Permutation
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
A finite sequence of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722702.png" /> in which all the elements are different, i.e. a permutation is an [[Arrangement|arrangement]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722703.png" /> elements without repetition. The number of permutations is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722704.png" />.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
Usually, one takes as the elements to be permuted the elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722705.png" />; a one-to-one mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722706.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722707.png" /> onto itself defines the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722708.png" />. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722709.png" /> is also called a substitution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227010.png" />. 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. [[#References|[1]]], [[#References|[2]]]). A permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227011.png" /> can be regarded as an ordered set consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227012.png" /> elements if one assumes that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227013.png" /> precedes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227015.png" />.
+
''of $  n $
 +
elements''
  
Examples. 1) The pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227016.png" /> forms an inversion in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227017.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227018.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227019.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227020.png" /> is the number of permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227021.png" /> elements with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227022.png" /> inversions, then
+
A finite sequence of length  $  n $
 +
in which all the elements are different, i.e. a permutation is an [[Arrangement|arrangement]] of  $  n $
 +
elements without repetition. The number of permutations is  $  n! $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227023.png" /></td> </tr></table>
+
Usually, one takes as the elements to be permuted the elements of the set  $  \mathbf Z _ {n} = \{ 1 \dots n \} $;  
 +
a one-to-one mapping  $  \pi $
 +
of  $  \mathbf Z _ {n} $
 +
onto itself defines the permutation  $  \overline \pi \; = ( \pi ( 1) \dots \pi ( n)) $.
 +
The mapping  $  \pi $
 +
is also called a substitution of  $  \mathbf Z _ {n} $.
 +
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. [[#References|[1]]], [[#References|[2]]]). A permutation  $  \overline \pi \; $
 +
can be regarded as an ordered set consisting of  $  n $
 +
elements if one assumes that  $  \pi ( i) $
 +
precedes  $  \pi ( i+ 1) $,
 +
$  i = 1 \dots n $.
  
2) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227024.png" /> is the number of permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227025.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227026.png" /> elements such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227027.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227028.png" /> even and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227029.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227030.png" /> odd, then
+
Examples. 1) The pair  $  \{ \pi ( i) , \pi ( j) \} $
 +
forms an inversion in  $  \overline \pi \; $
 +
if  $  \pi ( i) > \pi ( j) $
 +
for  $  i < j $;
 +
if  $  a _ {r} $
 +
is the number of permutations of $  n $
 +
elements with  $  r $
 +
inversions, then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227031.png" /></td> </tr></table>
+
$$
 +
\sum _ { r= } 0 ^ {  \left  ( \begin{array}{c}
 +
n \\
 +
2
 +
\end{array}
 +
\right ) } a _ {r} x  ^ {r}  = \
 +
 
 +
\frac{( 1- x) \dots ( 1- x  ^ {n} ) }{( 1- x)  ^ {n} }
 +
.
 +
$$
 +
 
 +
2) If  $  b _ {n} $
 +
is the number of permutations  $  \overline \pi \; $
 +
consisting of  $  n $
 +
elements such that  $  \pi ( i) > \pi ( i- 1) $
 +
for  $  i $
 +
even and  $  \pi ( i) < \pi ( i- 1) $
 +
for  $  i $
 +
odd, then
 +
 
 +
$$
 +
\sum _ { n= } 0 ^  \infty  b _ {n}
 +
\frac{x  ^ {n} }{n!}
 +
  =   \mathop{\rm tan}  x +  \mathop{\rm sec}  x.
 +
$$
  
 
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|Permutation of a set]]).
 
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|Permutation of a set]]).
Line 17: Line 69:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.N. Sachkov,  "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Riordan,  "An introduction to combinational analysis" , Wiley  (1958)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.N. Sachkov,  "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Riordan,  "An introduction to combinational analysis" , Wiley  (1958)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
See also [[Permutation group|Permutation group]].
 
See also [[Permutation group|Permutation group]].

Revision as of 08:05, 6 June 2020


of $ n $ elements

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

Usually, one takes as the elements to be permuted the elements of the set $ \mathbf Z _ {n} = \{ 1 \dots n \} $; a one-to-one mapping $ \pi $ of $ \mathbf Z _ {n} $ onto itself defines the permutation $ \overline \pi \; = ( \pi ( 1) \dots \pi ( n)) $. The mapping $ \pi $ is also called a substitution of $ \mathbf Z _ {n} $. 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 $ \overline \pi \; $ can be regarded as an ordered set consisting of $ n $ elements if one assumes that $ \pi ( i) $ precedes $ \pi ( i+ 1) $, $ i = 1 \dots n $.

Examples. 1) The pair $ \{ \pi ( i) , \pi ( j) \} $ forms an inversion in $ \overline \pi \; $ if $ \pi ( i) > \pi ( j) $ for $ i < j $; if $ a _ {r} $ is the number of permutations of $ n $ elements with $ r $ inversions, then

$$ \sum _ { r= } 0 ^ { \left ( \begin{array}{c} n \\ 2 \end{array} \right ) } a _ {r} x ^ {r} = \ \frac{( 1- x) \dots ( 1- x ^ {n} ) }{( 1- x) ^ {n} } . $$

2) If $ b _ {n} $ is the number of permutations $ \overline \pi \; $ consisting of $ n $ elements such that $ \pi ( i) > \pi ( i- 1) $ for $ i $ even and $ \pi ( i) < \pi ( i- 1) $ for $ i $ odd, then

$$ \sum _ { n= } 0 ^ \infty b _ {n} \frac{x ^ {n} }{n!} = \mathop{\rm tan} x + \mathop{\rm sec} x. $$

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=16301
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article