Namespaces
Variants
Actions

Difference between revisions of "Permutation of a set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (links)
 
(3 intermediate revisions by one other user not shown)
Line 1: Line 1:
A one-to-one mapping of a set onto itself. The term permutation is used mainly for a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p0722901.png" />. In that case it is convenient to assume that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p0722902.png" /> and to write the permutation in the form
+
{{MSC|20}}
 +
{{TEX|done}}
  
<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/p072290/p0722903.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
 
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p0722904.png" /> is a certain [[Permutation|permutation]] of the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p0722905.png" />. The notation (*) means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p0722906.png" /> transforms the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p0722907.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p0722908.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p0722909.png" /> (one writes also <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229010.png" />) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229011.png" />. The number of different permutations of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229012.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229013.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229014.png" />. The product of the permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229016.png" /> of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229017.png" /> is defined as the successive application of the mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229019.png" />, and is given by the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229020.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229021.png" />. The set of all permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229022.png" /> forms a [[Group|group]] with respect to this multiplication, called the [[Symmetric group|symmetric group]]. Any subgroup of a symmetric group is called a [[Permutation group|permutation group]].
+
A permutation is  
 +
a one-to-one mapping of a set onto itself. The term permutation is used mainly for a finite set $X$. In that case it is convenient to assume that $X=\{1,\dots,n\}$ and to write the permutation in the form
  
The symmetric group of permutations of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229023.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229024.png" />, and it contains as a subgroup <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229025.png" />, the group consisting of those permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229026.png" /> which displace only a finite subset of elements (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229027.png" /> only for a finite set of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229028.png" />). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229029.png" /> is finite and consists of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229030.png" /> elements, the symmetric group is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229031.png" />.
+
$$\def\g{\gamma}\g = \begin{pmatrix}1&\dots&n\\i_1&\dots&i_n\end{pmatrix},\tag{$*$}$$
 +
where $i_1,\dots,i_n$ is a certain
 +
[[Permutation|permutation]] of the numbers $1,\dots,n$. The notation (*) means that $\g$ transforms the number $k$ into $i_k$, i.e. $\g(k) = i_k$ (one writes also $k^\g = i_k$) for $i=1,\dots,n$. The number of different permutations of a set $X$ with $|X|=n$ is equal to $n!$. The product of the permutations $\def\a{\alpha}\a$ and $\def\b{\beta}\b$ of a set $X$ is defined as the successive application of the mappings $\a$ and $\b$, and is given by the formula $\a\b(x) = \a(\b(x))$ for all $x\in X$.  
 +
(In the notation $x^\g$, the expression $x^{\a\b}$ is to be read as $(x^\a)^\b$, i.e. first $\a$, then $\b$.)
  
A transposition is a permutation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229032.png" /> that displaces only two elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229034.png" />; it is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229035.png" />. In <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229036.png" /> there are precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229037.png" /> transpositions. Any permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229038.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229039.png" /> can be written as a product of transpositions. In particular, each permutation in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229040.png" /> is a product of transpositions. A permutation can be written as a product of transpositions in many ways. However, for a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229041.png" /> the parity of the number of factors in a decomposition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229042.png" /> into transpositions is independent of the method of decomposing it. A permutation representable as a product of an even number of transpositions is called even, while one that decomposes as a product of an odd number of transpositions is called odd. In <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229043.png" /> there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229044.png" /> even permutations and the same number of odd ones. If a permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229045.png" /> is written in the form (*), its parity coincides with the parity of the number of inversions in the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229046.png" />, i.e. it is equal to the number of pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229047.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229049.png" />. A transposition is clearly an odd permutation. Composing a permutation with a single transposition alters the parity of the number of inversions. The product of two even permutations, and also of two odd ones, is an even permutation, while the product of an even and an odd permutation (in either order) is odd. The even permutations constitute a [[Normal subgroup|normal subgroup]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229050.png" /> in the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229051.png" />, called the alternating group. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229052.png" />, the subgroup <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229053.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229054.png" />.
+
The set of all permutations of $X$ forms a
 +
[[Group|group]] with respect to this multiplication, called the
 +
[[Symmetric group|symmetric group]]. Any subgroup of a symmetric group is called a
 +
[[Permutation group|permutation group]].
  
A cycle of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229056.png" /> is a permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229057.png" /> of a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229058.png" /> such that
+
The symmetric group of permutations of a set $X$ is denoted by $S(X)$, and it contains as a subgroup $SF(X)$, the group consisting of those permutations $\g$ which displace only a finite subset of elements (i.e. $\g(x)\ne x$ only for a finite set of elements $x\in X$). If $X$ is finite and consists of $n$ elements, the symmetric group is denoted by $S_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/p072290/p07229059.png" /></td> </tr></table>
+
A transposition is a permutation of $X$ that displaces only two elements $i$ and $j$; it is denoted by $(i,j)$. In $S_n$ there are precisely $n(n-1)/2$ transpositions. Any permutation $\g\in SF(X)$ in $S_n$ can be written as a product of transpositions. In particular, each permutation in $S_n$ is a product of transpositions. A permutation can be written as a product of transpositions in many ways. However, for a given $\g$ the parity of the number of factors in a decomposition of $\g$ into transpositions is independent of the method of decomposing it. A permutation representable as a product of an even number of transpositions is called even, while one that decomposes as a product of an odd number of transpositions is called odd. In $S_n$ there are $n!/2$ even permutations and the same number of odd ones. If a permutation $\g\in S_n$ is written in the form (*), its parity coincides with the parity of the number of inversions in the permutation $i_1,\dots,i_n$, i.e. it is equal to the number of pairs $\{i_k,i_j\}$ such that $k<j$, $i_k>i_j$. A transposition is clearly an odd permutation. Composing a permutation with a single transposition alters the parity of the number of inversions. The product of two even permutations, and also of two odd ones, is an even permutation, while the product of an even and an odd permutation (in either order) is odd. The even permutations constitute a [[normal subgroup]] $A(X)$ in the group $SF(X)$, called the ''[[alternating group]]''. For $|X|=n$, the subgroup $A(X)$ is denoted by $A_n$.
  
A finite cycle is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229060.png" />. An infinite cycle is a permutation of a countable set, of the form
+
A cycle of length $l$ is a permutation $\def\s{\sigma}\s$ of a finite set $Y=\{y_1,\dots,y_l\}$ such that
  
<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/p072290/p07229061.png" /></td> </tr></table>
+
$$\s(y_1) = y_2,\dots,\s(y_{l-1}) = y_l,\s(y_l) = y_1.$$
 +
A finite cycle is denoted by $(y_1,\dots,y_l)$. An infinite cycle is a permutation of a countable set, of the form
  
where for any integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229063.png" />. The symbol for an infinite cycle is:
+
$$Y=\{\dots,y_{-2},y_{-1},y_0,y_1,y_2,\dots\}$$
 +
where for any integer $i$, $\s(y_i) = y_{i+1}$. The symbol for an infinite cycle is:
  
<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/p072290/p07229064.png" /></td> </tr></table>
+
$$(\dots,y_{-2},y_{-1},y_0,y_1,y_2,\dots).$$
 +
A cycle of length 2 is a transposition. The group $S_n$ contains $(n-1)!$ cycles of length $n$. For any permutation $\g$ from $S(X)$ there exists a decomposition of $X$ into non-intersecting subsets such that on each of them $\g$ acts as a cycle. The finite subsets in this decomposition take the form
  
A cycle of length 2 is a transposition. The group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229065.png" /> contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229066.png" /> cycles of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229067.png" />. For any permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229068.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229069.png" /> there exists a decomposition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229070.png" /> into non-intersecting subsets such that on each of them <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229071.png" /> acts as a cycle. The finite subsets in this decomposition take the form
+
$$\{x,\g(x),\dots,\g^{l-1}(x)\},$$
 +
where $\g^l(x) = x$, while the infinite ones take the form
  
<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/p072290/p07229072.png" /></td> </tr></table>
+
$$\{\dots,\g^{-2},\g^{-1},x,\g(x),\g^2(x),\dots\},$$
 +
where $\g^k(x) \ne x$ for $k\ne 0$. The cycles induced by $\g$ on the subsets of the decomposition are called disjoint cycles of the permutation $\g$. For example, $(1,3,4)$ and $(2,5)$ are disjoint cycles of the permutation
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229073.png" />, while the infinite ones take the form
+
$$\g = \begin{pmatrix}1&2&3&4&5\\3&5&4&1&2\end{pmatrix};$$
 +
and $\g$ is written in the form
  
<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/p072290/p07229074.png" /></td> </tr></table>
+
$$(1,3,4)(2,5)$$
 +
as the product of its disjoint cycles. In general, if $\g$ is not the identity permutation and has only a finite number of cycles of length greater than one, then $\g$ is the product of such cycles. In particular, each non-identity permutation from $SF(X)$ is the product of its disjoint cycles of length greater than one. The order of a permutation $\g$ from $SF(X)$, i.e. the order of the
 +
[[cyclic group]] $\langle \g\rangle$, is equal to the lowest common multiple of the lengths of its disjoint cycles.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229075.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229076.png" />. The cycles induced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229077.png" /> on the subsets of the decomposition are called disjoint cycles of the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229078.png" />. For example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229079.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229080.png" /> are disjoint cycles of the permutation
+
From the disjoint cycles of a given permutation one can obtain the disjoint cycles of any permutation conjugate with it (cf.
 +
[[Conjugate elements]]). For example, if
  
<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/p072290/p07229081.png" /></td> </tr></table>
+
$$\g = (a_1,\dots,a_l)\dots(a_j,\dots,a_n)$$
 +
is the product of the disjoint cycles of the permutation $\g$ from $S_n$, if $\def\d{\delta}\d\in S_n$ and if $\d(a_i)=b_i$, $i=1,\dots,n$, then
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229082.png" /> is written in the form
+
$$\d\g\d^{-1} = (b_1,\dots,b_l)\dots(b_j,\dots,b_n)$$
 +
is the decomposition of the permutation $\d\g\d^{-1}$ as a product of disjoint cycles. Two permutations of the group $S_n$ are conjugate in $S_n$ if and only if they have the same number of disjoint cycles of each length.
  
<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/p072290/p07229083.png" /></td> </tr></table>
+
Let $s\in S_n$ and let $k$ be the number of independent cycles of $s$, including cycles of length 1. Then the difference $n-k$ is called the decrement of the permutation $s$. The least number of factors in a decomposition of the permutation $s$ as a product of transpositions coincides with its decrement. The parity of a permutation coincides with the parity of its decrement.
  
as the product of its disjoint cycles. In general, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229084.png" /> is not the identity permutation and has only a finite number of cycles of length greater than one, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229085.png" /> is the product of such cycles. In particular, each non-identity permutation from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229086.png" /> is the product of its disjoint cycles of length greater than one. The order of a permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229087.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229088.png" />, i.e. the order of the [[Cyclic group|cyclic group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229089.png" />, is equal to the lowest common multiple of the lengths of its disjoint cycles.
+
Permutations arose originally in combinatorics in the 18th century. At the end of the 18th century, J.L. Lagrange applied them in his research on the solvability of algebraic equations by radicals. A.L. Cauchy gave much attention to this topic, and was responsible, in particular, for the idea of expressing a permutation as a product of cycles. Research on the group properties of permutations has been carried out by N.H. Abel and, particularly, by E. Galois. See [[Galois theory]] and [[Permutation group]].
 
 
From the disjoint cycles of a given permutation one can obtain the disjoint cycles of any permutation conjugate with it (cf. [[Conjugate elements|Conjugate elements]]). For example, if
 
 
 
<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/p072290/p07229090.png" /></td> </tr></table>
 
 
 
is the product of the disjoint cycles of the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229091.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229092.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229093.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229094.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229095.png" />, 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/p072290/p07229096.png" /></td> </tr></table>
 
 
 
is the decomposition of the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229097.png" /> as a product of disjoint cycles. Two permutations of the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229098.png" /> are conjugate in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p07229099.png" /> if and only if they have the same number of disjoint cycles of each length.
 
 
 
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290100.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290101.png" /> be the number of independent cycles of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290102.png" />, including cycles of length 1. Then the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290103.png" /> is called the decrement of the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290104.png" />. The least number of factors in a decomposition of the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290105.png" /> as a product of transpositions coincides with its decrement. The parity of a permutation coincides with the parity of its decrement.
 
 
 
Permutations arose originally in combinatorics in the 18th century. At the end of the 18th century, J.L. Lagrange applied them in his research on the solvability of algebraic equations by radicals. A.L. Cauchy gave much attention to this topic, and was responsible, in particular, for the idea of expressing a permutation as a product of cycles. Research on the group properties of permutations has been carried out by N.H. Abel and, particularly, by E. Galois. See [[Galois theory|Galois theory]] and [[Permutation group|Permutation group]].
 
 
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C. Jordan,  "Traité des substitutions et des équations algébriques" , Paris  (1957)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.I. Kostrikin,  "Introduction to algebra" , Springer  (1982)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.G. Kurosh,  "Higher algebra" , MIR  (1972)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  M. Hall,  "Group theory" , Macmillan  (1959)</TD></TR></table>
 
 
 
 
 
 
 
====Comments====
 
In the notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290106.png" />, the expression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290107.png" /> is to be read as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290108.png" />, i.e. first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290109.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072290/p072290110.png" />.
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> M. Suzuki,  "Group theory" , '''1–2''' , Springer  (1986)</TD></TR></table>
+
{|
 +
|-
 +
|valign="top"|{{Ref|Ha}}||valign="top"|  M. Hall,  "The theory of groups", Macmillan  (1959)    {{MR|0103215}}  {{ZBL|0084.02202}}
 +
|-
 +
|valign="top"|{{Ref|Jo}}||valign="top"|  C. Jordan,  "Traité des substitutions et des équations algébriques", Paris  (1957)  {{MR|0091260}}  {{ZBL|0078.01204}}   
 +
|-
 +
|valign="top"|{{Ref|Ko}}||valign="top"|  A.I. Kostrikin,  "Introduction to algebra", Springer  (1982)  (Translated from Russian)  {{MR|0661256}}  {{ZBL|0482.00001}}   
 +
|-
 +
|valign="top"|{{Ref|Ku}}||valign="top"|  A.G. Kurosh,  "Higher algebra", MIR  (1972)  (Translated from Russian)  {{ZBL|0237.13001}}   
 +
|-
 +
|valign="top"|{{Ref|Su}}||valign="top"| M. Suzuki,  "Group theory", '''1–2''', Springer  (1986) {{MR|0815926}}  {{ZBL|0586.20001}}   
 +
|-
 +
|}

Latest revision as of 20:15, 27 September 2016

2020 Mathematics Subject Classification: Primary: 20-XX [MSN][ZBL]


A permutation is a one-to-one mapping of a set onto itself. The term permutation is used mainly for a finite set $X$. In that case it is convenient to assume that $X=\{1,\dots,n\}$ and to write the permutation in the form

$$\def\g{\gamma}\g = \begin{pmatrix}1&\dots&n\\i_1&\dots&i_n\end{pmatrix},\tag{$*$}$$ where $i_1,\dots,i_n$ is a certain permutation of the numbers $1,\dots,n$. The notation (*) means that $\g$ transforms the number $k$ into $i_k$, i.e. $\g(k) = i_k$ (one writes also $k^\g = i_k$) for $i=1,\dots,n$. The number of different permutations of a set $X$ with $|X|=n$ is equal to $n!$. The product of the permutations $\def\a{\alpha}\a$ and $\def\b{\beta}\b$ of a set $X$ is defined as the successive application of the mappings $\a$ and $\b$, and is given by the formula $\a\b(x) = \a(\b(x))$ for all $x\in X$. (In the notation $x^\g$, the expression $x^{\a\b}$ is to be read as $(x^\a)^\b$, i.e. first $\a$, then $\b$.)

The set of all permutations of $X$ forms a group with respect to this multiplication, called the symmetric group. Any subgroup of a symmetric group is called a permutation group.

The symmetric group of permutations of a set $X$ is denoted by $S(X)$, and it contains as a subgroup $SF(X)$, the group consisting of those permutations $\g$ which displace only a finite subset of elements (i.e. $\g(x)\ne x$ only for a finite set of elements $x\in X$). If $X$ is finite and consists of $n$ elements, the symmetric group is denoted by $S_n$.

A transposition is a permutation of $X$ that displaces only two elements $i$ and $j$; it is denoted by $(i,j)$. In $S_n$ there are precisely $n(n-1)/2$ transpositions. Any permutation $\g\in SF(X)$ in $S_n$ can be written as a product of transpositions. In particular, each permutation in $S_n$ is a product of transpositions. A permutation can be written as a product of transpositions in many ways. However, for a given $\g$ the parity of the number of factors in a decomposition of $\g$ into transpositions is independent of the method of decomposing it. A permutation representable as a product of an even number of transpositions is called even, while one that decomposes as a product of an odd number of transpositions is called odd. In $S_n$ there are $n!/2$ even permutations and the same number of odd ones. If a permutation $\g\in S_n$ is written in the form (*), its parity coincides with the parity of the number of inversions in the permutation $i_1,\dots,i_n$, i.e. it is equal to the number of pairs $\{i_k,i_j\}$ such that $k<j$, $i_k>i_j$. A transposition is clearly an odd permutation. Composing a permutation with a single transposition alters the parity of the number of inversions. The product of two even permutations, and also of two odd ones, is an even permutation, while the product of an even and an odd permutation (in either order) is odd. The even permutations constitute a normal subgroup $A(X)$ in the group $SF(X)$, called the alternating group. For $|X|=n$, the subgroup $A(X)$ is denoted by $A_n$.

A cycle of length $l$ is a permutation $\def\s{\sigma}\s$ of a finite set $Y=\{y_1,\dots,y_l\}$ such that

$$\s(y_1) = y_2,\dots,\s(y_{l-1}) = y_l,\s(y_l) = y_1.$$ A finite cycle is denoted by $(y_1,\dots,y_l)$. An infinite cycle is a permutation of a countable set, of the form

$$Y=\{\dots,y_{-2},y_{-1},y_0,y_1,y_2,\dots\}$$ where for any integer $i$, $\s(y_i) = y_{i+1}$. The symbol for an infinite cycle is:

$$(\dots,y_{-2},y_{-1},y_0,y_1,y_2,\dots).$$ A cycle of length 2 is a transposition. The group $S_n$ contains $(n-1)!$ cycles of length $n$. For any permutation $\g$ from $S(X)$ there exists a decomposition of $X$ into non-intersecting subsets such that on each of them $\g$ acts as a cycle. The finite subsets in this decomposition take the form

$$\{x,\g(x),\dots,\g^{l-1}(x)\},$$ where $\g^l(x) = x$, while the infinite ones take the form

$$\{\dots,\g^{-2},\g^{-1},x,\g(x),\g^2(x),\dots\},$$ where $\g^k(x) \ne x$ for $k\ne 0$. The cycles induced by $\g$ on the subsets of the decomposition are called disjoint cycles of the permutation $\g$. For example, $(1,3,4)$ and $(2,5)$ are disjoint cycles of the permutation

$$\g = \begin{pmatrix}1&2&3&4&5\\3&5&4&1&2\end{pmatrix};$$ and $\g$ is written in the form

$$(1,3,4)(2,5)$$ as the product of its disjoint cycles. In general, if $\g$ is not the identity permutation and has only a finite number of cycles of length greater than one, then $\g$ is the product of such cycles. In particular, each non-identity permutation from $SF(X)$ is the product of its disjoint cycles of length greater than one. The order of a permutation $\g$ from $SF(X)$, i.e. the order of the cyclic group $\langle \g\rangle$, is equal to the lowest common multiple of the lengths of its disjoint cycles.

From the disjoint cycles of a given permutation one can obtain the disjoint cycles of any permutation conjugate with it (cf. Conjugate elements). For example, if

$$\g = (a_1,\dots,a_l)\dots(a_j,\dots,a_n)$$ is the product of the disjoint cycles of the permutation $\g$ from $S_n$, if $\def\d{\delta}\d\in S_n$ and if $\d(a_i)=b_i$, $i=1,\dots,n$, then

$$\d\g\d^{-1} = (b_1,\dots,b_l)\dots(b_j,\dots,b_n)$$ is the decomposition of the permutation $\d\g\d^{-1}$ as a product of disjoint cycles. Two permutations of the group $S_n$ are conjugate in $S_n$ if and only if they have the same number of disjoint cycles of each length.

Let $s\in S_n$ and let $k$ be the number of independent cycles of $s$, including cycles of length 1. Then the difference $n-k$ is called the decrement of the permutation $s$. The least number of factors in a decomposition of the permutation $s$ as a product of transpositions coincides with its decrement. The parity of a permutation coincides with the parity of its decrement.

Permutations arose originally in combinatorics in the 18th century. At the end of the 18th century, J.L. Lagrange applied them in his research on the solvability of algebraic equations by radicals. A.L. Cauchy gave much attention to this topic, and was responsible, in particular, for the idea of expressing a permutation as a product of cycles. Research on the group properties of permutations has been carried out by N.H. Abel and, particularly, by E. Galois. See Galois theory and Permutation group.

References

[Ha] M. Hall, "The theory of groups", Macmillan (1959) MR0103215 Zbl 0084.02202
[Jo] C. Jordan, "Traité des substitutions et des équations algébriques", Paris (1957) MR0091260 Zbl 0078.01204
[Ko] A.I. Kostrikin, "Introduction to algebra", Springer (1982) (Translated from Russian) MR0661256 Zbl 0482.00001
[Ku] A.G. Kurosh, "Higher algebra", MIR (1972) (Translated from Russian) Zbl 0237.13001
[Su] M. Suzuki, "Group theory", 1–2, Springer (1986) MR0815926 Zbl 0586.20001
How to Cite This Entry:
Permutation of a set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Permutation_of_a_set&oldid=14475
This article was adapted from an original article by D.A. Suprunenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article