Fehlstand

Fehlstand einer Permutation

Unter Fehlstand, Fehlstellung oder Inversion einer Permutation versteht man in der Kombinatorik ein Paar von Elementen einer geordneten Menge, deren Reihenfolge durch die Permutation vertauscht wird. Die Anzahl der Fehlstände einer Permutation heißt Fehlstandszahl oder Inversionszahl der Permutation. Über die Fehlstandszahl lässt sich das Vorzeichen einer Permutation ermitteln, wobei eine gerade Permutation eine gerade Fehlstandszahl und eine ungerade Permutation eine ungerade Fehlstandszahl aufweist.

Es gibt verschiedene Möglichkeiten zur Darstellung der Fehlstände einer Permutation, beispielsweise über die Inversionstafel, den Lehmer-Code oder das Rothe-Diagramm. Fasst man die Einträge der Inversionstafel oder des Lehmer-Codes als Zahl in einem fakultätsbasierten Zahlensystem auf, kann jeder Permutation eine eindeutige Nummer zugewiesen werden. Weiter lässt sich mit Hilfe der Fehlstände auf der Menge der Permutationen eine partielle Ordnung definieren.

Nachdem die Fehlstandszahl einer Permutation als Maß für die Unordnung der durch die Permutation vertauschten Zahlen angesehen werden kann, spielen Fehlstände eine wichtige Rolle bei der Analyse von Sortierverfahren.

Definition

Ist $S_{n}$ die symmetrische Gruppe aller Permutationen der Menge $\{1,\ldots ,n\}$, dann ist ein Fehlstand einer Permutation $\pi =(\pi (1),\pi (2),\ldots ,\pi (n))\in S_{n}$ ein Paar $(i,j)$, für das

$i<j$   und   $\pi (i)>\pi (j)$

gilt. Die Menge der Fehlstände einer Permutation $\pi \in S_{n}$ ist dann durch

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

gegeben. Gelegentlich wird in der Literatur anstelle des Paares $(i,j)$ auch das Paar $(\pi (i),\pi (j))$ als Fehlstand bezeichnet.

Allgemeiner können auch Permutationen beliebiger endlicher geordneter Mengen betrachtet werden, für die mathematische Analyse kann man sich jedoch auf die ersten $n$ natürlichen Zahlen beschränken.

Beispiele

Konkretes Beispiel

Die Menge der Fehlstände der Permutation

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

ist

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

Man kann diese fünf Fehlstände dadurch ermitteln, dass man in der zweiten Zeile für jede Zahl von $1$ bis $n-1$ alle Zahlen sucht, die größer sind und links von der Zahl stehen. Im Beispiel sind dies die Paare $(3,1),(5,1),(3,2),(5,2)$ und $(5,4)$. Die Fehlstände sind dann die jeweils zugehörigen Zahlenpaare der ersten Zeile. Beispielsweise ist der zu dem Paar $(5,1)$ zugehörige Fehlstand das Paar $(2,3)$, da über der $5$ die Zahl $2$ und über der $1$ die Zahl $3$ steht.

Allgemeinere Beispiele

Die identische Permutation $\operatorname {id}$ ist die einzige Permutation ohne Fehlstände, also

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

Eine Nachbarvertauschung $\tau _{i,i+1}=(~i~~i+1~)$ generiert genau einen Fehlstand

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

Eine Transposition $\tau _{i,j}=(~i~~j~)$ mit $i<j$ weist die folgenden $2(j-i)-1$ Fehlstände auf:

$\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\}$.

Anzahl

Fehlstandszahl

Fehlstände der Permutationen in S₃

Nr.	Permutation	Fehlstände	Anzahl
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
4	(3,1,2)	(1,2),(1,3)	2
5	(3,2,1)	(1,2),(1,3),(2,3)	3

Die Anzahl der Fehlstände $|\operatorname {inv} (\pi )|$ einer Permutation $\pi$ heißt Fehlstandszahl oder Inversionszahl der Permutation. Die Fehlstandszahl kann als Maß für die Unordnung der durch die Permutation vertauschten Zahlen angesehen werden. Über die Fehlstandszahl lässt sich das Vorzeichen einer Permutation ermitteln, denn es gilt

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

