~2025-16775-1: /* Inversionstafel */

2025-07-10T17:10:00Z

Inversionstafel

Neue Seite

[[Datei:Inversion qtl1.svg|mini|hochkant=0.8|Fehlstand einer Permutation]]
Unter '''Fehlstand''', '''Fehlstellung''' oder '''Inversion''' einer [[Permutation]] versteht man in der [[Kombinatorik]] ein Paar von Elementen einer [[Geordnete Menge|geordneten Menge]], deren [[Wohlordnung|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 (Permutation)|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ätsbasiertes Zahlensystem|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 <math>S_n</math> die [[symmetrische Gruppe]] aller [[Permutation]]en der Menge <math>\{ 1, \ldots , n \}</math>, dann ist ein Fehlstand einer Permutation <math>\pi = ( \pi(1), \pi(2), \ldots , \pi(n) ) \in S_n</math> ein [[Geordnetes Paar|Paar]] <math>(i,j)</math>, für das

: <math>i < j</math>   und   <math>\pi(i) > \pi(j)</math>

gilt. Die Menge der Fehlstände einer Permutation <math>\pi \in S_n</math> ist dann durch

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

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

Allgemeiner können auch Permutationen beliebiger [[Endliche Menge|endlicher]] [[Geordnete Menge|geordneter Mengen]] betrachtet werden, für die mathematische Analyse kann man sich jedoch auf die ersten <math>n</math> [[Natürliche Zahl|natürlichen Zahlen]] beschränken.

== Beispiele ==

=== Konkretes Beispiel ===

Die Menge der Fehlstände der Permutation

: <math>\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 2 & 4 \end{pmatrix} \in S_5</math>

ist

: <math>\operatorname{inv}(\pi) = \left\{ (1,3), (1,4), (2,3), (2,4), (2,5)\right\}</math>.

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

=== Allgemeinere Beispiele ===

Die [[identische Permutation]] <math>\operatorname{id}</math> ist die einzige Permutation ohne Fehlstände, also

: <math>\operatorname{inv}(\operatorname{id}) = \{ \}</math>.

Eine [[Nachbarvertauschung]] <math>\tau_{i,i+1} = ( ~ i ~~ i+1 ~ )</math> generiert genau einen Fehlstand

: <math>\operatorname{inv}(\tau_{i,i+1}) = \{ (i,i+1) \}</math>.

Eine [[Vertauschung|Transposition]] <math>\tau_{i,j} = ( ~ i ~~ j ~ )</math> mit <math>i<j</math> weist die folgenden <math>2(j-i)-1</math> Fehlstände auf:

: <math>\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 \}</math>.

== Anzahl ==

=== Fehlstandszahl ===

{| class="wikitable float-right" style="text-align:center"
|+ Fehlstände der Permutationen in ''S3''
|- class="hintergrundfarbe8"
! Nr.
! Permutation
! Fehlstände
! Anzahl
|-
|class="hintergrundfarbe8"| 0 || (1,2,3) ||style="text-align:left"| - || 0
|-
|class="hintergrundfarbe8"| 1 || (1,3,2) ||style="text-align:left"| (2,3) || 1
|-
|class="hintergrundfarbe8"| 2 || (2,1,3) ||style="text-align:left"| (1,2) || 1
|-
|class="hintergrundfarbe8"| 3 || (2,3,1) ||style="text-align:left"| (1,3),(2,3) || 2
|-
|class="hintergrundfarbe8"| 4 || (3,1,2) ||style="text-align:left"| (1,2),(1,3) || 2
|-
|class="hintergrundfarbe8"| 5 || (3,2,1) ||style="text-align:left"| (1,2),(1,3),(2,3) || 3
|}

Die Anzahl der Fehlstände <math>| \operatorname{inv}(\pi) |</math> einer Permutation <math>\pi</math> 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 (Permutation)|Vorzeichen]] einer Permutation ermitteln, denn es gilt

