permutation

All six permutations of three colored balls

Under a permutation (from latin permutare , reverse ' ) is understood in the combinatorics an arrangement of objects in a specific order . Depending on whether or not certain objects are allowed to appear several times, one speaks of a permutation with repetition or a permutation without repetition. The number of permutations without repetition results as a factorial , while the number of permutations with repetition is given via multinomial coefficients .

In group theory , a permutation without repetition is a bijective self-mapping of a usually finite set , whereby the first natural numbers are usually used as reference sets. The set of permutations of the first natural numbers forms the symmetrical group of degree with the consecutive execution as a link . The neutral element of this group represents the identical permutation, while the inverse element is the inverse permutation. The subgroups of the symmetric group are the permutation groups . ${\displaystyle n}$ ${\displaystyle n}$

Important parameters of permutations are their cycle type , their order and their sign . With the help of the missing positions of a permutation, a partial order can be defined on the set of permutations of fixed length . Using its inversion table , each permutation can also be assigned a unique number in a faculty-based number system . Important classes of permutations are cyclic , fixed-point-free , self-inverse and alternating permutations .

Permutations have a wide range of uses within and outside of mathematics , for example in linear algebra ( Leibniz formula ), analysis ( rearrangement of rows ), graph theory and game theory , cryptography ( encryption method ) , computer science ( sorting method ) and quantum mechanics ( Pauli Principle ).

Combinatorial basics

Permutations of four colored balls without repetition (left) and with repetition (middle and right).

Problem

A permutation is an arrangement of objects in a certain order or a rearrangement of objects from a given order. Examples of permutations are:

• An anagram is a permutation of the letters in a word, such as GRANDSON and CARNATION.
• The shuffling of the cards in a deck of cards is (ideally) a random permutation of the cards.
• In volleyball , changing position after conquering the right to serve is a cyclical permutation of the players.
• Many sorting methods work with successive transpositions, i.e. permutations that exchange exactly two objects.

If not all objects are selected in such an arrangement, one speaks of a variation instead of a permutation ; the sequence in the selection does not matter, of a combination . In counting combinatorics , the question of the number of possible permutations arises. A distinction is made here between the case that all objects are different and the case that some of the objects are identical.

Permutation without repetition

A permutation without repetition is an arrangement of objects that are all distinguishable. Since there are placement options for the first object, there are only options for the second object , for the third object only and so on up to the last object, which only has a free space. The number of possible permutations of objects is therefore given by the factorial ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-2}$ ${\displaystyle n}$

${\displaystyle n!=n\cdot (n-1)\cdot (n-2)\cdot \ldots \cdot 1}$

specified.

For example, there are possible arrangements of four different colored balls in a row. ${\displaystyle 4!=4\cdot 3\cdot 2\cdot 1=24}$

Permutation with repetition

A permutation with repetition is an arrangement of objects, some of which are indistinguishable. If exactly the objects are identical, they can be exchanged in their places without resulting in a new order. In this way, arrangements are exactly the same. The number of permutations of objects, of which are identical, is therefore given by the decreasing factorial ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k!}$ ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle {\frac {n!}{k!}}=n\cdot (n-1)\cdot \ldots \cdot (k+1)=n^{\underline {n-k}}}$

given. If there is not just one, but groups with identical objects, then all of these objects can be exchanged in their places without creating new arrangements. If one also counts the objects that only occur once with a multiplicity , then the following applies and the number of possible permutations is given by the multinomial coefficient ${\displaystyle s}$ ${\displaystyle k_{1},\ldots ,k_{s}}$ ${\displaystyle 1}$ ${\displaystyle k_{1}+\ldots +k_{s}=n}$

${\displaystyle {\frac {n!}{k_{1}!\cdot \ldots \cdot k_{s}!}}={\binom {n}{k_{1},\ldots ,k_{s}}}}$

specify.

For example, there are possible arrangements of four colored balls in a row if exactly two of the balls have the same color, and possible arrangements if two balls are each of the same color . ${\displaystyle {\tfrac {4!}{2!\,1!\,1!}}={\tfrac {24}{2}}=12}$ ${\displaystyle {\tfrac {4!}{2!\,2!}}={\tfrac {24}{4}}=6}$