Ist die Fehlstandszahl gerade, so spricht man von einer geraden Permutation, ansonsten von einer ungeraden Permutation. Die Fehlstandszahl der inversen Permutation $\pi ^{-1}$ ist identisch mit der Fehlstandszahl der Ausgangspermutation $\pi$, das heißt

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

denn die Menge der Fehlstände der inversen Permutation hat die Darstellung

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

Verteilung

Anzahl der Permutationen von n Elementen mit k Fehlständen

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

Die Anzahl der $n$-stelligen Permutationen mit genau $k$ Fehlständen ist definiert als

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

Nachdem die identische Permutation die einzige Permutation ohne Fehlstände ist, gilt $I_{n,0}=1$ für alle $n$. Da es $n-1$ Nachbarvertauschungen mit genau einem Fehlstand gibt, ist weiter $I_{n,1}=n-1$ für alle $n$. Die maximale Fehlstandszahl einer $n$-stelligen Permutation beträgt

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

und wird genau für diejenige Permutation angenommen, die die Reihenfolge aller Zahlen umkehrt. Weiterhin gilt die Symmetrie

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

Mit der Konvention $I_{n,k}=0$ für $k<0$ und $k>k_{\max }$ erfüllen die Zahlen $I_{n,k}$ die Rekursion (Folge A008302 in OEIS)

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

und die Summendarstellung

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

Erzeugende Funktion

Die erzeugende Funktion für die Anzahl der Fehlstände hat die verhältnismäßig einfache Form

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

Dieses Resultat geht auf Olinde Rodrigues (1839) zurück.

Erwartungswert und Varianz

Der Erwartungswert der Fehlstandszahl $X$ einer (gleichverteilt) zufälligen Permutation aus $S_{n}$ beträgt

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

weshalb Sortierverfahren wie Bubblesort, die pro Schritt genau einen Fehlstand beheben, nicht nur im schlechtesten Fall, sondern auch im durchschnittlichen Fall eine quadratische Laufzeit aufweisen. Für die Varianz der Fehlstandszahl einer zufälligen Permutation gilt entsprechend

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

wodurch auch die Standardabweichung der Fehlstandszahl mit einem Wert von etwa ${\tfrac {1}{6}}n^{3/2}$ vergleichsweise groß ausfällt. Die Anzahl der Fehlstände einer zufälligen Permutation ist für $n\to \infty$ asymptotisch normalverteilt.

Darstellungen

Inversionstafel

Inversionstafeln der Permutationen in S₃

Nr.	Permutation	Inversionstafel
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)
4	(2,3,1)	(2,0,0)
5	(3,2,1)	(2,1,0)

Die Inversionstafel oder der Inversionsvektor einer Permutation $\pi \in S_{n}$ ordnet jeder Zahl $1\leq j\leq n$ die Anzahl der Fehlstände zu, die sie erzeugt. Bezeichnet

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

die Anzahl der Zahlen, die in der Tupeldarstellung von $\pi$ links von $j$ stehen und größer als $j$ sind, dann ist die Inversionstafel einer Permutation der Vektor

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

Da die Zahl $j$ höchstens $n-j$ Fehlstände erzeugen kann, gilt $0\leq b_{j}\leq n-j$ und somit immer $b_{n}=0$. Die Fehlstandszahl der Permutation ergibt sich dann als Summe

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

Aus der Inversionstafel $I(\pi )$ lässt sich umgekehrt die zugrundeliegende Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} ermitteln. Hierzu bestimmt man der Reihe nach die relativen Platzierungen der Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n, n-1, \ldots , 1} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_i} jeweils angibt, an welcher Position die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} innerhalb der bereits betrachteten Zahlen auftritt. Dabei steht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j=0} für die erste Stelle, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j=1} für die zweite Stelle und so fort. Diese Eins-zu-Eins-Korrespondenz von Permutation und zugehöriger Inversionstafel ist von großer praktischer Bedeutung, da sich kombinatorische Probleme im Zusammenhang mit Permutationen durch die Betrachtung von Inversionstafeln oft leichter lösen lassen. Der Grund hierfür liegt darin, dass die Einträge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_1, \ldots , b_n} der Inversionstafel innerhalb der vorgegebenen Grenzen unabhängig voneinander gewählt werden können, während die Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(1), \ldots , \pi(n)} paarweise verschieden sein müssen.

