Mathe für Nicht-Freaks: Permutationen

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Motivation für Permutationen[Bearbeiten]

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

Definition[Bearbeiten]

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 sich wieder selber 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 Permutationen[Bearbeiten]

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

Tabellennotation[Bearbeiten]

Eine Permutation der Elementen kann als eine Tabelle dargestellt werden. Diese Tabelle bestehet 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 , 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:

Tupelnotation[Bearbeiten]

Eine etwas kompakete 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 \{1, 2, 3\} lauten in Tupelnotation:

Zyklennotation[Bearbeiten]

Anschaulich gesprochen ist ein Zyklus eine Permutation, wo alle Elemente einen Schritt im Kreis gewegt 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 Zahl 1 die 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.

Gruppenstruktur[Bearbeiten]

  • 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 Permutation[Bearbeiten]

  • Permutationen können in Transpositionen (Zweierzyklen) zerlegt weren.
  • 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