TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 335

Sei eine Permutation von $\pi$ von { 1, 2, ..., n } in zweizeiliger Darstellung gegeben.

Unter der Inversionstafel von $\pi$ versteht man die Folge ${b_{1},b_{2},...,b_{n}}$, wobei $b_{k}\geq 0$ angibt, wieviele größere Zahlen in der zweiten Zeile links Element k stehen. Bestimmen Sie für die Permutation $\pi$ aus Aufgabe 119) die Inversionstafel.

Wie kann man bei Kenntnis der Inversionstafel die Permutation rekonstruieren? Demonstrieren Sie ein geeignetes Verfahren am obigen Beispiel.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Erstellen der Inversionstafel

Die Permutation $\pi$ in zweizeiliger Darstellung schaut so aus:

$\pi ={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\8&9&1&7&2&5&4&3&6\end{pmatrix}}$

Wenn man jetzt für jede Zahl der zweiten Zeile die Anzahl der Zahlen, die links davon und größer sind, erhält man die Inversionstafel:

• links von 8 sind 0 Zahlen größer als 8
• links von 9 sind 0 Zahlen größer als 9
• links von 1 sind 2 Zahlen größer als 1 (nämlich 8 und 9)
• .
• .
• links von 6 sind 3 Zahlen größer als 6 (nämlich 8, 9 und 7)

Damit erhält man als Inversionstafel:

1	2	3	4	5	6	7	8	9
0	0	2	2	3	3	4	5	3

Rekonstruieren der Permutation

Zum Rekonstruieren der Permutation aus der Inversionstafel sucht man nacheinander jeweils das kleinste Element der Permutation. Das kleinste Element ist am Anfang die 1. Hat man die 1 gefunden, kann man die Spalte der 1 ignorieren und das neue kleinste Element ist die 2, usw.

Das kleinste Element hat die Eigenschaft, dass alle Elemente die links davon stehen größer sind (Oh Mann, wer hätte das gedacht *g*).

Angenommen das kleinste Element steht an der Stelle k, so gilt immer:

$b_{k}=k-1$

Steht das kleinste Element z.B. an der 5. Stelle, dann steht in der Inversionstafel an der 5. Stelle der Wert 4.

Gibt es in der Inversionstafel zwei Elemente $b_{j}$ und $b_{k}$ mit $1\leq j<k\leq n$ und $b_{j}=j-1,b_{k}=k-1$, so ist immer das Element rechts (hier $b_{k}$) das kleinste Element.

Wäre $b_{j}$ da kleinste Element, gäbe es links von $b_{k}$ ein Element das kleiner ist, und somit könnte $b_{k}$ nur noch eine Wert von maximal k-2 haben, und nicht k-1.

Unten ist der Lösungsweg Schritt-für-Schritt ausgeführt. Die fettgedruckten Zahlen in der Inversionstafel sind die "möglichen" Positionen für das kleinste Element (sie erfüllen $b_{k}=k-1$), jeweils das Element rechts ist die richtige Position des kleinesten Elements. Die bereits verwendeten Positionen werden in den nachfolgenden Schritten ignoriert.

kleinstes Element	Inversionstafel	Permutation
1	1 2 3 4 5 6 7 8 9 0 0 2 2 3 3 4 5 3	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\&&1&&&&&&\end{pmatrix}}$
2	1 2 4 5 6 7 8 9 0 0 2 3 3 4 5 3	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\&&1&&2&&&&\end{pmatrix}}$
3	1 2 4 6 7 8 9 0 0 2 3 4 5 3	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\&&1&&2&&&3&\end{pmatrix}}$
4	1 2 4 6 7 9 0 0 2 3 4 3	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\&&1&&2&&4&3&\end{pmatrix}}$
5	1 2 4 6 9 0 0 2 3 3	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\&&1&&2&5&4&3&\end{pmatrix}}$
6	1 2 4 9 0 0 2 3	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\&&1&&2&5&4&3&6\end{pmatrix}}$
7	1 2 4 0 0 2	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\&&1&7&2&5&4&3&6\end{pmatrix}}$
8	1 2 0 0	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\8&&1&7&2&5&4&3&6\end{pmatrix}}$
9	2 0	${\begin{pmatrix}1&2&3&4&5&6&7&8&9\\8&9&1&7&2&5&4&3&6\end{pmatrix}}$

mfg, --W wallner