Absenteeism

Absence of a permutation

Under false state , misalignment or inversion of a permutation is understood in the combinatorics a pair of elements of an ordered set whose, order is reversed by the permutation. The number of errors in a permutation is called the error number or inversion number of the permutation. The sign of a permutation can be determined via the missing number, an even permutation having an even missing number and an odd permutation having an odd missing number.

There are various options for displaying the deficits in a permutation, for example using the inversion table, the Lehmer code or the Rothe diagram. If the entries on the inversion table or the Lehmer code are interpreted as a number in a faculty-based number system , each permutation can be assigned a unique number. Furthermore, a partial order can be defined with the help of the missing positions on the set of permutations .

Since the missing number of a permutation can be viewed as a measure of the disorder of the numbers swapped by the permutation, missing statuses play an important role in the analysis of sorting processes .

definition

If the symmetric group of all permutations of the set , then a missing permutation is a pair for which ${\displaystyle S_{n}}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle \pi =(\pi (1),\pi (2),\ldots ,\pi (n))\in S_{n}}$ ${\displaystyle (i,j)}$

${\displaystyle i<j}$   and   ${\displaystyle \pi (i)>\pi (j)}$

applies. The set of errors in a permutation is then through ${\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. Occasionally, in the literature, instead of the couple , the couple is also referred to as a deficit. ${\displaystyle (i,j)}$ ${\displaystyle (\pi (i),\pi (j))}$

In a more general way, permutations of arbitrary finite ordered sets can also be considered, but for the mathematical analysis one can restrict oneself to the first natural numbers. ${\displaystyle n}$

Examples

Concrete example

The set of permutation errors

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

is

${\displaystyle \operatorname {inv} (\pi )=\left\{(1,3),(2,3),(1,4),(2,4),(2,5)\right\}}$.

You can find these five missing items by looking for every number from to in the second line that are larger and to the left of the number. In the example these are the pairs and . The missing items are then the corresponding pairs of numbers in the first line. For example, the pair is to the associated faulty state the pair , as to the number and the number is. ${\displaystyle 1}$ ${\displaystyle n-1}$ ${\displaystyle (3,1),(5,1),(3,2),(5,2)}$ ${\displaystyle (5,4)}$ ${\displaystyle (5,1)}$ ${\displaystyle (2,3)}$ ${\displaystyle 5}$ ${\displaystyle 2}$ ${\displaystyle 1}$ ${\displaystyle 3}$

More general examples

The identical permutation is the only permutation without deficiencies, so ${\displaystyle \operatorname {id} }$

${\displaystyle \operatorname {inv} (\operatorname {id} )=\{\}}$.

A neighbor swap generates exactly one deficit ${\displaystyle \tau _{i,i+1}=(~i~~i+1~)}$

${\displaystyle \operatorname {inv} (\tau _{i,i+1})=\{(i,i+1)\}}$.

A transposition with has the following deficiencies: ${\displaystyle \tau _{i,j}=(~i~~j~)}$ ${\displaystyle i<j}$ ${\displaystyle 2(j-i)-1}$

${\displaystyle \operatorname {inv} (\tau _{i,j})=\{(i,j)\}\cup \{(i,k)\mid k=i+1,\ldots ,j-1\}\cup \{(k,j)\mid k=i+1,\ldots ,j-1\}}$.

number

Missing number

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.3), (2.3)	2
4th	(3.1.2)	(1.2), (1.3)	2
5	(3.2.1)	(1,2), (1,3), (2,3)	3

The number of errors in a permutation is called the error 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. The sign of a permutation can be determined from the missing number , because it applies ${\displaystyle |\operatorname {inv} (\pi )|}$ ${\displaystyle \pi }$

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

If the missing number is even, it is called an even permutation, otherwise it is called an odd permutation. The missing number of the inverse permutation is identical to the missing number of the initial permutation , that is ${\displaystyle \pi ^{-1}}$ ${\displaystyle \pi }$

${\displaystyle |\operatorname {inv} (\pi ^{-1})|=|\operatorname {inv} (\pi )|}$,

because the set of the imperfections of the inverse permutation has the representation

${\displaystyle \operatorname {inv} (\pi ^{-1})=\{(\pi (i),\pi (j))\mid (i,j)\in \operatorname {inv} (\pi )\}}$.

