Fehlstand

Alle Permutationen der Menge $\scriptstyle \{1,2,3,4\}$ mit zugehörigen Fehlstandszahlen (rechts)

Unter Fehlstand oder Inversion versteht man in der Kombinatorik ein Zahlenpaar, deren Reihenfolge durch eine Permutation vertauscht wird. Die Anzahl der Fehlstände einer Permutation heißt Fehlstandszahl oder Inversionszahl der Permutation. Über die Fehlstandszahl lässt sich beispielsweise das Signum einer Permutation ermitteln. Mit Hilfe einer Inversionstafel, die alle Fehlstände einer Permutation protokolliert, lässt sich jeder Permutation eine eindeutige Nummer zuweisen.

Definition

Ein Fehlstand einer Permutation der Menge $\{1,\ldots ,n\}$

$\pi ={\begin{pmatrix}1&2&\cdots &n\\\pi (1)&\pi (2)&\cdots &\pi (n)\end{pmatrix}}\in S_{n}$

ist ein Paar $(i,j)$, für das

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

gilt. Die Anzahl der Fehlstände einer Permutation heißt Fehlstandszahl oder Inversionszahl und mit $F(\pi )$ bezeichnet.

Beispiel

Die Fehlstände der Permutation

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

sind $(1,2),(1,4)$ und $(3,4)$, es gilt also $F(\pi )=3$.

Inversionstafel

Eine Inversionstafel ordnet jeder Zahl $1\leq i\leq n$ die Anzahl der Fehlstände zu, die sie erzeugt. Ist $b(i)$ die Zahl der Fehlstände der Form $(i,j)$, dann ist die Inversionstafel einer Permutation $\pi \in S_{n}$ gegeben durch

$I(\pi )={\begin{pmatrix}1&2&\ldots &n\\b(1)&b(2)&\ldots &b(n)\end{pmatrix}}$

Die Fehlstandszahl ergibt sich dann einfach als Summe $b(1)+\ldots +b(n)$. In obigem Beispiel ist die Inversionstafel

$I(\pi )={\begin{pmatrix}1&2&3&4\\2&0&1&0\end{pmatrix}}$

Aus der Inversionstafel einer Permutation lässt sich umgekehrt die zugrundeliegende Permutation eindeutig ermitteln. Fasst man den Vektor $(b(1),\ldots ,b(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.

Eigenschaften

• Die identische Permutation ist die einzige Permutation ohne Fehlstände.
• Die Permutationen mit genau einem Fehlstand sind die Nachbarschaftsvertauschungen.
• Die maximale Anzahl der Fehlstände in einer Permutation $\pi \in S_{n}$ beträgt ${\tfrac {n(n-1)}{2}}$, was genau dann der Fall ist, wenn die Permutation die Reihenfolge aller Zahlen umkehrt.
• Über die Inversionszahl lässt sich das Signum einer Permutation ermitteln. In einer geraden Permutation ist die Anzahl der Fehlstände gerade, in einer ungeraden Permutation ungerade.
• Mit Hilfe der Inversionszahl lässt sich auf der Menge der Permutationen eine partielle Ordnung definieren.
• Ist $(i,j)$ ein Fehlstand in $\pi$, dann ist $(\pi (i),\pi (j))$ ein Fehlstand in der inversen Permutation $\pi ^{-1}$.

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. Springer, 2009, ISBN 3-540-76437-2.