Beispiel

In obigem Beispiel ist die Inversionstafel

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I(\pi) = ( \, 2, ~ 2, ~ 0, ~ 1, ~ 0 \, )} .

Aus der Inversionstafel erhält man die zugrundeliegende Permutation zurück, indem man folgende Anordnungen der Reihe nach ermittelt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ( \, 5 \, ), ~ ( \, 5, ~ 4 \, ), ~ ( \, 3, ~ 5, ~ 4 \, ), ~ ( \, 3, ~ 5, ~ 2, ~ 4 \, )}   und   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ( \, 3, ~ 5, ~ 1, ~ 2, ~ 4 \, )} .

Lehmer-Code

Lehmer-Codes der Permutationen in S₃

Nr.	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)
4	(3,1,2)	(2,0,0)
5	(3,2,1)	(2,1,0)

Auf gewisse Weise dual zur Inversionstafel ist der Lehmer-Code (benannt nach Derrick Henry Lehmer), der ebenfalls die Fehlstände einer Permutation zusammenfasst. Bezeichnet

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_i = \# \left\{ j \in \{ 1, \ldots , n \} \mid (i,j) \in \operatorname{inv}(\pi) \right\}}

die Anzahl der Zahlen, die in der Tupeldarstellung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} rechts von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(i)} stehen und kleiner als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(i)} sind, dann ist der Lehmer-Code einer Permutation der Vektor

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(\pi) = ( \, l_1, ~ l_2, ~ \ldots , ~ l_n \, )} .

Auch hier gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 \leq l_i \leq n-i} und somit immer $l_{n}=0$. Die Fehlstandszahl der Permutation ergibt sich entsprechend als Summe

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle | \operatorname{inv}(\pi) | = l_1 + \ldots + l_n} .

Aus dem Lehmer-Code Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(\pi)} lässt sich ebenfalls die zugrundeliegende Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} ermitteln. Hierzu notiert man zunächst alle Zahlen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} bis $n$ hintereinander. Im Folgenden entfernt man aus dieser Liste jeweils im Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -ten Schritt die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (l_i+1)} -te Zahl und notiert diese dann als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(i)} . Auch hier liegt eine Eins-zu-Eins-Korrespondenz zwischen der Permutation und dem zugehörigen Lehmer-Code vor.

Beispiel

In obigem Beispiel ist der Lehmer-Code

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

Aus dem Lehmer-Code erhält man die zugrundeliegende Permutation zurück, indem man folgende Anordnungen der Reihe nach ermittelt:

$(\,3\,),~(\,3,~5\,),~(\,3,~5,~1\,),~(\,3,~5,~1,~2\,)$   und   $(\,3,~5,~1,~2,~4\,)$.

Rothe-Diagramm

Rothe-Diagramm der
Permutation (3,5,1,2,4)

	1	2	3	4	5	l
1	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \times}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \times}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bullet}			2
2	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \times}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \times}		Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \times}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bullet}	3
3	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bullet}					0
4		Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bullet}				0
5				Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bullet}		0
b	2	2	0	1	0

Eine weitere Möglichkeit, die Fehlstände einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} darzustellen, ist das Rothe-Diagramm (benannt nach Heinrich August Rothe). In einem Schema bestehend aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \times n} Feldern wird zunächst in jeder Zeile Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} diejenige Spalte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l} mit einem Punkt markiert, für die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(k) = l} gilt. Diese Felder entsprechen gerade den Einträgen mit Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} der zugehörigen Permutationsmatrix. Die Fehlstände der Permutation entsprechen dann denjenigen Feldern, die sowohl einen Punkt unterhalb in der gleichen Spalte, als auch einen Punkt rechts in der gleichen Zeile haben. Diese Felder werden mit einem Kreuz markiert. Auf diese Weise wird ein Feld Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (k,l)} genau dann mit einem Kreuz markiert, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (k,\pi^{-1}(l))} ein Fehlstand von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} ist.

