Permutationen – Serlo „Mathe für Nicht-Freaks“

Dieser Abschnitt ist noch im Entstehen und noch nicht offizieller Bestandteil des Buchs. Gib den Autoren Zeit, den Inhalt anzupassen!

Motivation für PermutationenBearbeiten

  • Permutationen stellen Umordnungen von Elementen dar (Anschauliches Beispiel: Hütchenspiel, Rubikwürfel)
  • Permutationen spielen bei der Berechnung der Determinate eine wichtige Rolle

DefinitionBearbeiten

Definition (Permutation)

Wir haben eine Menge von Zahlen   gegeben. Unter einer Permutation dieser Menge verstehen wir eine bijektive Abbildung von  .

Anschaulich bilden wir jede Zahl zwischen 1 und   auf irgendeine andere Zahl zwischen 1 und   ab. Dabei darf eine Zahl auch auf sich selbst abgebildet werden. Diese Abbildung soll bijektiv sein. Es dürfen also keine zwei Zahlen auf die selbe Zahl abgebildet werden und es muss jede Zahl getroffen werden.


Beispiel (Permutationen)

Ein Beispiel für eine Permutation ist die Abbildung  . Hier wird jede Zahl auf der rechten Seite des Gleichheitszeichens von genau einer Zahl links getroffen.

Nicht jede Abbildung der Menge   auf die Menge   ist eine Permutation. Zum Beispiel können wir die Abbildung   anschauen. Diese Abbildung ist keine Permutation, weil die Zahl auf 3 gleich von mehreren Werten getroffen wird.

Schreibweise für PermutationenBearbeiten

Permutationen können auf verschiedene Art und Weise dargestellt werden.

TabellennotationBearbeiten

Eine Permutation der Elementen   kann als eine Tabelle dargestellt werden. Diese Tabelle besteht aus zwei Zeilen.

  • In der oberen Zeile stehen die Nummern 1 von   in aufsteigender Reihenfolge.
  • In der unteren Zeile stehen die Nummer 1 von   in irgendeiner umgeordneten Reihenfolge.

Die Art und Weise wie die Zahlen in der zweiten Zeile umgeordnet sind, gibt unsere Permutation an.

Schauen wir uns zum Beispiel die Permutation   an, welche durch die Funktionswerte   und   gegeben ist.

Diese Permutation wird wie folgt als Tabelle geschrieben.  

  • Ursprünglich liegt die Zahl 1 auf der ersten Position, die Zahl 2 auf der zweiten Position, die 3 auf der dritten Position usw.
  • Nach Anwendung der Permutation befindet sich an der ersten Position die Zahl 2 an der zweiten Position die Zahl 3, an der dritten Position die Zahl 1 usw.

Beispiel (Tabellennotation)

Folgende Liste enthält alle 6 Permutationen der Menge   in Tabellennotation:  

TupelnotationBearbeiten

Eine etwas kompaktere Art der Darstellung ist die Darstellung als Tupel. Diese Darstellung erhalten wir, wenn wir aus der Tabellenform die erste Zeile rauslöschen und nur die zweite Zeile nehmen. Für das vorherige Beispiel   erhalten wir damit die Tupeldarstellung  .

Die Permutationen der Menge   lauten in Tupelnotation:  

ZyklennotationBearbeiten

Anschaulich gesprochen ist ein Zyklus eine Permutation, wo alle Elemente einen Schritt im Kreis bewegt werden, zum Beispiel  . Die Elemente 2 bis 4 wandern einen Schritt nach links. Das Element 1 fällt links raus und ganz rechts wieder eingefügt. Jede Permutation kann in mehrere unabhängige Zyklen zerlegt werden.

  • Definition Zyklus


Beispiel (Zyklennotation)

Schauen wir uns folgende Permutation an:  

Wir möchten die Zyklen dieser Permutation untersuchen. Dazu schauen wir uns an, was mit der Zahl 1 passiert.

  • Wenden wir die Permutation einmal an, so wird die Zahl 1 auf die Zahl 2 abgebildet.
  • Wenden wir die Permutation nochmals an, so wird die Zahl 2 auf die Zahl 4 abgebildet.
  • Bei der dritten Anwendung wird die Zahl 4 wieder auf die Zahl 1 abgebildet.
  • Damit haben wir einen Zyklus   gefunden.
  • Diese drei Zahlen werden von unserer Permutation im Kreis bewegt:  .

Damit haben wir die Zahlen 1, 2 und 4 schon mit einem Zyklus abgedeckt.

Schauen wir uns nun an, was mit der Zahl 3 passiert:

  • Wenden wir die Permutation einmal an, so wird die Zahl 3 auf die Zahl 5 abgebildet.
  • Wenden wir die Permutation nochmals an, so wird die Zahl 5 wieder auf die Zahl 3 abgebildet.
  • Damit haben wir einen weiteren Zyklus   gefunden.
  • Dieser Zyklus vertauscht die Zahlen 3 und 5 miteinander.

Beiden gefunden Zyklus decken bereits alle Zahlen zwischen 1 und 5 ab. Daher müssen keine weiteren Zyklen mehr suchen.

Die Permutation   zerfällt also insgesamt in zwei Zyklen   und  . In Kurznotation schreiben wir diese Zyklen als   und  . Die ganze Permutation hat damit die Zyklendarstellung  .


Beispiel (Zyklennotation)

Folgende Liste enthält alle 6 Permutationen der Menge   in Zyklennotation:   Mit   schreiben wir Identität, also diejenige Permutation, welche keine Zahlen ändert.

GruppenstrukturBearbeiten

  • Zwei Permutationen können miteinander verknüpft werden
  • Verknüpfung von Permutationen ist nicht kommutativ
 (Achtung klar machen, ob man in der Notation von rechts nach links oder andersrum auswertet)
  • Es gibt eine Permutation, die nichts tut [1, 2, 3] (neutrales Element)
  • Eine Permutation hat eine inverse Permutation (inverses Element)
  • Die Menge der Permutation bildet eine Gruppe (mit Hintereinanderausführung)

Signum einer PermutationBearbeiten

  • Permutationen können in Transpositionen (Zweierzyklen) zerlegt werden.
  • Vorgehensweise: Permutation in Zyklen zerlegen, anschließend jeden Zyklus in Zweierzyklen zerlegen mittels der Formel  
  • Die Zerlegung in Transpositionen ist nicht eindeutig
  • Jedoch braucht man in jeder Zerlegung immer entweder gerade viele oder ungerade viele Transposition
  • Definition: Signum einer Permutation (1 = gerade Permutation, -1 ungerade Permutation)
  • Formel für das Signum   mit  
  • Analogon zur Vorzeichen bei ganzen Zahlen (negativ * negativ ist positiv)
  • Produktregel für das Signum  
  • Gerade Permutationen bilden eine Untergruppe, Signum ist ein Gruppenhomomorphismus
  • Signum lässt sich anhand der Zyklenstruktur gut ablesen