distribution

Number of permutations of n elements with k deficiencies

${\displaystyle {}_{k}\!\diagdown \!\!{}^{n}}$	1	2	3	4th	5	6th
0	1	1	1	1	1	1
1	0	1	2	3	4th	5
2	0	0	2	5	9	14th
3	0	0	1	6th	15th	29
4th	0	0	0	5	20th	49
5	0	0	0	3	22nd	71
6th	0	0	0	1	20th	90
7th	0	0	0	0	15th	101
8th	0	0	0	0	9	101
9	0	0	0	0	4th	90
10	0	0	0	0	1	71
11	0	0	0	0	0	49
12th	0	0	0	0	0	29
13th	0	0	0	0	0	14th
14th	0	0	0	0	0	5
15th	0	0	0	0	0	1
total	1	2	6th	24	120	720

The number of -digit permutations with exactly missing positions is defined as ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle I_{n,k}=\#\left\{\pi \in S_{n}\mid |\operatorname {inv} (\pi )|=k\right\}}$.

Since the identical permutation is the only permutation without missing gaps, applies to all . Since there are neighbors exchanges with exactly one missing position, it is next for everyone . The maximum missing number of a -digit permutation is ${\displaystyle I_{n,0}=1}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle I_{n,1}=n-1}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle k_{\max }={\frac {n(n-1)}{2}}}$

and is assumed for precisely that permutation which reverses the order of all numbers. The symmetry also applies

${\displaystyle I_{n,k_{\max }-k}=I_{n,k}}$.

With the convention for and , the numbers fulfill the recursion (sequence A008302 in OEIS ) ${\displaystyle I_{n,k}=0}$ ${\displaystyle k<0}$ ${\displaystyle k>k_{\max }}$ ${\displaystyle I_{n,k}}$

${\displaystyle I_{n,k}=I_{n,k-1}+I_{n-1,k}-I_{n-1,k-n}}$

and the total representation

${\displaystyle I_{n,k}=\sum _{j=0}^{n-1}I_{n-1,k-j}}$.

Generating function

The generating function for the number of deficiencies has a relatively simple form

${\displaystyle G_{n}(x)=\sum _{k=0}^{k_{\max }}I_{n,k}\,x^{k}=\prod _{j=1}^{n}{\frac {1-x^{j}}{1-x}}}$.

This result goes back to Olinde Rodrigues (1839).

Expectation and variance

The expected value of the missing number of a ( uniformly distributed ) random permutation from is ${\displaystyle X}$ ${\displaystyle S_{n}}$

${\displaystyle \operatorname {E} (X)=\sum _{j=1}^{n}{\frac {j-1}{2}}={\frac {n(n-1)}{4}}}$,

which is why sorting processes such as bubble sort , which correct exactly one deficit per step, not only have a quadratic runtime in the worst case, but also in the average case. The same applies to the variance of the missing number of a random permutation

${\displaystyle \operatorname {Var} (X)=\sum _{j=1}^{n}{\frac {j^{2}-1}{12}}={\frac {n(2n+5)(n-1)}{72}}}$,

as a result, the standard deviation of the number of missing items is comparatively large with a value of approximately . The number of faults in a random permutation is asymptotically normally distributed . ${\displaystyle {\tfrac {1}{6}}n^{3/2}}$ ${\displaystyle n\to \infty }$

Representations

Inversion table

Inversion tables of the permutations in S ₃

No.	permutation	Inversion table
0	(1,2,3)	(0,0,0)
1	(1,3,2)	(0.1.0)
2	(2,1,3)	(1,0,0)
3	(3.1.2)	(1,1,0)
4th	(2,3,1)	(2.0.0)
5	(3.2.1)	(2.1.0)

The inversion table or the inversion vector of a permutation assigns to each number the number of faults it generates. Designated ${\displaystyle \pi \in S_{n}}$ ${\displaystyle 1\leq j\leq n}$

