Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

III_26_titel_flugzeug

Sitzplatzpermutationen

Ben und Rike sitzen im Flieger und fliegen nach Hause. Wird ja auch Zeit, das Weihnachtsfest … Plötzlich knallt es. Es gibt einen ohrenbetäubenden Lärm, Ben wird von seinem Sitz hochgeschleudert und landet auf dem Nachbarsitz. Die anderen Fluggäste werden auch jeweils weiter zum nächsten Sitz expediert. Nur Rike nicht. Sie lacht.

Ben Was lachst Du?

Rike Die Sitzplatzpermutationsgruppe!

Ben Was?

Rike Ihr seid alle einen Platz weiter gerückt. Dieses Weiterrücken ist eine Aktion, dazu gibt es eine Gegenaktion, die das Weiterrücken vom Platz

n\; \longrightarrow \; n+1

rückgängig macht.

Ben Klar, von n+1 auf n.

Rike Richtig! Und die „Nullaktion“, wo keiner weiterrückt, ist die Identität:

\mathrm{Id}\;:\;n\; \longrightarrow\; n

n wird auf n abgebildet.

Ben Was ist die Permutationsgruppe? Wir hatten wenig lineare Algebra im Studium.

Rike Zunächst gibt es den Gruppenbegriff:

Gruppe

Eine Menge G mit einer Verknüpfung \circ von 2 Elementen g1 und g2 von G

\circ\;:\;G\; \times\; G\; \longrightarrow\; G

muß definiert sein, also

g_1\;\circ\;g_2\;=\;g_3\; \in\; G

ist immer ausführbar.

1-Element

Es gibt ein 1-Element e\; \in\; G sodass

e\;\circ\;g\;=\;g\;\circ\;e\;=\;g,\;   \forall\; g\; \in\; G

Inverses

Und als Letztes soll zu jedem g\; \in\; G stets ein „Inverses“ g^{-1}\; \in\; G existieren, sodass

 g^{-1}\;\circ\;g\;=\;g\;\circ\;g^{-1}\;=\;e

Ben Na, gut. Gibt’s triviale Beispiele?

Rike Die ganzen Zahlen mit der Addition als Verknüpfung oder die Restklassen mit der Restklassenaddition.

Ben Gut. Und die Permutationsgruppe?

Rike Die Permutationsgruppe Pn ist die Menge der bijektiven Abbildungen der Menge

M_n\;=\;\{ 1,\; 2,\; \dots,\; n\}

auf sich.

Ben Okay, dann gibt es n! Permutationen.

Rike Stimmt! Die Permutationsgruppe ist eine endliche Gruppe. Sie hat wirklich schöne Eigenschaften. Schau mal, wenn \pi eine Permutation ist, dann bildet \pi Mn auf Mn ab,

\pi\;:\;M_n\; \longrightarrow\; M_n

Permutation in Komponentenschreibweise

und komponentenweise kann man das so schreiben:

\pi i\;=\;j

Oder man kann es gleich auf die ganze Menge Mn anwenden und schreibt das mit einer Matrix:

Permutation in Matrixschreibweise

III_26_formel_01

Vereinfachte Schreibweise

Es ist üblich, die Spalten, die invariant bleiben, also für die

\pi j\;=\;j

ist, in der Matrix wegzulassen.

Verknüpfung in Pn

Die Verknüpfung in Pn ist die Nacheinanderausführung der Abbildungen. Das geht so: Wenn

III_26_formel_02

und

III_26_formel_03

sind, dann soll die Verknüpfung von \pi_1 und \pi_2

\pi_2\;\circ\;\pi_1

die Permutation \pi_2, angewendet auf die Permutation \pi_1 sein:

(\pi_2\;\circ\;\pi_1) i\;=\;\pi_2 (\pi_1i)

komponentenweise oder in Matrixschreibweise:

III_26_formel_04

Ben Hm, das lässt sich gut programmieren.

Rike Ja, lass uns mal aufschreiben, was jetzt passiert ist, sagen wir mal, wir haben 100 Sitzplätze,