definition

Let be a set with elements , then a -digit permutation (without repetition) is a bijective map ${\displaystyle X=\{x_{1},x_{2},\ldots ,x_{n}\}}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle \pi \colon X\rightarrow X}$,

which assigns an element of the same set to each element of the set. Vividly takes each element of the permutation for the place of its associated element one. Due to the bijectivity of the mapping, two different elements are never mapped onto the same element. The case is also admissible and is then the empty set . ${\displaystyle x_{i}}$ ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle \pi (x_{i})}$ ${\displaystyle n=0}$ ${\displaystyle X}$

Since, by definition, every finite set is equal to a set of the form {1, 2, ..., n} , one can always restrict oneself to the first natural numbers as a reference set when considering permutations mathematically . A permutation is then a bijective mapping ${\displaystyle n}$

${\displaystyle \pi \colon \{1,2,\ldots ,n\}\rightarrow \{1,2,\ldots ,n\}}$,

which assigns every natural number between and exactly one number in the same range. If you imagine all the numbers in a list, then the number takes the place with the number through the permutation . ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle j\in \{1,\ldots ,n\}}$ ${\displaystyle \pi (j)}$

notation

Two-line form

In the detailed representation of a -digit permutation , this is written as a matrix with two rows and columns. In the top line are the numbers from to (in any order). The function value is then located under each number in the second line : ${\displaystyle n}$ ${\displaystyle \pi }$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle j\in \{1,\ldots ,n\}}$ ${\displaystyle \pi (j)}$

${\displaystyle \pi ={\begin{pmatrix}1&2&\cdots &n\\\pi \left(1\right)&\pi \left(2\right)&\cdots &\pi \left(n\right)\end{pmatrix}}}$

The second line also contains every number from to exactly once. ${\displaystyle 1}$ ${\displaystyle n}$

example

The permutation with and is in the two-line form by ${\displaystyle \pi \colon \{1,2,3,4\}\rightarrow \{1,2,3,4\}}$ ${\displaystyle \pi (1)=2,\pi (2)=4,\pi (3)=3}$ ${\displaystyle \pi (4)=1}$

${\displaystyle \pi ={\begin{pmatrix}1&2&3&4\\2&4&3&1\end{pmatrix}}}$

written down.

Tuple notation

With the more compact tuple notation, you just write the function values in one line: ${\displaystyle \pi (j)}$

${\displaystyle \pi =\left(\pi (1),\pi (2),\dotsc ,\pi (n)\right)}$

This notation therefore only uses the second line of the two-line form. Since the information about the number that is mapped to is lost, the tuple notation can only be used if the order of the numbers from the first line is known. Usually this is the natural order. The tuple notation can easily be confused with the cycle notation (see following section), especially since some authors leave out the commas. ${\displaystyle j}$ ${\displaystyle \pi (j)}$

example

The tuple notation is used for the above example permutation

${\displaystyle \pi =(2,~4,~3,~1)}$.

Cycle notation

The cycle notation also only requires one line. You start with any number and write ${\displaystyle a\in \{1,\ldots ,n\}}$

${\displaystyle \left(a\;\pi (a)\;\pi ^{2}(a)\;\cdots \;\pi ^{\ell _{a}-1}(a)\right)}$,

where the -fold execution of denotes and the smallest natural number is with . Such a bracket is called a cycle and is its length. If there are other numbers that have not yet been noted, choose such a number and write another cycle of length after it. You go on until you write down each number exactly once. Brackets containing only one number can then be deleted again. This representation is not clear, because the order of the cycles can be selected as desired and the numbers can be interchanged cyclically in each cycle. ${\displaystyle \pi ^{k}}$ ${\displaystyle k}$ ${\displaystyle \pi }$ ${\displaystyle \ell _{a}}$ ${\displaystyle \pi ^{\ell _{a}}(a)=a}$ ${\displaystyle \ell _{a}}$ ${\displaystyle b}$ ${\displaystyle (b\;\pi (b)\;\cdots \;\pi ^{\ell _{b}-1}(b))}$ ${\displaystyle \ell _{b}}$