: <math>\operatorname{sgn}(\pi) = (-1)^{| \operatorname{inv}(\pi) |}</math>.

Ist die Fehlstandszahl gerade, so spricht man von einer geraden Permutation, ansonsten von einer ungeraden Permutation. Die Fehlstandszahl der [[Inverse Permutation|inversen Permutation]] <math>\pi^{-1}</math> ist identisch mit der Fehlstandszahl der Ausgangspermutation <math>\pi</math>, das heißt

: <math>| \operatorname{inv}(\pi^{-1}) | = | \operatorname{inv}(\pi) |</math>,

denn die Menge der Fehlstände der inversen Permutation hat die Darstellung<ref name="knuth14" />

: <math>\operatorname{inv}(\pi^{-1}) = \{ (\pi(j), \pi(i)) \mid (i,j) \in \operatorname{inv}(\pi) \}</math>.

=== Verteilung ===

{| class="wikitable float-right" style="text-align:right"
|+ Anzahl der Permutationen von ''n'' Elementen mit ''k'' Fehlständen
|- class="hintergrundfarbe8"
|style="text-align:center; width:2em;"| <math>{}_{k} \! \diagdown \!\! {}^{n}</math>
|style="width:2em"| 1
|style="width:2em"| 2
|style="width:2em"| 3
|style="width:2em"| 4
|style="width:2em"| 5
|style="width:2em"| 6
|-
|class="hintergrundfarbe8" style="text-align:center"| 0 || 1 || 1 || 1 || 1 || 1 || 1
|-
|class="hintergrundfarbe8" style="text-align:center"| 1 || 0 || 1 || 2 || 3 || 4 || 5
|-
|class="hintergrundfarbe8" style="text-align:center"| 2 || 0 || 0 || 2 || 5 || 9 || 14
|-
|class="hintergrundfarbe8" style="text-align:center"| 3 || 0 || 0 || 1 || 6 || 15 || 29
|-
|class="hintergrundfarbe8" style="text-align:center"| 4 || 0 || 0 || 0 || 5 || 20 || 49
|-
|class="hintergrundfarbe8" style="text-align:center"| 5 || 0 || 0 || 0 || 3 || 22 || 71
|-
|class="hintergrundfarbe8" style="text-align:center"| 6 || 0 || 0 || 0 || 1 || 20 || 90
|-
|class="hintergrundfarbe8" style="text-align:center"| 7 || 0 || 0 || 0 || 0 || 15 || 101
|-
|class="hintergrundfarbe8" style="text-align:center"| 8 || 0 || 0 || 0 || 0 || 9 || 101
|-
|class="hintergrundfarbe8" style="text-align:center"| 9 || 0 || 0 || 0 || 0 || 4 || 90
|-
|class="hintergrundfarbe8" style="text-align:center"| 10 || 0 || 0 || 0 || 0 || 1 || 71
|-
|class="hintergrundfarbe8" style="text-align:center"| 11 || 0 || 0 || 0 || 0 || 0 || 49
|-
|class="hintergrundfarbe8" style="text-align:center"| 12 || 0 || 0 || 0 || 0 || 0 || 29
|-
|class="hintergrundfarbe8" style="text-align:center"| 13 || 0 || 0 || 0 || 0 || 0 || 14
|-
|class="hintergrundfarbe8" style="text-align:center"| 14 || 0 || 0 || 0 || 0 || 0 || 5
|-
|class="hintergrundfarbe8" style="text-align:center"| 15 || 0 || 0 || 0 || 0 || 0 || 1
|-
|class="hintergrundfarbe8"| Summe || 1 || 2 || 6 || 24 || 120 || 720
|}

Die Anzahl der <math>n</math>-stelligen Permutationen mit genau <math>k</math> Fehlständen ist definiert als

: <math>I_{n,k} = \# \left\{ \pi \in S_n \mid | \operatorname{inv}(\pi) | = k \right\}</math>.

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