Aus dem Rothe-Diagramm lässt sich sowohl die Inversionstafel, als auch der Lehmer-Code ablesen. Die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j} entspricht gerade der Anzahl der Kreuze in der Spalte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} und die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_i} der Anzahl der Kreuze in der Zeile Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} . Transponiert man das Diagramm (vertauscht man also die Zeilen und Spalten), dann erhält man eine Darstellung der Fehlstände der zugehörigen inversen Permutation. Weist das Rothe-Diagramm einer Permutation im Feld Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (k,l)} ein Kreuz auf, dann gilt dies für das Diagramm der zugehörigen inversen Permutation im Feld Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (l,k)} . Aufgrund der Symmetrieeigenschaft des Rothe-Diagramms gilt demnach für die inverse Permutation

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I(\pi^{-1}) = L(\pi)}   und   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(\pi^{-1}) = I(\pi)} .

Für selbstinverse Permutationen, also Permutationen, für die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{-1}=\pi} gilt, stimmen demnach Inversionstafel und Lehmer-Code überein.

Permutationsgraph

Permutationsgraph der Permutation (4,3,5,1,2) und zugehörige Streckenmenge

Jeder Permutation kann mit Hilfe der Fehlstände auch ein Permutationsgraph (nicht zu verwechseln mit der Graphdarstellung einer Permutation) zugeordnet werden. Der Permutationsgraph einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} ist ein ungerichteter Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=(V,E)} mit der Knotenmenge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V = \{ 1, \ldots , n \}}

und der Kantenmenge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle E = \{ (\pi(i),\pi(j)) \mid (i,j) \in \operatorname{inv}(\pi) \}} .

Die Kanten des Permutationsgraphen verbinden also diejenigen Zahlenpaare, die einen Fehlstand erzeugen. Permutationsgraphen können auch geometrisch als Schnittgraphen der Strecken

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_i = [(i,0),(\sigma(i),1)]}

für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i=1, \ldots , n} definiert werden. Die Endpunkte dieser Strecken liegen auf zwei parallelen Geraden und zwei Strecken schneiden sich genau dann, wenn die Zahlen an den Endpunkten einen Fehlstand erzeugen. Permutationsgraphen können auch dadurch charakterisiert werden, dass sowohl der Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} , als auch sein Komplementgraph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar{G}} Vergleichbarkeitsgraphen sind. Der Komplementgraph entspricht dabei dem Permutationsgraphen der reversen Permutation $(\pi (n),\ldots ,\pi (1))$.

Beispiel

Beispielsweise besitzt der Permutationsgraph der Permutation $(4,3,5,1,2)\in S_{5}$ die Kantenmenge

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

Verwendung

Aufzählung von Permutationen

Fasst man die Inversionstafel $(b_{1},\ldots ,b_{n})$ beziehungsweise den Lehmer-Code $(l_{1},\ldots ,l_{n})$ als Zahl in einem fakultätsbasierten Zahlensystem auf, lässt sich jeder Permutation $\pi \in S_{n}$ eine eindeutige Nummer in der Menge $\{0,\ldots ,n!-1\}$ zuweisen. Aus der Inversionstafel erhält man so die Nummer

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

und aus dem Lehmer-Code die Nummer

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

Diese beiden Nummern stimmen nur für selbstinverse Permutationen überein. Weitere Varianten zur Nummerierung von Permutationen bestehen durch die Betrachtung der Zahlenpaare, die in der Fehlstandsdefinition Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i>j} statt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i<j} und/oder $\pi (i)<\pi (j)$ statt $\pi (i)>\pi (j)$ erfüllen. Diese Zahlenpaare entsprechen dann im Rothe-Diagramm Kreuzen rechts statt links beziehungsweise unterhalb statt oberhalb der Punkte. Die Vektoren bestehend aus den Summen der Kreuze pro Zeile oder Spalte können dann ebenfalls als Zahlen in einem fakultätsbasierten Zahlensystem aufgefasst werden.

