Fehlstand

Grundidee und Definition

Ein Fehlstand, auch Fehlstellung oder Inversion, beschreibt bei einer Permutation eine vertauschte Reihenfolge zweier Elemente. Er ist ein Maß dafür, wie stark die durch eine Permutation erzeugte Zahlenfolge von der aufsteigenden Reihenfolge abweicht. Fehlstände sind unter anderem wichtig für das Vorzeichen von Permutationen, für die Nummerierung von Permutationen und für die Analyse von Sortierverfahren.

Für die symmetrische Gruppe Sₙ, also die Menge aller Permutationen von {1, …, n}, sei π = (π(1), π(2), …, π(n)). Ein Fehlstand ist ein Paar von Positionen (i, j), für das i < j und zugleich π(i) > π(j) gilt. Anders gesagt: Eine größere Zahl steht links von einer kleineren Zahl. Die Fehlstandsmenge lautet inv(π) = {(i, j) ∈ {1, …, n}² | i < j und π(i) > π(j)}.

Manchmal bezeichnet die Literatur statt des Positionspaares (i, j) das Wertepaar (π(i), π(j)) als Fehlstand. Die Definition lässt sich auf beliebige endliche geordnete Mengen übertragen; mathematisch genügt jedoch die Betrachtung der Zahlen 1 bis n.

Fehlstandszahl und Verteilung

Die Anzahl |inv(π)| der Fehlstände heißt Fehlstandszahl oder Inversionszahl. Sie misst die Unordnung einer Permutation. Sie bestimmt auch deren Vorzeichen: sgn(π) = (−1)^{|inv(π)|}.

Eine Permutation mit gerader Fehlstandszahl heißt gerade, eine mit ungerader Fehlstandszahl ungerade. Die inverse Permutation besitzt gleich viele Fehlstände wie die ursprüngliche Permutation: |inv(π⁻¹)| = |inv(π)|. Genauer gilt inv(π⁻¹) = {(π(j), π(i)) | (i, j) ∈ inv(π)}.

Die Anzahl der Permutationen von n Elementen mit genau k Fehlständen wird mit Iₙ,ₖ bezeichnet: Iₙ,ₖ = #{π ∈ Sₙ | |inv(π)| = k}. Es gilt Iₙ,₀ = 1, denn nur die identische Permutation hat keinen Fehlstand. Außerdem ist Iₙ,₁ = n − 1, weil es n − 1 Nachbarvertauschungen mit genau einem Fehlstand gibt. Die größtmögliche Fehlstandszahl beträgt kmax = n(n − 1)/2. Sie tritt genau bei der Permutation auf, welche die Reihenfolge aller Zahlen umkehrt. Die Verteilung ist symmetrisch: Iₙ,kmax−k = Iₙ,ₖ.

Mit Iₙ,ₖ = 0 für k < 0 oder k > kmax gelten die Rekursion Iₙ,ₖ = Iₙ,ₖ₋₁ + Iₙ₋₁,ₖ − Iₙ₋₁,ₖ₋ₙ sowie die Summenformel Iₙ,ₖ = Σⱼ₌₀ⁿ⁻¹ Iₙ₋₁,ₖ₋ⱼ. Die erzeugende Funktion lautet Gₙ(x) = Σₖ₌₀ᵏᵐᵃˣ Iₙ,ₖxᵏ = ∏ⱼ₌₁ⁿ (1 − xʲ)/(1 − x).

Bei einer gleichverteilt zufälligen Permutation ist die Fehlstandszahl X im Mittel E(X) = n(n − 1)/4. Ihre Varianz ist Var(X) = n(2n + 5)(n − 1)/72; die Standardabweichung ist ungefähr (1/6)n^(3/2). Für n → ∞ ist die Fehlstandszahl asymptotisch normalverteilt. Sortierverfahren wie Bubblesort, die in einem Schritt genau einen Fehlstand beseitigen, haben deshalb nicht nur im schlechtesten, sondern auch im durchschnittlichen Fall quadratische Laufzeit.

Inversionstafel und Lehmer-Code

Die Inversionstafel I(π) = (b₁, …, bₙ) ordnet jeder Zahl j die Anzahl der größeren Zahlen zu, die in der Tupeldarstellung links von j stehen. Es gilt bⱼ = #{i ∈ {1, …, n} | (π⁻¹(i), π⁻¹(j)) ∈ inv(π)}. Dabei gilt 0 ≤ bⱼ ≤ n − j, insbesondere bₙ = 0, und die Fehlstandszahl ist b₁ + … + bₙ. Aus einer Inversionstafel lässt sich die Permutation eindeutig zurückgewinnen: Man bestimmt n, n − 1, …, 1 nacheinander; bᵢ gibt jeweils die Position innerhalb der bereits betrachteten Zahlen an. Dabei bedeutet bⱼ = 0 die erste Stelle, bⱼ = 1 die zweite Stelle usw.