${\displaystyle b_{j}=\#\left\{i\in \{1,\ldots ,n\}\mid (\pi ^{-1}(i),\pi ^{-1}(j))\in \operatorname {inv} (\pi )\right\}}$

the number of numbers that are to the left of in the tuple representation and that are greater than , then the inversion table of a permutation is the vector ${\displaystyle \pi }$ ${\displaystyle j}$ ${\displaystyle j}$

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

Since the number can at most generate errors, it always applies . The missing number of the permutation then results as the sum ${\displaystyle j}$ ${\displaystyle n-j}$ ${\displaystyle 0\leq b_{j}\leq n-j}$ ${\displaystyle b_{n}=0}$

${\displaystyle |\operatorname {inv} (\pi )|=b_{1}+\ldots +b_{n}}$.

Conversely, the underlying permutation can be determined from the inversion table. For this purpose, one determines in turn the relative placements of the figures , in which each indicates the number at which position occurs within the already considered numbers. Here stands for the first digit, for the second digit and so on. This one-to-one correspondence between permutation and the associated inversion table is of great practical importance, since combinatorial problems in connection with permutations can often be more easily solved by looking at inversion tables. The reason for this is that the entries in the inversion table can be selected independently of one another within the specified limits, while the numbers must be different in pairs. ${\displaystyle I(\pi )}$ ${\displaystyle \pi }$ ${\displaystyle n,n-1,\ldots ,1}$ ${\displaystyle b_{i}}$ ${\displaystyle i}$ ${\displaystyle b_{j}=0}$ ${\displaystyle b_{j}=1}$ ${\displaystyle b_{1},\ldots ,b_{n}}$ ${\displaystyle \pi (1),\ldots ,\pi (n)}$

example

In the example above is the inversion table

${\displaystyle I(\pi )=(\,2,~2,~0,~1,~0\,)}$.

The underlying permutation can be obtained from the inversion table by determining the following arrangements in sequence:

${\displaystyle (\,5\,),~(\,5,~4\,),~(\,3,~5,~4\,),~(\,3,~5,~2,~4\,)}$   and   . ${\displaystyle (\,3,~5,~1,~2,~4\,)}$

Lehmer Code

Lehmer codes of the permutations in S ₃

No.	permutation	Lehmer Code
0	(1,2,3)	(0,0,0)
1	(1,3,2)	(0.1.0)
2	(2,1,3)	(1,0,0)
3	(2,3,1)	(1,1,0)
4th	(3.1.2)	(2.0.0)
5	(3.2.1)	(2.1.0)

In a certain way, dual to the inversion table is the Lehmer code (named after Derrick Henry Lehmer ), which also summarizes the deficiencies of a permutation. Designated

${\displaystyle l_{i}=\#\left\{j\in \{1,\ldots ,n\}\mid (i,j)\in \operatorname {inv} (\pi )\right\}}$

the number of numbers that are to the right of in the tuple representation and are less than , then the Lehmer code of a permutation is the vector ${\displaystyle \pi }$ ${\displaystyle \pi (i)}$ ${\displaystyle \pi (i)}$

${\displaystyle L(\pi )=(\,l_{1},~l_{2},~\ldots ,~l_{n}\,)}$.

The same applies here and therefore always . The missing number of the permutation results accordingly as a sum ${\displaystyle 0\leq l_{i}\leq n-i}$ ${\displaystyle l_{n}=0}$

${\displaystyle |\operatorname {inv} (\pi )|=l_{1}+\ldots +l_{n}}$.

The underlying permutation can also be determined from the Lehmer code . To do this, first write down all the numbers from to one after another. In the following, in the -th step, remove the -th number from this list and then write it down as . Here, too, there is a one-to-one correspondence between the permutation and the associated Lehmer code. ${\displaystyle L(\pi )}$ ${\displaystyle \pi }$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle (l_{i}+1)}$ ${\displaystyle \pi (i)}$

example

In the example above is the Lehmer code

${\displaystyle L(\pi )=(\,2,~3,~0,~0,~0\,)}$.

The underlying permutation is obtained from the Lehmer code by determining the following arrangements in sequence:

${\displaystyle (\,3\,),~(\,3,~5\,),~(\,3,~5,~1\,),~(\,3,~5,~1,~2\,)}$   and   . ${\displaystyle (\,3,~5,~1,~2,~4\,)}$

Rothe diagram

Rothe diagram of the
permutation (3,5,1,2,4)

	1	2	3	4th	5	l
1	${\displaystyle \times }$	${\displaystyle \times }$	${\displaystyle \bullet }$			2
2	${\displaystyle \times }$	${\displaystyle \times }$		${\displaystyle \times }$	${\displaystyle \bullet }$	3
3	${\displaystyle \bullet }$					0
4th		${\displaystyle \bullet }$				0
5				${\displaystyle \bullet }$		0
b	2	2	0	1	0

Another possibility to show the missing positions of a permutation is the Rothe diagram (named after Heinrich August Rothe ). In a scheme consisting of fields, the column for which applies is first marked with a point in each line . These fields correspond precisely to the entries with the value of the associated permutation matrix . The permutation errors then correspond to those fields that have both a point below in the same column and a point to the right in the same line. These fields are marked with a cross. In this way, a field is marked with a cross if and only if there is an error in . ${\displaystyle \pi \in S_{n}}$ ${\displaystyle n\times n}$ ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle \pi (k)=l}$ ${\displaystyle 1}$ ${\displaystyle (k,l)}$ ${\displaystyle (k,\pi ^{-1}(l))}$ ${\displaystyle \pi }$