Beispiel

Für die Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi = ( \, 3, ~ 5, ~ 1, ~ 2, ~ 4 \, )} erhält man aus der zugehörigen Inversionstafel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I(\pi)} die Nummer

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z(\pi) = 2 \cdot 4! + 2 \cdot 3! + 0 \cdot 2! + 1 \cdot 1! + 0 \cdot 0! = 61}

und aus dem zugehörigen Lehmer-Code Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(\pi)} die Nummer

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

Anordnung von Permutationen

Hasse-Diagramm (Cayley-Graph) der Permutationen in S₄

Weiter lässt sich durch Betrachtung der Fehlstände auf der Menge der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stelligen Permutationen eine partielle Ordnung angeben. Eine solche Ordnungsrelation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \leq} wird für Permutationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi, \sigma \in S_n} durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \leq \sigma \Leftrightarrow \operatorname{inv}(\pi) \subseteq \operatorname{inv}(\sigma)}

definiert. Zwei Permutationen stehen dabei in Relation, wenn die Menge der Fehlstände der ersten Permutation eine Teilmenge der Fehlstandsmenge der zweiten Permutation ist. Das minimale Element bezüglich dieser Ordnung ist die identische Permutation, während das maximale Element diejenige Permutation ist, die die Reihenfolge aller Zahlen umkehrt.

Grafisch lässt sich diese Ordnungsrelation mit Hilfe eines Hasse-Diagramms veranschaulichen. Zwei Permutationen sind dabei durch eine Kante verbunden, wenn sie durch eine Nachbarvertauschung auseinander hervorgehen. Die Knoten und Kanten des Hasse-Diagramms bilden einen Cayley-Graphen, der isomorph zum Kantengraphen des entsprechenden Permutaeders ist.

Beispiel

In dem nebenstehenden Hasse-Diagramm der Permutationen der symmetrischen Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_4} befindet sich die bezüglich dieser Ordnung kleinste Permutation ganz unten und die größte Permutation ganz oben. Blaue, grüne und rote Kanten entsprechen jeweils den Nachbarvertauschungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau_{12}} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau_{23}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau_{34}} , die von unten nach oben gesehen immer genau einen Fehlstand erzeugen.

Geschichte

Das Konzept des Fehlstands einer Permutation wurde im Jahr 1750 von Gabriel Cramer in seinem Werk Introduction à l’analyse des lignes courbes algébriques eingeführt. Im Rahmen der nach ihm benannten cramerschen Regel zur Angabe der Lösung linearer Gleichungssysteme definierte er die Determinante einer quadratischen Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=(a_{ij})} durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \det(A) = \sum_{\pi \in S_n} \left( (-1)^{| \operatorname{inv}(\pi) |} \prod_{i=1}^n a_{i, \pi(i)} \right)} ,

wobei die Summe über alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stelligen Permutation läuft. Die cramersche Regel war der Anstoß für die Entwicklung einer umfangreichen Determinantentheorie.

Für das Konzept des Fehlstands wurden im Lauf der Zeit verschiedene Begriffe verwendet. Cramer selbst bezeichnete Fehlstände als dérangement (Vertauschung), Pierre-Simon Laplace verwendete 1772 den Begriff variation (Veränderung) und Joseph Gergonne führte schließlich 1813 den Begriff inversion (Umkehrung) ein, der heute vor allem im englischsprachigen Raum verwendet wird. Der deutsche Begriff „Fehlstand“ wurde Anfang des 20. Jahrhunderts von Gerhard Kowalewski popularisiert.

Literatur

• Albrecht Beutelspacher: Lineare Algebra. Eine Einführung in die Wissenschaft der Vektoren, Abbildungen und Matrizen. 6. Auflage. Vieweg, 2009, ISBN 3-528-56508-X. 
• Siegfried Bosch: Lineare Algebra. 4. überarbeitete Auflage. Springer, 2009, ISBN 3-540-76437-2. 
• Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, 1998, ISBN 0-201-89685-0. 

Weblinks

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