n\; =\; 100,

und jeder Inhaber eines Platzes ist eins weitergerückt, außer mir, ich habe den Platz 1, aber nur heute im Flugzeug, Ben, dann schreibt sich das als

III_26_formel_05

Ben Okay. Ich bin vom Platz Nr. 2, aber nur heute, Rike, zu Platz Nr. 3 gekommen.

k-Zykel

Rike Für solche „Weiterrück-Permutationen“ gibt es einen Begriff: Wenn k von n Elementen immer eins weitergerückt werden:

\pi a_j\;=\;a_{j+1},\; j\;=\;1,\; \dots,\; k-1

\pi a_k\;=\;a_1

oder in Matrixschreibweise:

III_26_formel_06-02

so heißt das k-Zykel.

Ben Okay, wir haben gerade einen 99-Zykel erlebt.

III_26_permutationsgruppe_01_05

Transposition

Rike Richtig. Den einfachste Fall eines k-Zykels haben wir für k = 2, also wenn sich zwei Elemente vertauschen:

\pi a_j\;=\;a_i

\pi a_i\;=\;a_j

III_26_permutationsgruppe_02_03

das heißt Transposition. In Matrixschreibweise geht das so:

III_26_formel_07

Ben Sind das nicht ganz unterschiedliche Dinge? Beim k-Zykel rücken alle „Beteiligten“ eins weiter, ihre relative Ordnung bleibt bestehen, bei der Transposition werden zwei Plätze getauscht, ihre Ordnung wird umgekehrt. Hier bei dem Bild war erst das 6. Element vor dem 7. Nach der Transposition ist das 7. Element vor dem 6.?

Rike Ja, das sieht so aus. Aber höre, Ben, es gibt einen Zusammenhang von beiden, Du kannst nämlich jeden k-Zykel als Produkt – also als Nacheinanderausführung von Transpositionen schreiben!

Ben Das glaube ich nicht!

Rike Doch! Dieses Produkt kann ich Dir sogar konstruktiv nennen:

III_26_formel_08b

Ben Warte mal, zuerst tauscht Du die ersten beiden Teilnehmer des Zykels. Das zweite Element geht an die Stelle des ersten und das erste an die Stelle des zweiten. Danach tauschst Du die 1. und 3. Stelle, dann steht das 3. Element wieder hinter dem 2. usw. Ist ja krass!

Flugzeugbeispiel

III_26_permutationsgruppe_03_02
k-Zykel als Nacheinanderausführung von Transpositionen. Die Nummern links geben die Transposition aus der Produktformel oben an.

Kann man eigentlich jede Permutation als Produkt von Transpositionen schreiben?

Rike Ja!

Ben Das ist ja cool. Dann kann man das eigentlich gut für einen Sortieralgorithmus benutzen, man zerlegt jede Sortierung  in seine elementaren Bestandteile, die Transpositionen, das ist überschaubar und gut programmierbar!

Übungsaufgaben

  1. Prüfe die Gruppeneigenschaften für die Permutationsgruppe.
  2. Ist Pn kommutativ, das heißt, da ist

    \pi_1\;\circ\;\pi_2\;=\;\pi_2\;\circ\;\pi_1?

Lösungen

  1. Pn ist eine Gruppe mit dem Einselement Id:

    \mathrm{Id} j\;=\;j,\; \forall j\;=\;1,\; \dots,\; n

    und dem zu einer Permutation \pi mit

    \pi i\;=\;j

    inverser Permutation \pi^{-1} mit

    \pi^{-1} j\;=\;i.

  2. Nein, Pn ist nicht kommutativ, denn für die Transpositionen

    III_26_formel_09_02
    undIII_26_formel_10_02
    ist
    III_26_formel_11

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Wir freuen uns, dass Du einen Kommentar hinterlassen möchtest. Denk bitte daran, dass Du dich durch das Abschicken des Kommentars mit unseren Nutzungsbedingungen einverstanden erklärst.