example

The following cycle notation is used for the above example permutation:

${\displaystyle \pi =(1~2~4)(3)=(1~2~4)=(2~4~1)=(4~1~2)}$

Further representations

Graph representation

Graph of the permutation ${\displaystyle (1~2~4~3)(5)(6~7)}$

The graph of a -digit permutation is a directed graph with a set of nodes and a set of edges ${\displaystyle n}$ ${\displaystyle \pi }$ ${\displaystyle (V,E)}$ ${\displaystyle V=\{1,2,\ldots ,n\}}$

${\displaystyle E=\{(i,\pi (i))\mid i=1,\ldots ,n\}}$.

In such a graph, each node has exactly one outgoing and exactly one incoming edge. The cycles of the graph are precisely the cycles of the permutation, with the numbers that are held by the permutation creating loops at the associated nodes. The graph of a permutation is only connected if the permutation consists of a single cycle of length . ${\displaystyle n}$

Permutation matrices

${\displaystyle {\begin{pmatrix}0&1&0&0\\0&0&0&1\\0&0&1&0\\1&0&0&0\\\end{pmatrix}}}$ Permutation matrix of the permutation ${\displaystyle (2,4,3,1)}$

→ Main article : permutation matrix

The permutation matrix of a -digit permutation is given by ${\displaystyle P_{\pi }\in \{0,1\}^{n\times n}}$ ${\displaystyle n}$ ${\displaystyle \pi }$

${\displaystyle P_{\pi }={\begin{pmatrix}p_{11}&\dots &p_{1n}\\\vdots &\ddots &\vdots \\p_{n1}&\dots &p_{nn}\end{pmatrix}}\quad {\text{ mit }}\quad p_{ij}={\begin{cases}1,&{\text{falls }}\pi (i)=j\\0,&{\text{sonst}}\end{cases}}}$

Are defined. If the number is mapped onto the number by a permutation , then the associated permutation matrix in the -th row has one in the column . The elements of a column vector are in linear algebra permuted characterized in that the vector from the left by the permutation matrix multiplied is: ${\displaystyle i}$ ${\displaystyle \pi (i)}$ ${\displaystyle i}$ ${\displaystyle 1}$ ${\displaystyle \pi (i)}$ ${\displaystyle (x_{1},\dotsc ,x_{n})^{T}}$ ${\displaystyle P_{\pi }}$

${\displaystyle (x_{\pi (1)},\ldots ,x_{\pi (n)})^{T}=P_{\pi }\cdot (x_{1},\dotsc ,x_{n})^{T}}$.

Permutations as a group

The permutations of the set form a group with the sequential execution as a link , the symmetrical group . The symmetrical groups play an important role in mathematics. For example, according to Cayley's theorem, every finite group is isomorphic to a subgroup of a symmetric group . The subgroups of the symmetric group are called permutation groups . ${\displaystyle \{1,2,\dotsc ,n\}}$ ${\displaystyle S_{n}}$

The Galois group in (classical) Galois theory is such a subgroup of the symmetrical group: The zeros of polynomials are permuted . The properties of the Galois group provide information about the solvability of a polynomial equation by radicals, i.e. H. by root expressions. This can be used to prove, for example, that the general polynomial equation of the fifth or higher degree cannot be solved by radicals ( Abel-Ruffini theorem ).

composition

Two -digit permutations can be carried out one after the other by first applying the first permutation and then applying the second permutation to the result. The sequential execution is written as ${\displaystyle n}$ ${\displaystyle \pi ,\tau \in S_{n}}$

${\displaystyle \tau \circ \pi }$,

applying first and then . This sequential execution is also called composition , linkage or product of two permutations and the result is again a -digit permutation. The composition of permutations is not commutative , that is, in general, and give different results. The symmetric group is therefore not Abelian . However, the composition is associative, i.e. it applies to all permutations ${\displaystyle \pi }$ ${\displaystyle \tau }$ ${\displaystyle n}$ ${\displaystyle \tau \circ \pi }$ ${\displaystyle \pi \circ \tau }$ ${\displaystyle S_{n}}$ ${\displaystyle n>2}$ ${\displaystyle \pi ,\tau ,\sigma \in S_{n}}$