: <math>k_{\max} = \frac{n(n-1)}{2}</math>

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

: <math>I_{n,k_{\max}-k} = I_{n,k}</math>.

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

: <math>I_{n,k} = I_{n,k-1} + I_{n-1,k} - I_{n-1,k-n}</math>

und die Summendarstellung

: <math>I_{n,k} = \sum_{j=0}^{n-1} I_{n-1,k-j}</math>.

=== Erzeugende Funktion ===

Die [[erzeugende Funktion]] für die Anzahl der Fehlstände hat die Form

: <math>G_n(x) = \sum_{k=0}^{k_\max} I_{n,k} \, x^k = \prod_{j=1}^n \frac{1-x^j}{1-x}</math>.

Dieses Resultat geht auf [[Olinde Rodrigues]] (1839) zurück.<ref>{{Literatur |Autor=Donald E. Knuth |Titel=The Art of Computer Programming, Volume 3: Sorting and Searching |Datum= |Seiten=15}}</ref>

=== Erwartungswert und Varianz ===

Der [[Erwartungswert]] der Fehlstandszahl <math>X</math> einer ([[Diskrete Gleichverteilung|gleichverteilt]]) [[Zufällige Permutation|zufälligen Permutation]] aus <math>S_n</math> beträgt

: <math>\operatorname{E}( X ) = \sum_{j=1}^{n} \frac{j-1}{2} = \frac{n(n-1)}{4}</math>,

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 (Stochastik)|Varianz]] der Fehlstandszahl einer zufälligen Permutation gilt entsprechend

: <math>\operatorname{Var}( X ) = \sum_{j=1}^{n} \frac{j^2-1}{12} = \frac{n(2n+5)(n-1)}{72}</math>,

wodurch auch die [[Standardabweichung (Wahrscheinlichkeitstheorie)|Standardabweichung]] der Fehlstandszahl mit einem Wert von etwa <math>\tfrac16 n^{3/2}</math> vergleichsweise groß ausfällt.<ref>{{Literatur |Autor=Donald E. Knuth |Titel=The Art of Computer Programming, Volume 3: Sorting and Searching |Datum= |Seiten=16}}</ref> Die Anzahl der Fehlstände einer zufälligen Permutation ist für <math>n \to \infty</math> asymptotisch [[Normalverteilung|normalverteilt]].<ref>{{Literatur |Autor=Vladimir Nikolaevič Sačkov |Titel=Probabilistic Methods in Combinatorial Analysis |Verlag=Cambridge University Press |Datum=1997 |Seiten=30}}</ref>

== Darstellungen ==

=== Inversionstafel ===

{| class="wikitable float-right" style="text-align:center"
|+ Inversionstafeln der Permutationen in ''S3''
|- class="hintergrundfarbe8"
!style="width:2em"| Nr.
!style="width:8em"| Permutation
!style="width:8em"| Inversionstafel
|-
|class="hintergrundfarbe8"| 0 || (1,2,3) || (0,0,0)
|-
|class="hintergrundfarbe8"| 1 || (1,3,2) || (0,1,0)
|-
|class="hintergrundfarbe8"| 2 || (2,1,3) || (1,0,0)
|-
|class="hintergrundfarbe8"| 3 || (3,1,2) || (2,0,0)
|-
|class="hintergrundfarbe8"| 4 || (2,3,1) || (1,1,0)
|-
|class="hintergrundfarbe8"| 5 || (3,2,1) || (2,1,0)
|}

Die '''Inversionstafel''' oder der '''Inversionsvektor''' einer Permutation <math>\pi \in S_n</math> ordnet jeder Zahl <math>1 \leq j \leq n</math> die Anzahl der Fehlstände zu, die sie erzeugt. Bezeichnet

: <math>b_j = \# \left\{ i \in \{ 1, \ldots , n \} \mid (\pi^{-1}(i),\pi^{-1}(j)) \in \operatorname{inv}(\pi) \right\}</math>

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

