Proposition - Permutationen lassen sich in disjunkte Zyklen zerlegen

• Involvierte Definitionen:
  • Fixpunkt
  • Permutation
  • Disjunkte Zyklen
• Veranstaltung: AlMa
• Referenz: } AlgoMathe KE1 - Abbildungen, Permutationen, Fakultät

⠀

Proposition: Permutationen lassen sich in disjunkte Zyklen zerlegen

Beweis

Wie bereits in Disjunkte Zyklen angesprochen:

• Zyklen können zu Permutationen verkettet werden.
• und Permutationen können in Zyklen aufgeteilt werden

Dass sich jede Permutation in paarweise disjunkte Zyklen zerlegen lässt, wollen wir nun noch formal zeigen.

Hierzu werden wir eine Induktion über die Anzahl der Fixpunkte einer Permutation führen.

Induktionsanfang

Sei eine Permutation mit ausschließlich Fixpunkten. Das bedeutet . Mit anderen Worten: ist die Identische Abbildung .

Wir können daher auch als Verkettung von Zyklen der Länge 1 schreiben (wie bereits in Fixpunkte demonstriert.)

Der Induktionsanfang hält also.

Induktionsannahme

Eine Permutation , die mindestens einen Fixpunkt hat, lässt sich in paarweise Disjunkte Zyklen zerlegen

Induktionsschritt

Sei eine Permutation ohne Fixpunkte.

Sei nun , dann ist und

mit

Wir können diese Kette so lange fortsetzen, bis sich wiederholt, also bis .

Jedes der Elemente mit ist dann Teil des Zyklus

Als Randnotiz: Dass dieser Fall (also ) irgendwann eintreten muss, wissen wir, weil Permutationen (und damit unser ) bijektiv sind.

Wir können nun eine neue Permutation bilden. Für diese Permutation soll gelten:

Oder in anderen Worten:

• alle Elemente des Zyklus sind Fixpunkte in ,
• der Rest wird wie von abgebildetet.

Daher gilt auch

Da nun also Fixpunkte hat, können wir unsere Induktionsannahme anwenden und in die disjunkten Zyklen mit zerlegen.

Die gesamte disjunkte Zerlegung von ist dann