${\displaystyle \sigma \circ (\tau \circ \pi )=(\sigma \circ \tau )\circ \pi }$.

Examples

It is for example

${\displaystyle {\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}\circ {\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}}={\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}}$.

To get the result, you apply the permutations from right to left and follow the path of the individual numbers. This is mapped to itself in the second permutation and then to the , that is , as a whole in the first permutation . The way is corresponding , so . The finally goes the way , in the result . ${\displaystyle 1}$ ${\displaystyle 3}$ ${\displaystyle 1\mapsto 1\mapsto 3}$ ${\displaystyle 1\mapsto 3}$ ${\displaystyle 2}$ ${\displaystyle 2\mapsto 3\mapsto 2}$ ${\displaystyle 2\mapsto 2}$ ${\displaystyle 3}$ ${\displaystyle 3\mapsto 2\mapsto 1}$ ${\displaystyle 3\mapsto 1}$

The cycle display is analogous, whereby numbers that do not appear in a cycle are recorded. For example is

${\displaystyle (1~2~3)\circ (2~3~4)={\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}}=(1~2)(3~4)}$.

Here we determined the paths , , and . ${\displaystyle 1\mapsto 1\mapsto 2}$ ${\displaystyle 2\mapsto 3\mapsto 1}$ ${\displaystyle 3\mapsto 4\mapsto 4}$ ${\displaystyle 4\mapsto 2\mapsto 3}$

Identical permutation

The neutral element of the symmetric group is the identical permutation ${\displaystyle S_{n}}$

${\displaystyle \operatorname {id} ={\begin{pmatrix}1&2&3&\ldots &n\\1&2&3&\ldots &n\end{pmatrix}}\in S_{n}}$,

that is, the permutation that leaves all numbers in their place. So for every permutation ${\displaystyle \pi \in S_{n}}$

${\displaystyle \operatorname {id} \circ \,\pi =\pi \circ \operatorname {id} =\pi }$.

The identical permutation is also noted as empty brackets , as or as . The permutation matrix of the identical permutation is the identity matrix . The identical permutation graph has only one loop at each node. The identical permutation of length one is also known as the trivial permutation. ${\displaystyle ()}$ ${\displaystyle (1)}$ ${\displaystyle \epsilon }$

Inverse permutation

For every permutation there is exactly one inverse element , the inverse permutation , with ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \pi ^{-1}}$

${\displaystyle \pi \circ \pi ^{-1}=\pi ^{-1}\circ \pi =\operatorname {id} }$.

The inverse permutation is obtained by exchanging the upper and lower lines in the two-line form:

${\displaystyle \pi ^{-1}={\begin{pmatrix}\pi \left(1\right)&\pi \left(2\right)&\cdots &\pi \left(n\right)\\1&2&\cdots &n\end{pmatrix}}}$

In the cycle notation, the inverse permutation is obtained by writing the numbers in the reverse order in each cycle. In the graph of the inverse permutation, only the directions of all edges are reversed. The permutation matrix of the inverse permutation is the transposed matrix of the initial permutation .

example

The inverse permutation to

${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\2&4&5&1&3\end{pmatrix}}=(1~2~4)(3~5)}$

is

${\displaystyle \pi ^{-1}={\begin{pmatrix}2&4&5&1&3\\1&2&3&4&5\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\4&1&5&2&3\end{pmatrix}}=(4~2~1)(5~3)}$.

conjugation

Two permutations are said to be conjugated to each other if a permutation exists such that ${\displaystyle \sigma ,\pi \in S_{n}}$ ${\displaystyle \tau \in S_{n}}$

${\displaystyle \sigma =\tau \circ \pi \circ \tau ^{-1}}$   or.   ${\displaystyle \sigma \circ \tau =\tau \circ \pi }$

