Permutation Produkt von Transpositionen

Question

 Es sei n ∈ Z≥1. Zeigen Sie, dass sich jede Permutation in Sn als Produkt von Transpositionen schreiben lässt, d.h. für alle σ ∈ Sn existieren a1,...,ak,b1,...,bk ∈ {1,...,n} mit

σ = (a1 b1)(a2 b2)···(ak bk). 

Answer 1

sieht sehr nach vollständiger Induktion aus.
bei n=1 ist nicht viel zu machen.

hast du ein sigma ( ich schreib mal s) aus S_n+1, dann kannst du
die Zahl  (n+1) so lange mit ihrem rechten Nachbarn tauschen, bis sie am Ende
steht.
Dann stehen natürlich nicht unbedingt alle anderen auch an der richtigen Stelle,
aber es ist nur noch eine Permutation der ersten n Stück nötig, diese sei p1.

Die zum Einstellen von n+1 ans Ende benutzten Transpositionen ergeben
hintereinanderausgeführt eine Permutation p2.

Jetzt machst du als erstes die Permutation p1. Die läßt das n+1 hinten stehen
und ändert nur die ersten n.   Außerdem ist p1 aus S_n also nach Induktionsannahme
durch Transpositionen darstellbar.
Danach kommen jetzt die Transpositionen von p2 in umgekehrter Reihenfolge, also
sozusagen p2^{-1}.
also gilt s = p1 ° p2^{-1} und beide Faktoren sind durch Transpositionen
darstellbar,  also auch das Produkt.