: <math>I(\pi) = ( \, b_1, ~ b_2, ~ \ldots , ~ b_n \, )</math>.

Da die Zahl <math>j</math> höchstens <math>n-j</math> Fehlstände erzeugen kann, gilt <math>0 \leq b_j \leq n-j</math> und somit immer <math>b_n=0</math>. Die Fehlstandszahl der Permutation ergibt sich dann als Summe

: <math>| \operatorname{inv}(\pi) | = b_1 + \ldots + b_n</math>.

Aus der Inversionstafel <math>I(\pi)</math> lässt sich umgekehrt die zugrundeliegende Permutation <math>\pi</math> ermitteln. Hierzu bestimmt man der Reihe nach die relativen Platzierungen der Zahlen <math>n, n-1, \ldots , 1</math>, wobei <math>b_i</math> jeweils angibt, an welcher Position die Zahl <math>i</math> innerhalb der bereits betrachteten Zahlen auftritt. Dabei steht <math>b_j=0</math> für die erste Stelle, <math>b_j=1</math> 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 <math>b_1, \ldots , b_n</math> der Inversionstafel innerhalb der vorgegebenen Grenzen unabhängig voneinander gewählt werden können, während die Zahlen <math>\pi(1), \ldots , \pi(n)</math> [[paarweise verschieden]] sein müssen.<ref>{{Literatur |Autor=Donald E. Knuth |Titel=The Art of Computer Programming, Volume 3: Sorting and Searching |Datum= |Seiten=13}}</ref>

'''Beispiel'''

In obigem Beispiel ist die Inversionstafel

: <math>I(\pi) = ( \, 2, ~ 2, ~ 0, ~ 1, ~ 0 \, )</math>.

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

: <math>( \, 5 \, ), ~ ( \, 5, ~ 4 \, ), ~ ( \, 3, ~ 5, ~ 4 \, ), ~ ( \, 3, ~ 5, ~ 2, ~ 4 \, )</math>   und   <math>( \, 3, ~ 5, ~ 1, ~ 2, ~ 4 \, )</math>.

=== Lehmer-Code ===