applies. Is the permutation the number to the number displayed, then the permutation is the number to the number from. The conjugation represents an equivalence relation on the set of permutations of fixed length, that is, it is reflexive ( ), symmetric (from follows ) and transitive (from and follows ). The set of all permutations conjugated to a permutation form an equivalence class (the conjugation class ), which is noted by. ${\displaystyle \pi }$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \sigma }$ ${\displaystyle \tau (i)}$ ${\displaystyle \tau (j)}$ ${\displaystyle \sim }$ ${\displaystyle \pi \sim \pi }$ ${\displaystyle \pi \sim \sigma }$ ${\displaystyle \sigma \sim \pi }$ ${\displaystyle \pi \sim \sigma }$ ${\displaystyle \sigma \sim \tau }$ ${\displaystyle \pi \sim \tau }$ ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \left[\pi \right]}$

example

The symmetrical group has the three conjugation classes: ${\displaystyle S_{3}}$

${\displaystyle [\operatorname {id} ]=\{\operatorname {id} \}}$

${\displaystyle [(1~2)]=\{(1~2),(1~3),(2~3)\}}$

${\displaystyle [(1~2~3)]=\{(1~2~3),(1~3~2)\}}$

Parameters

Cycle type

${\displaystyle n}$	Cycle type	Cycle structure	number
1	1 1	(•)	1
2	1 2	(•) (•)	1
	2 1	(• •)	1
3	1 3	(•) (•) (•)	1
	1 1 2 1	(• •) (•)	3
	3 1	(• • •)	2
4th	1 4	(•) (•) (•) (•)	1
	1 2 2 1	(• •) (•) (•)	6th
	2 2	(• •) (• •)	3
	1 1 3 1	(• • •) (•)	8th
	4 1	(• • • •)	6th

→ Main article : cycle type

Denoted for the number of cycles of the length in a permutation , then the cycle type of this permutation is the formal expression ${\displaystyle b_{j}}$ ${\displaystyle j=1,\ldots ,n}$ ${\displaystyle j}$ ${\displaystyle \pi \in S_{n}}$

${\displaystyle \operatorname {typ} (\pi )=1^{b_{1}}2^{b_{2}}\ldots n^{b_{n}}}$,

whereby the terms do not have to be listed with. Formal here means that the product and the potencies are not actually calculated. The number of possible cycle types with -digit permutations corresponds to the number of partitions of the number . The number of permutations per cycle type can be calculated from the type description. The inverse permutation always has the same cycle type as the initial permutation. In addition, the result of composing two permutations has the same cycle type regardless of the order of the operands. Accordingly, two permutations are conjugated to each other if and only if they are of the same cycle type. The permutations of the same cycle type therefore form the conjugation classes of the symmetrical group . The permutations with the same number of cycles are counted by the Stirling numbers of the first kind. ${\displaystyle b_{j}=0}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S_{n}}$

order

→ Main article : Element order

The order of a permutation is the smallest natural number in such a way that executing one after the other results in the identical permutation: ${\displaystyle \pi }$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \pi }$

${\displaystyle \operatorname {ord} (\pi )=\min\{k\in \mathbb {N} \mid \pi ^{k}=\operatorname {id} \}}$.

The order of a permutation is thus the element order of as a group element of the symmetrical group. From the cycle representation of a permutation, the order can be determined as the smallest common multiple of the lengths of the disjoint cycles. For example, the order of the permutation is the least common multiple of three and two, i.e. six. ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle (124)(35)}$

Deficiencies

Missing permutations in S ₃

No.	permutation	Deficiencies	number
0	(1,2,3)	-	0
1	(1,3,2)	(2.3)	1
2	(2,1,3)	(1.2)	1
3	(2,3,1)	(1.2), (1.3)	2
4th	(3.1.2)	(1.3), (2.3)	2
5	(3.2.1)	(1,2), (1,3), (2,3)	3

→ Main article : Absence

A pair of numbers is called an error or inversion of a permutation , if and applies. So two numbers form an error if and only if the larger one comes before the smaller one after applying the permutation. The set of deficiencies in a permutation is thus through ${\displaystyle (i,j)}$ ${\displaystyle \pi }$ ${\displaystyle i<j}$ ${\displaystyle \pi (i)>\pi (j)}$ ${\displaystyle \pi \in S_{n}}$