Both the inversion table and the Lehmer code can be read from the Rothe diagram. The number corresponds to the number of crosses in the column and the number to the number of crosses in the row . If you transpose the diagram (i.e. swap the rows and columns), you get a representation of the missing positions of the associated inverse permutation. If the Rothe diagram of a permutation has a cross in the field , then this applies to the diagram of the associated inverse permutation in the field . Due to the symmetry property of the Rothe diagram, the inverse permutation applies ${\displaystyle b_{j}}$ ${\displaystyle j}$ ${\displaystyle l_{i}}$ ${\displaystyle i}$ ${\displaystyle (k,l)}$ ${\displaystyle (l,k)}$

${\displaystyle I(\pi ^{-1})=L(\pi )}$   and   . ${\displaystyle L(\pi ^{-1})=I(\pi )}$

For self-inverse permutations , i.e. permutations for which applies, the inversion table and Lehmer code therefore agree. ${\displaystyle \pi ^{-1}=\pi }$

Permutation graph

Permutation graph of the permutation (4,3,5,1,2) and the corresponding set of distances

Each permutation can also be assigned a permutation graph (not to be confused with the graph representation of a permutation) with the aid of the errors . The permutation graph of a permutation is an undirected graph with the node set ${\displaystyle \pi \in S_{n}}$ ${\displaystyle G=(V,E)}$

${\displaystyle V=\{1,\ldots ,n\}}$

and the set of edges

${\displaystyle E=\{(\pi (i),\pi (j))\mid (i,j)\in \operatorname {inv} (\pi )\}}$.

The edges of the permutation graph connect those pairs of numbers that create an error. Permutation graphs can also be used geometrically as section graphs of the lines

${\displaystyle S_{i}=[(i,0),(\sigma (i),1)]}$

to be defined for. The end points of these lines lie on two parallel straight lines and two lines intersect exactly when the numbers at the end points create a fault. Permutation graphs can also be characterized in that both the graph and its complement graph are comparability graphs . The complement graph corresponds to the permutation graph of the reverse permutation . ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle G}$ ${\displaystyle {\bar {G}}}$ ${\displaystyle (\pi (n),\ldots ,\pi (1))}$

example

For example, the permutation graph of the permutation has the edge set ${\displaystyle (4,3,5,1,2)\in S_{5}}$

${\displaystyle E=\{(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4)\}}$.

use

List of permutations

If you understand the inversion table or the Lehmer code as a number in a faculty-based number system , each permutation can be assigned a unique number in the set . The number is obtained from the inversion table ${\displaystyle (b_{1},\ldots ,b_{n})}$ ${\displaystyle (l_{1},\ldots ,l_{n})}$ ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \{0,\ldots ,n!-1\}}$

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

and the number from the Lehmer code

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

These two numbers only match for self-inverse permutations. Further variants for numbering permutations exist by considering the pairs of numbers that are fulfilled instead of and / or instead of in the deficiency definition . These pairs of numbers then correspond to crosses on the right instead of left or below instead of above the points in the Rothe diagram. The vectors consisting of the sums of the crosses per row or column can then also be interpreted as numbers in a faculty-based number system. ${\displaystyle i>j}$ ${\displaystyle i<j}$ ${\displaystyle \pi (i)<\pi (j)}$ ${\displaystyle \pi (i)>\pi (j)}$