{| class="wikitable float-right" style="text-align:center"
|+ Lehmer-Codes der Permutationen in ''S3''
|- class="hintergrundfarbe8"
!style="width:2em"| Nr.
!style="width:8em"| Permutation
!style="width:8em"| Lehmer-Code
|-
|class="hintergrundfarbe8"| 0 || (1,2,3) || (0,0,0)
|-
|class="hintergrundfarbe8"| 1 || (1,3,2) || (0,1,0)
|-
|class="hintergrundfarbe8"| 2 || (2,1,3) || (1,0,0)
|-
|class="hintergrundfarbe8"| 3 || (2,3,1) || (1,1,0)
|-
|class="hintergrundfarbe8"| 4 || (3,1,2) || (2,0,0)
|-
|class="hintergrundfarbe8"| 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

: <math>l_i = \# \left\{ j \in \{ 1, \ldots , n \} \mid (i,j) \in \operatorname{inv}(\pi) \right\}</math>

die Anzahl der Zahlen, die in der Tupeldarstellung von <math>\pi</math> rechts von <math>\pi(i)</math> stehen und kleiner als <math>\pi(i)</math> sind, dann ist der Lehmer-Code einer Permutation der Vektor

: <math>L(\pi) = ( \, l_1, ~ l_2, ~ \ldots , ~ l_n \, )</math>.

Auch hier gilt <math>0 \leq l_i \leq n-i</math> und somit immer <math>l_n=0</math>. Die Fehlstandszahl der Permutation ergibt sich entsprechend als Summe

: <math>| \operatorname{inv}(\pi) | = l_1 + \ldots + l_n</math>.

Aus dem Lehmer-Code <math>L(\pi)</math> lässt sich ebenfalls die zugrundeliegende Permutation <math>\pi</math> ermitteln. Hierzu notiert man zunächst alle Zahlen von <math>1</math> bis <math>n</math> hintereinander. Im Folgenden entfernt man aus dieser Liste jeweils im <math>i</math>-ten Schritt die <math>(l_i+1)</math>-te Zahl und notiert diese dann als <math>\pi(i)</math>. 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

: <math>L(\pi) = ( \, 2, ~ 3, ~ 0, ~ 0, ~ 0 \, )</math>.

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

: <math>( \, 3 \, ), ~ ( \, 3, ~ 5 \, ), ~ ( \, 3, ~ 5, ~ 1 \, ), ~ ( \, 3, ~ 5, ~ 1, ~ 2 \, )</math>   und   <math>( \, 3, ~ 5, ~ 1, ~ 2, ~ 4 \, )</math>.

=== Rothe-Diagramm ===

{| class="wikitable float-right" style="text-align:center"
|+ Rothe-Diagramm der Permutation (3,5,1,2,4)
|- class="hintergrundfarbe8"
|style="width:2.5em"|
|style="width:2.5em"| 1
|style="width:2.5em"| 2
|style="width:2.5em"| 3
|style="width:2.5em"| 4
|style="width:2.5em"| 5
|style="width:2.5em"| ''l''
|- style="height:2.5em"
|class="hintergrundfarbe8"| 1 || <math>\times</math> || <math>\times</math> || <math>\bullet</math> || || || 2
|- style="height:2.5em"
|class="hintergrundfarbe8"| 2 || <math>\times</math> || <math>\times</math> || || <math>\times</math> || <math>\bullet</math> || 3
|- style="height:2.5em"
|class="hintergrundfarbe8"| 3 || <math>\bullet</math> || || || || || 0
|- style="height:2.5em"
|class="hintergrundfarbe8"| 4 || || <math>\bullet</math> || || || || 0
|- style="height:2.5em"
|class="hintergrundfarbe8"| 5 || || || || <math>\bullet</math> || || 0
|- style="height:2.5em"
|class="hintergrundfarbe8"| ''b'' || 2 || 2 || 0 || 1 || 0 ||
|}

Eine weitere Möglichkeit, die Fehlstände einer Permutation <math>\pi \in S_n</math> darzustellen, ist das '''Rothe-Diagramm''' (benannt nach [[Heinrich August Rothe]]). In einem Schema bestehend aus <math>n \times n</math> Feldern wird zunächst in jeder Zeile <math>k</math> diejenige Spalte <math>l</math> mit einem Punkt markiert, für die <math>\pi(k) = l</math> gilt. Diese Felder entsprechen gerade den Einträgen mit Wert <math>1</math> 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 <math>(k,l)</math> genau dann mit einem Kreuz markiert, wenn <math>(k,\pi^{-1}(l))</math> ein Fehlstand von <math>\pi</math> ist.<ref name="knuth14">{{Literatur |Autor=Donald E. Knuth |Titel=The Art of Computer Programming, Volume 3: Sorting and Searching |Datum= |Seiten=14}}</ref>

Aus dem Rothe-Diagramm lässt sich sowohl die Inversionstafel, als auch der Lehmer-Code ablesen. Die Zahl <math>b_j</math> entspricht gerade der Anzahl der Kreuze in der Spalte <math>j</math> und die Zahl <math>l_i</math> der Anzahl der Kreuze in der Zeile <math>i</math>. [[Transponierte Matrix|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 <math>(k,l)</math> ein Kreuz auf, dann gilt dies für das Diagramm der zugehörigen inversen Permutation im Feld <math>(l,k)</math>. Aufgrund der Symmetrieeigenschaft des Rothe-Diagramms gilt demnach für die inverse Permutation<ref name="knuth14" />

: <math>I(\pi^{-1}) = L(\pi)</math>   und   <math>L(\pi^{-1}) = I(\pi)</math>.

Für [[selbstinverse Permutation]]en, also Permutationen, für die <math>\pi^{-1}=\pi</math> gilt, stimmen demnach Inversionstafel und Lehmer-Code überein.

=== Permutationsgraph ===
[[Datei:Permutation graph.svg|mini|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 [[Permutation#Graphdarstellung|Graphdarstellung]] einer Permutation) zugeordnet werden. Der Permutationsgraph einer Permutation <math>\pi \in S_n</math> ist ein [[ungerichteter Graph]] <math>G=(V,E)</math> mit der [[Knoten (Graphentheorie)|Knotenmenge]]

: <math>V = \{ 1, \ldots , n \}</math>

und der [[Kante (Graphentheorie)|Kantenmenge]]

: <math>E = \{ (\pi(i),\pi(j)) \mid (i,j) \in \operatorname{inv}(\pi) \}</math>.

Die Kanten des Permutationsgraphen verbinden also diejenigen Zahlenpaare, die einen Fehlstand erzeugen. Permutationsgraphen können auch geometrisch als [[Schnittgraph]]en der [[Strecke (Geometrie)|Strecken]]

: <math>S_i = [(i,0),(\sigma(i),1)]</math>

für <math>i=1, \ldots , n</math> 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 <math>G</math>, als auch sein [[Komplementgraph]] <math>\bar{G}</math> [[Vergleichbarkeitsgraph]]en sind. Der Komplementgraph entspricht dabei dem Permutationsgraphen der [[Reverse Permutation|reversen Permutation]] <math>(\pi(n), \ldots , \pi(1))</math>.

'''Beispiel'''

Beispielsweise besitzt der Permutationsgraph der Permutation <math>(4,3,5,1,2) \in S_5</math> die Kantenmenge

: <math>E = \{ (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4) \}</math>.

== Verwendung ==
=== Aufzählung von Permutationen ===

Fasst man die Inversionstafel <math>(b_1, \ldots , b_n)</math> beziehungsweise den Lehmer-Code <math>(l_1, \ldots , l_n)</math> als Zahl in einem [[Fakultätsbasiertes Zahlensystem|fakultätsbasierten Zahlensystem]] auf, lässt sich jeder Permutation <math>\pi \in S_n</math> eine eindeutige Nummer in der Menge <math>\{ 0 , \ldots , n!-1 \}</math> zuweisen. Aus der Inversionstafel erhält man so die Nummer

: <math>z(\pi) = \sum_{i=1}^n b_i \cdot (n-i)!</math>

und aus dem Lehmer-Code die Nummer

: <math>z'(\pi) = \sum_{i=1}^n l_i \cdot (n-i)!</math>.

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 <math>i>j</math> statt <math>i<j</math> und/oder <math>\pi(i)<\pi(j)</math> statt <math>\pi(i)>\pi(j)</math> 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.<ref>{{Literatur |Autor=Donald E. Knuth |Titel=The Art of Computer Programming, Volume 3: Sorting and Searching |Datum= |Seiten=18}}</ref>

'''Beispiel'''

Für die Permutation <math>\pi = ( \, 3, ~ 5, ~ 1, ~ 2, ~ 4 \, )</math> erhält man aus der zugehörigen Inversionstafel <math>I(\pi)</math> die Nummer

: <math>z(\pi) = 2 \cdot 4! + 2 \cdot 3! + 0 \cdot 2! + 1 \cdot 1! + 0 \cdot 0! = 61</math>

und aus dem zugehörigen Lehmer-Code <math>L(\pi)</math> die Nummer

: <math>z'(\pi) = 2 \cdot 4! + 3 \cdot 3! + 0 \cdot 2! + 0 \cdot 1! + 0 \cdot 0! = 66</math>.

=== Anordnung von Permutationen ===
[[Datei:Symmetric group 4; Cayley graph 1,2,6 (3D).svg|mini|[[Hasse-Diagramm]] ([[Cayley-Graph]]) der Permutationen in ''S4'']]

Weiter lässt sich durch Betrachtung der Fehlstände auf der Menge der <math>n</math>-stelligen Permutationen eine [[partielle Ordnung]] angeben. Eine solche Ordnungsrelation <math>\leq</math> wird für Permutationen <math>\pi, \sigma \in S_n</math> durch

: <math>\pi \leq \sigma \Leftrightarrow \operatorname{inv}(\pi) \subseteq \operatorname{inv}(\sigma)</math>

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-Diagramm]]s veranschaulichen. Zwei Permutationen sind dabei durch eine [[Kante (Graphentheorie)|Kante]] verbunden, wenn sie durch eine [[Vertauschung|Nachbarvertauschung]] auseinander hervorgehen. Die Knoten und Kanten des Hasse-Diagramms bilden einen [[Cayley-Graph]]en, der [[Isomorphie von Graphen|isomorph]] zum Kantengraphen des entsprechenden [[Permutaeder]]s ist.

'''Beispiel'''

In dem nebenstehenden Hasse-Diagramm der Permutationen der [[Symmetrische Gruppe|symmetrischen Gruppe]] <math>S_4</math> 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 <math>\tau_{12}</math>, <math>\tau_{23}</math> und <math>\tau_{34}</math>, 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 [[Cramersche Regel|cramerschen Regel]] zur Angabe der Lösung [[Lineares Gleichungssystem|linearer Gleichungssysteme]] definierte er die [[Determinante]] einer quadratischen Matrix <math>A=(a_{ij})</math> durch

: <math>\det(A) = \sum_{\pi \in S_n} \left( (-1)^{| \operatorname{inv}(\pi) |} \prod_{i=1}^n a_{i, \pi(i)} \right)</math>,

wobei die Summe über alle <math>n</math>-stelligen Permutation läuft.<ref>{{Literatur |Autor=Thomas Muir |Titel=Theory of determinants in the historical order of development |Band=1 |Verlag=Macmillan and Co |Datum=1906 |Seiten=13}}</ref> 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.<ref>{{Literatur |Autor=Thomas Muir |Titel=Theory of determinants in the historical order of development |Band=1 |Verlag=Macmillan and Co |Datum=1906 |Seiten=25,134}}</ref> Der deutsche Begriff „Fehlstand“ wurde Anfang des 20. Jahrhunderts von [[Gerhard Kowalewski]] popularisiert.<ref>{{Literatur |Autor=Gerhard Kowalewski |Titel=Einführung in die Determinantentheorie einschließlich der unendlichen und der Fredholmschen Determinanten |Verlag=Veit & Co. |Datum=1909}}</ref>

== Literatur ==
* {{Literatur
|Autor=[[Albrecht Beutelspacher]]
|Titel=Lineare Algebra. Eine Einführung in die Wissenschaft der Vektoren, Abbildungen und Matrizen
|Auflage=6.
|Verlag=Vieweg
|Datum=2009
|ISBN=3-528-56508-X}}
* {{Literatur
|Autor=[[Siegfried Bosch]]
|Titel=Lineare Algebra
|Auflage=4. überarbeitete
|Verlag=Springer
|Datum=2009
|ISBN=3-540-76437-2}}
* {{Literatur
|Autor=[[Donald E. Knuth]]
|Titel=The Art of Computer Programming
|Band=Volume 3: Sorting and Searching
|Auflage=2.
|Verlag=Addison-Wesley
|Datum=1998
|ISBN=0-201-89685-0}}

== Weblinks ==
* {{MathWorld|title=Permutation Inversion|id=PermutationInversion}}

== Einzelnachweise ==
<references />

[[Kategorie:Permutationstheorie]]

Fehlstand - Versionsgeschichte

~2025-16775-1: /* Inversionstafel */