Namespaces
Variants
Actions

Difference between revisions of "Permutation"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
(latex details)
 
Line 15: Line 15:
  
 
A finite sequence of length  $  n $
 
A finite sequence of length  $  n $
in which all the elements are different, i.e. a permutation is an [[Arrangement|arrangement]] of  $  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! $.
 
elements without repetition. The number of permutations is  $  n! $.
  
Line 40: Line 40:
  
 
$$  
 
$$  
\sum _ { r= } 0 ^ {  \left  ( \begin{array}{c}
+
\sum _ {r=0} ^ {  \left  ( \begin{array}{c}
 
n \\
 
n \\
 
  2  
 
  2  
Line 60: Line 60:
  
 
$$  
 
$$  
\sum _ { n= } 0 ^  \infty  b _ {n}  
+
\sum _{n=0} ^  \infty  b _ {n} \frac{x  ^ {n} }{n!}
\frac{x  ^ {n} }{n!}
 
 
   =  \mathop{\rm tan}  x +  \mathop{\rm sec}  x.
 
   =  \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]]).
 
 
====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>
 
  
 
====Comments====
 
====Comments====
 
See also [[Permutation group|Permutation group]].
 
See also [[Permutation group|Permutation group]].
 +
 +
====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>

Latest revision as of 17:40, 6 January 2024


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).

Comments

See also Permutation group.

References

[1] V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[2] J. Riordan, "An introduction to combinational analysis" , Wiley (1958)
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