${\displaystyle \operatorname {inv} (\pi )=\left\{(i,j)\in \{1,\ldots ,n\}^{2}\mid i<j~{\text{und}}~\pi (i)>\pi (j)\right\}}$

given. The number of faults in a permutation is called the fault number or inversion number of the permutation. The missing number can be viewed as a measure of the disorder of the numbers swapped by the permutation. ${\displaystyle |\operatorname {inv} (\pi )|}$

sign

→ Main article : Sign (permutation)

The sign of a permutation is the number ${\displaystyle \pi \in S_{n}}$

${\displaystyle \operatorname {sgn} (\pi )=\left(-1\right)^{|\operatorname {inv} (\pi )|}}$.

A permutation thus has the sign if its missing number is even, otherwise the sign . In the first case one speaks of an even and in the second case of an odd permutation. The set of even permutations forms a subgroup of the symmetrical group , the alternating group . ${\displaystyle +1}$ ${\displaystyle -1}$ ${\displaystyle S_{n}}$ ${\displaystyle A_{n}}$

Ascents and descents

An increase in a permutation is a number for which holds. The set of increases in a permutation is thus through ${\displaystyle \pi \in S_{n}}$ ${\displaystyle i}$ ${\displaystyle \pi (i+1)>\pi (i)}$

${\displaystyle \operatorname {asc} (\pi )=\left\{i\in \{1,\ldots ,n-1\}\mid \pi (i+1)>\pi (i)\right\}}$

given. The same applies to a descent . The number of permutations in with exact increases or decreases is given by the Euler numbers . A maximum, that is to say no longer extendable on both sides ${\displaystyle \pi (i+1)<\pi (i)}$ ${\displaystyle S_{n}}$ ${\displaystyle k}$ ${\displaystyle \textstyle \left\langle \!{n \atop k}\!\right\rangle }$

${\displaystyle (\pi (i),\pi (i+1),\ldots ,\pi (i+l))}$

successively increasing or decreasing numbers in a permutation is called increasing or decreasing run of length . For such a sequence can only consist of one number. If a permutation has a total of ascents or descents, it is composed of descending or ascending runs. Accordingly, the number of permutations in with exactly increasing or decreasing runs is given by. ${\displaystyle l+1}$ ${\displaystyle l=0}$ ${\displaystyle k}$ ${\displaystyle k+1}$ ${\displaystyle S_{n}}$ ${\displaystyle k}$ ${\displaystyle \textstyle \left\langle \!{n \atop k-1}\!\right\rangle }$

Order properties

arrangement

Hasse diagram of the permutations in S ₄ . Blue, green and red edges correspond to the neighboring swaps (1 2), (2 3) and (3 4), which, viewed from bottom to top, always produce exactly one missing position.

Using the wrong objects can be on the set of one -bit permutations partial order by ${\displaystyle n}$

${\displaystyle \pi \leq \tau \Leftrightarrow \operatorname {inv} (\pi )\subseteq \operatorname {inv} (\tau )}$,

define, where are. The minimum element with respect to this order is the identical permutation, while the maximum element is the permutation which reverses the order of all numbers. In the associated Hasse diagram , two permutations are connected by an edge if they emerge from one another through a neighboring exchange. The nodes and edges of the Hasse diagram form a Cayley graph that is isomorphic to the edge graph of the corresponding permutahedron . The permutahedron is a convex polytope in -dimensional space, which arises from the fact that the permutations of the set are interpreted as coordinate vectors and then the convex hull of these points is formed. ${\displaystyle \pi ,\tau \in S_{n}}$ ${\displaystyle n}$ ${\displaystyle \{1,\ldots ,n\}}$

enumeration

The inversion table or the inversion vector of a permutation assigns to each number the number of faults it generates. Designates the number of numbers that are to the left of in the tuple representation and are greater than , then the inversion vector of a permutation is through ${\displaystyle \pi \in S_{n}}$ ${\displaystyle 1\leq j\leq n}$ ${\displaystyle b_{j}}$ ${\displaystyle \pi }$ ${\displaystyle j}$ ${\displaystyle j}$

${\displaystyle I(\pi )=(b_{1},b_{2},\ldots ,b_{n})}$