example

The number for the permutation is obtained from the associated inversion table ${\displaystyle \pi =(\,3,~5,~1,~2,~4\,)}$ ${\displaystyle I(\pi )}$

${\displaystyle z(\pi )=2\cdot 4!+2\cdot 3!+0\cdot 2!+1\cdot 1!+0\cdot 0!=61}$

and the number from the associated Lehmer code ${\displaystyle L(\pi )}$

${\displaystyle z'(\pi )=2\cdot 4!+3\cdot 3!+0\cdot 2!+0\cdot 1!+0\cdot 0!=66}$.

Arrangement of permutations

Hasse diagram ( Cayley graph ) of the permutations in S ₄

Furthermore, a partial order can be given by considering the deficiencies on the set of -digit permutations . Such order relation is for permutations by ${\displaystyle n}$ ${\displaystyle \leq }$ ${\displaystyle \pi ,\sigma \in S_{n}}$

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

Are defined. Two permutations are related if the set of errors in the first permutation is a subset of the error set in the second permutation. The minimum element with respect to this order is the identical permutation, while the maximum element is the permutation that reverses the order of all numbers.

This order relation can be graphically illustrated with the help of a Hasse diagram . Two permutations are connected by an edge if they emerge from each other through an exchange of neighbors . The nodes and edges of the Hasse diagram form a Cayley graph that is isomorphic to the edge graph of the corresponding permutahedron .

example

In the adjacent Hasse diagram of the permutations of the symmetrical group , the smallest permutation with regard to this order is at the bottom and the largest permutation at the top. Blue, green and red edges each correspond to the neighboring swaps , and , which, viewed from bottom to top, always produce exactly one missing position. ${\displaystyle S_{4}}$ ${\displaystyle \tau _{12}}$ ${\displaystyle \tau _{23}}$ ${\displaystyle \tau _{34}}$

history

The concept of the absence of a permutation was introduced in 1750 by Gabriel Cramer in his work Introduction à l'analyse des lignes courbes algébriques . As part of the eponymous Cramer's rule to specify the solution of linear equations he defined the determinant of a square matrix by ${\displaystyle A=(a_{ij})}$

${\displaystyle \det(A)=\sum _{\pi \in S_{n}}\left((-1)^{|\operatorname {inv} (\pi )|}\prod _{i=1}^{n}a_{i,\pi (i)}\right)}$,

where the sum runs over all -digit permutation. Cramer's rule was the impetus for the development of an extensive theory of determinants. ${\displaystyle n}$

Various terms have been used over time to describe the concept of absenteeism. Cramer himself referred to deficiencies as dérangement (exchange), Pierre-Simon Laplace used the term variation in 1772 and Joseph Gergonne finally introduced the term inversion in 1813 , which is mainly used today in English-speaking countries. The German term “Fehlstand” was popularized by Gerhard Kowalewski at the beginning of the 20th century .

literature

• Albrecht Beutelspacher : Linear Algebra. An introduction to the science of vectors, maps, and matrices . 6th edition. Vieweg, 2009, ISBN 3-528-56508-X .
• Siegfried Bosch : Linear Algebra . 4th revised edition. Springer, 2009, ISBN 3-540-76437-2 .
• Donald E. Knuth : The Art of Computer Programming . 2nd Edition. Volume 3: Sorting and Searching. Addison-Wesley, 1998, ISBN 0-201-89685-0 .

Web links

• Eric W. Weisstein : Permutation Inversion . In: MathWorld (English).

Individual evidence

1. ^ ^{A b c} Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . S. 14 .
2. ^ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . S. 15 .
3. ^ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . S. 16 .
4. ↑ Vladimir Nikolaevič Sačkov: Probabilistic Methods in Combinatorial Analysis . Cambridge University Press, 1997, pp. 30 .
5. ^ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . S. 13 .
6. ^ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . S. 18 .
7. ^ Thomas Muir: Theory of determinants in the historical order of development . tape 1 . Macmillan and Co, 1906, pp. 13 .
8. ^ Thomas Muir: Theory of determinants in the historical order of development . tape 1 . Macmillan and Co, 1906, pp. 25,134 .
9. ↑ Gerhard Kowalewski: Introduction to the determinant theory including the infinite and the Fredholm determinants . Veit & Co., 1909.