Induktionsbeweis zeigen, es geht um Zyklendarstellung/Transpositionen
-
Erklären Sie das Verfahren der vollständigne Induktion anhand eines Beweises der folgenden Aussage: Für n >= 2 lässt sich jede Permutation π € Sn als Produkt von Transpositionen darstellen.
Hinweis: Benützen Sie die Tatsache, dass jede Permutation in Zyklen zerlegt werden kann (Zyklendarstellung).Kann mir jemand einen weiteren Hinweis geben? Also ich kann alle π als Zyklendarstellung darstellen - no problem. Eine Transposition ist ein 2er-Zyklus = tauscht zwei Positionen. Wenn ich die irgendwie verknüpfe, soll der Zyklus auch dargestellt werden können (selbstverständlicherweise für n >= 2, sonst geht sich ja keine Transposition aus).
Okay, los geht's: Anfangsbedingung:
(1,2) bzw. (2,1), die Transposition dazu heißt (1 2), fertig.
Induktionsschritt:
Annahme: ∏(von 2 bis n) (a b) = π (darf ich das so überhaupt noch schreiben?!)
Behauptung: Hier dann n+1
Also ich habe Probleme den Text mathematisch zu formulieren und hinzuschreiben. Wie gehe ich vor?
MfG SideWinder
-
SideWinder schrieb:
Erklären Sie das Verfahren der vollständigne Induktion anhand eines Beweises der folgenden Aussage: Für n >= 2 lässt sich jede Permutation π € Sn als Produkt von Transpositionen darstellen.
Hinweis: Benützen Sie die Tatsache, dass jede Permutation in Zyklen zerlegt werden kann (Zyklendarstellung).Dieser Hinweis soll wohl in die Richtung gehen, dass man die Zyklen getrennt betrachten kann. Du musst also nur zeigen, dass du einen einzigen Zyklus (natürlich beliebiger Länge n >= 2) als Produkt von Transpositionen schreiben kannst.
Du musst dir dann noch überlegen, warum das schon reicht, um die ganze Aussage zu zeigen, und warum man Zyklen der Länge 1 ignorieren darf (hier musst du u.a. den Spezialfall betrachten, dass die gegebene Permutation ausschließlich aus Zyklen der Länge 1 besteht).Die Anfangsbedingung hast du schon hingeschrieben.
Im Schrittfall darfst du annehmen, dass du alle Zyklen der Länge n (mit n>=2) als Produkt von Transpositionen schreiben kannst. Dann nimmst du dir einen Zyklus der Länge n+1 und zeigst, wie man den als Produkt von Transpositionen schreibst, wobei du dafür die Induktionsannahme verwendest.
-
braucht man dazu wirklich den Satz von der Zyklenzerlegung?
Daß man 1 2 3 .. n durch Vertauschungen in jede beliebige Reihenfolge bringen kann, ist doch vollkommen klar, man tauscht erst die 1 an die Zielstelle, und wiederholt das dann (induktiv) mit 2 3 ... n, wobei man die 1 in Ruhe läßt.