Der Lehmer-Code L(π) = (l₁, …, lₙ) ist dazu in gewisser Weise dual. lᵢ zählt die kleineren Zahlen rechts von π(i): lᵢ = #{j ∈ {1, …, n} | (i, j) ∈ inv(π)}. Auch hier gilt 0 ≤ lᵢ ≤ n − i, insbesondere lₙ = 0, und |inv(π)| = l₁ + … + lₙ. Zum Wiederherstellen der Permutation schreibt man zunächst 1 bis n auf. Im i-ten Schritt entfernt man die (lᵢ + 1)-te noch vorhandene Zahl und setzt sie als π(i) ein.

Beide Codes stehen jeweils in einer Eins-zu-Eins-Korrespondenz mit den Permutationen. Ihre Einträge können innerhalb ihrer Grenzen unabhängig gewählt werden, während die Werte einer Permutation paarweise verschieden sein müssen.

Diagramme und Graphen

Im Rothe-Diagramm einer Permutation π ∈ Sₙ werden in einem n × n-Schema zunächst Punkte gesetzt: In Zeile k liegt der Punkt in Spalte l genau dann, wenn π(k) = l. Ein Feld erhält ein Kreuz, wenn in derselben Spalte ein Punkt unterhalb und in derselben Zeile ein Punkt rechts davon liegt. Diese Kreuze entsprechen den Fehlständen; das Feld (k, l) ist genau dann markiert, wenn (k, π⁻¹(l)) ein Fehlstand ist.

Die Anzahl der Kreuze in Spalte j ist bⱼ der Inversionstafel, die Anzahl der Kreuze in Zeile i ist lᵢ des Lehmer-Codes. Durch Transponieren des Diagramms erhält man die Darstellung der inversen Permutation. Daher gilt I(π⁻¹) = L(π) und L(π⁻¹) = I(π). Für selbstinverse Permutationen mit π⁻¹ = π stimmen Inversionstafel und Lehmer-Code überein.

Der Permutationsgraph zu π ist ein ungerichteter Graph mit Knotenmenge V = {1, …, n} und Kantenmenge E = {(π(i), π(j)) | (i, j) ∈ inv(π)}. Eine Kante verbindet also zwei Zahlen, die einen Fehlstand bilden. Geometrisch können die Kanten als Schnittbeziehungen von Strecken Sᵢ = [(i, 0), (σ(i), 1)] zwischen zwei parallelen Geraden verstanden werden: Zwei Strecken schneiden sich genau dann, wenn ein Fehlstand vorliegt. Sowohl der Graph als auch sein Komplementgraph sind Vergleichbarkeitsgraphen; der Komplementgraph gehört zur reversen Permutation (π(n), …, π(1)).

Beispiele und Anwendungen

Für π = (3, 5, 1, 2, 4) ∈ S₅ ist inv(π) = {(1, 3), (1, 4), (2, 3), (2, 4), (2, 5)}. Die Fehlstandszahl ist also 5. Die zugehörige Inversionstafel ist I(π) = (2, 2, 0, 1, 0), der Lehmer-Code L(π) = (2, 3, 0, 0, 0). Die identische Permutation ist die einzige Permutation ohne Fehlstände. Eine Nachbarvertauschung τᵢ,ᵢ₊₁ = (i i+1) hat genau den Fehlstand (i, i+1). Eine Transposition τᵢ,ⱼ mit i < j hat 2(j − i) − 1 Fehlstände.

Inversionstafel und Lehmer-Code können als Zahlen in einem fakultätsbasierten Zahlensystem gelesen werden. Dadurch erhält jede Permutation aus Sₙ eine eindeutige Nummer von 0 bis n! − 1. Für die Inversionstafel gilt z(π) = Σᵢ₌₁ⁿ bᵢ·(n − i)!, für den Lehmer-Code z′(π) = Σᵢ₌₁ⁿ lᵢ·(n − i)!. Für π = (3, 5, 1, 2, 4) ergeben sich z(π) = 61 und z′(π) = 66. Beide Nummern stimmen nur bei selbstinversen Permutationen überein.

Fehlstandsmengen definieren außerdem eine partielle Ordnung auf Sₙ: π ≤ σ genau dann, wenn inv(π) ⊆ inv(σ). Das kleinste Element ist die identische Permutation, das größte die vollständig umgekehrte Reihenfolge. In einem Hasse-Diagramm sind zwei Permutationen durch eine Kante verbunden, wenn sie durch eine Nachbarvertauschung auseinander hervorgehen. Von unten nach oben erzeugt eine solche Kante jeweils genau einen Fehlstand.