Anzahl der Umkehrungen in der Permutation
Umkehrungen in der Kombinatorik sind die Anzahl von Elementpaaren, bei denen das nächste Element eine kleinere Zahl als das vorherige hat. Manchmal ist es wichtig, den Unterschied zwischen einer willkürlichen Permutation und der lexigraphisch geringsten Anzahl von Verstößen gegen die zunehmende Reihenfolge der Werte ihrer Elemente zu quantifizieren. Jedes Elementpaar, bei dem eine solche Verletzung ihrer gegenseitigen Position in der Permutation auftritt, wird als Inversion bezeichnet.
.Umkehrungen von Permutationen
Verwenden Sie einen Inversionsvektor, um Inversions über Permutationselemente kompakt zu schreiben (V1,…Vj,…Vn) und die Inversionstabelle (W1,…Wj,…Wn). Diese beiden Schreibformen identifizieren die Inversionszahlen für alle Permutationselemente.
Zusammensetzung des Vektors und der Inversionstabelle für die digitale Permutation P=(5,9,1,8,2,6,4,7,3) im folgenden Beispiel werden die Positionen aller Elemente zur Veranschaulichung indiziert:
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | pj | 5 | 9 | 1 | 8 | 2 | 6 | 4 | 7 | 3 | Vj | 0 | 0 | 2 | 1 | 3 | 2 | 4 | 2 | 6 | Wj | 2 | 3 | 6 | 4 | 0 | 2 | 2 | 1 | 9 |
Insbesondere in diesem Beispiel V8=2, weil links vom Element P8=7 es gibt 2 Elemente in der Permutation P2=9 und P4=8 mit mehr Wert als 7. Andererseits, W8=1, weil auf der linken Seite des Elements mit dem Wert 8 (das ist P4) es gibt nur 1 Element in der Permutation (P2=9), der Wert ist größer als 8. Ebenso können Sie die Auswahl der Größen der übrigen Komponenten des Vektors und der Inversionstabelle in diesem Beispiel rechtfertigen. Beachten Sie auch, dass für jede Permutation die Werte der Vektorkomponenten und der Inversionstabelle mit den folgenden Verhältnissen verknüpft sind:
V1 = Wn = 0; Vj = Wi | i = Pj; Wj = Vi | Pi = j.
Zurück zu den integralen Schätzungen sollte beachtet werden, dass die Summe der Werte aller Komponenten eines Vektors oder einer Inversionstabelle die Gesamtzahl der Inversionen I der Permutation bestimmt. Insbesondere für das betrachtete Beispiel ist es gleich 20:
I(5, 9, 1, 8, 2, 6, 4, 7, 3) = 20.