given. Conversely, the underlying permutation can be clearly determined from the inversion vector. Summing up the inversion vector as a number in a faculty-based number system on, every permutation can be a unique number by ${\displaystyle I(\pi )}$ ${\displaystyle \pi }$ ${\displaystyle \pi \in S_{n}}$ ${\displaystyle z(\pi )\in \{0,\ldots ,n!-1\}}$

${\displaystyle z(\pi )=\sum _{i=1}^{n}b_{i}\cdot (n-i)!}$

to assign. Instead of the inversion vector, the Lehmer code is also used to number permutations.

Symmetries

The permutation complementary to a permutation is ${\displaystyle \pi \in S_{n}}$

${\displaystyle \pi ^{-}=(n-\pi (1)+1,\ldots ,n-\pi (n)+1)}$.

The complementary permutation is created by horizontally mirroring the permutation matrix. The reverse permutation is similar

${\displaystyle \pi '=(\pi (n),\pi (n-1),\ldots ,\pi (1))}$

and is created by vertical reflection. Complementary and reverse permutations have the same cycle type and order as the initial permutation. However, the number of ascents and descents is swapped for complementary and reverse permutations. In addition, the sign is reversed for complementary permutations and for reverse permutations with length 2 modulo 4 or length 3 modulo 4. The inverse of the complementary permutation is equal to the reversed inverse and the inverse of the reverse permutation is equal to the complementary inverse.

Special permutations

Cyclic permutations

→ Main article : Cyclic permutation

Graph of a cyclic permutation of length 6

A permutation that cyclically swaps numbers and leaves the remaining numbers fixed is called a cyclic permutation or cycle and is written as a single cycle of length . A cycle, i.e. an exchange of two numbers, is also called transposition. The concatenation of cyclic permutations is commutative if they have disjoint carriers. The inverse of a cyclic permutation is always cyclic as well, as is the powers of a cyclic permutation whose length is a prime number. Every cyclic permutation can be broken down into individual (not disjoint) transpositions and has an even sign if and only if its length is odd. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2}$

Fixed point free permutations

→ Main article : Fixed point free permutation

Graph of a fixed point free permutation of the numbers from 1 to 8

Numbers that are held by a permutation are called fixed points of the permutation. In the two-line form, fixed points can be recognized by the fact that the top and bottom entries of the respective column are the same. In the cycle notation, fixed points are exactly the units' cycles or the numbers that do not appear. In the permutation matrix, the entries assigned to the fixed points are the main diagonal . A fixed point-free permutation does not hold any of the numbers and is also called derangement. The number of fixed point-free permutations of the numbers from to can be calculated by the sub-faculty . For increasing , the proportion of fixed-point-free permutations tends very quickly against the reciprocal of Euler's number . If some of the elements in a permutation are to remain in their old place, one speaks of a partial derangement, the number of which can be determined using the Rencontres numbers . ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle {!}n}$ ${\displaystyle n}$ ${\displaystyle e}$

Self-inverse permutations

→ Main article : Self-inverse permutation

Graph of a self-inverse permutation of the numbers from 1 to 8

A permutation with or equivalent to it is called involution or self-inverse. The involutions are precisely the permutations of order two as well as the identity itself (the only permutation of order one). A permutation is an involution if and only if its cycle representation contains a maximum of cycles of length two, i.e. transpositions. The permutation matrix of a self-inverse permutation is always symmetrical . Self-inverse permutations play an important role in cryptography , namely if a message is encrypted using a self-inverse permutation, then the message can also be decrypted again using the same permutation. ${\displaystyle \pi }$ ${\displaystyle \pi ^{2}={\mbox{id}}}$ ${\displaystyle \pi ^{-1}=\pi }$

An example of a self-inverse permutation is mirroring

${\displaystyle \sigma _{n}={\begin{pmatrix}1&2&\cdots &n\\n&n-1&\cdots &1\end{pmatrix}}=(1~n)(2~(n-1))(3~(n-2))\cdots }$,

see also word (Theoretical Computer Science) §Spiegelung und Palindrome .

Alternating permutations

→ Main article : Alternating permutation

A permutation is called alternating if there is no number in its tuple representation in terms of its size between the preceding number and the following number . In an alternating permutation, the numbers swapped by the permutation are therefore always alternately larger and smaller than the previous number. If the sequence of numbers begins with an increase, one speaks of an up-down permutation, and it begins with a decrease in a down-up permutation. Each alternating permutation of odd length corresponds to a full partially ordered binary tree and each alternating permutation of even length corresponds to an almost full such tree. The numbers of alternating permutations of fixed length appear as coefficients in the Maclaurin series of the secant and the tangent function and are closely related to the Euler and Bernoulli numbers . ${\displaystyle \pi (j)}$ ${\displaystyle \pi (j-1)}$ ${\displaystyle \pi (j+1)}$

Separable permutations

→ Main article : Separable permutation

Separable permutations are permutations that can be represented as a direct or skewed sum of trivial permutations. Such a sum of two permutations results in a new permutation whose length is the sum of the lengths of the two initial permutations. In the case of a direct sum, the second permutation is attached to the first in a shifted manner; in the case of an inclined sum, the first permutation is shifted in front of the second. The number of separable permutations of fixed length is given by the Schröder numbers . Separable permutations are characterized by a special recursive block structure of the associated permutation matrices. They are examined , among other things, in sorting theory.

Random permutations

→ Main article : Random permutation

A random permutation is a permutation selected at random from the set of permutations. In stochastics , random permutations are viewed as random variables from a discrete probability space . In this way, key figures of random permutations, such as the number of fixed points, deficiencies or cycles, can be viewed as discrete random variables, the probability distributions of which are then examined. In the computer, random permutations can be efficiently generated using the Fisher-Yates method . Random permutations are examined , among other things, in the analysis of sorting processes , in cryptography and coding theory, and in the context of randomized algorithms . The 100 Prisoners Problem is a mathematical puzzle based on random permutations. ${\displaystyle S_{n}}$

Permutation in music

Permutations of the Lulu series (Alban Berg)

About permutation in the fugue composition see under Fugue .

In twelve-tone technique , permutation is the derivation of further rows from a twelve-tone row by taking individual tones out one after the other according to a specific numerical selection mode until a new, complete twelve-tone row is created. This is how Alban Berg proceeds in his opera Lulu .

Remarks

1. ↑ Occasionally also as a bijective representation

   ${\displaystyle \pi \colon \{1,2,\ldots ,n\}\operatorname {\twoheadrightarrow \!\!\!\!\!\!\!\!\!\!\;\;\rightarrowtail } \;\{1,2,\ldots ,n\}}$

   written, see function (mathematics) §Symbolism .
2. ↑ Horst Weber: Article Permutation , in: The great Lexicon of Music , edited by Marc Honnegger and Günter Massenkeil , Herder Verlag Freiburg / Brsg. 1978/1987, Volume 6, ISBN 3-451-20948-9 , pp. 243f

literature

• Martin Aigner : Discrete Mathematics . Vieweg, 2006, ISBN 3-8348-9039-1 .
• Michael Artin : Algebra . Birkhäuser, 1998, ISBN 3-7643-5938-2 .
• Albrecht Beutelspacher : Linear Algebra . 6th revised and supplemented edition. Vieweg, 2003, ISBN 3-528-56508-X .
• Konrad Jacobs , Dieter Jungnickel : Introduction to combinatorics . de Gruyter, 2003, ISBN 3-11-016727-1 .
• Hans Kurzweil, Bernd Stellmacher : Theory of finite groups: an introduction . Springer, 1998, ISBN 3-540-60331-X .
• Kristina Reiss , Gernot Stroth : Finite Structures . Springer, 2011, ISBN 3-642-17181-8 .

Web links

Commons : Permutations  - collection of images, videos and audio files

Wiktionary: Permutation  - explanations of meanings, word origins, synonyms, translations

• DA Suprunenko: Permutation of a set . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
• alozano, Pedro Sanchez, Raymond Puzio, J. Pahikkala: Permutation . In: PlanetMath . (English)
• Eric W. Weisstein : Permutation . In: MathWorld (English).