Wie errechnet man hohe Potenzen von Permutationen?

Hi, wie errechnet man eigentich höhere Potenzen von Permutationen aus, die man "von hand" nur mühselig ausrechnen könnte?

z.B.:

LG:)

Answer 1

[Willibergi]

Die Intuition ist doch, dass eine Permutation Elemente durchmischt. Du fragst dich jetzt, wie die Elemente nachher aussehen, wenn du sie 73 Mal genau auf diese Weise durchgemischt hast. Dafür zerlegen wir die Permutation in Zyklen:

$\pi=\left(1\ 2\ 4\right)\left(3\right)$

Zuerst der einfache Teil: Was passiert mit der 3? Offensichtlich gar nichts, denn bei jedem neuen Mischen bleibt sie auf ihrem Platz. Interessant bleibt der 3-Zykel. Du scheinst den Begriff der Ordnung noch nicht zu kennen, also behelfen wir uns halt anders (wir werden am Ende genau bei der Ordnung ankommen). Gehen wir die Permutation doch einfach mal für die ersten Schritte durch. Die (3) werde ich im Folgenden ignorieren, aber wie wir uns ja schon überlegt haben, ändert sie eh nichts.

Was passiert, wenn wir

$\pi^2=\left(1\ 2\ 4\right)\left(1\ 2\ 4\right)$

betrachten? Das ist nichts anderes als zweimaliges Durchmischen. Das erste Mal Durchmischen - in Abbildungsschreibweise:

$1\mapsto2,\ 2\mapsto4,\ 4\mapsto1$

Die 1 geht auf die 2, die 2 auf die 4 und die 4 auf die 1. Jetzt machen wir das ganze noch ein zweites Mal,

$1\mapsto2,\ 2\mapsto4,\ 4\mapsto1$

- ja, das ist genau dasselbe (nur dass die 1 beim zweiten Mal Mischen eben nicht mehr die ursprüngliche 1, sondern die jetzt die 2 ist - wird gleich klar). Wir überlegen uns, was im Gesamtes passiert ist. Wo ist die 1 jetzt?

Im ersten Schritt wurde die 1 auf die 2 abgebildet, im zweiten Schritt die 2 auf die 4. Insgesamt wurde also die 1 auf die 4 abgebildet (in "permutation-ish" heißt das, die 1 hat den Platz der 4 angenommen). Genauso können wir es uns mit den anderen Zahlen überlegen - 2 auf 4 auf 1 und 4 auf 1 auf 2. Insgesamt ist also passiert:

$1\mapsto4,\ 2\mapsto1,\ 4\mapsto2$

Jetzt kommt der Knackpunkt: Wenn wir den Zykel jetzt nochmal dranmultiplizieren (d.h. aus π² wird π³), landen wir wieder beim ursprünglichen Zykel. Machen wir es einfach mal (die Abbildungsvorschrift über diesem Absatz ist, was wir nach dem Quadrieren haben): Nochmal Dranmultiplizieren ergibt, die 4 geht auf die 1, die 1 auf die 2 und die 2 auf die 4. Also insgesamt:

$1\mapsto4\mapsto1,\ 2\mapsto1\mapsto2,\ 4\mapsto2\mapsto4$

Wir haben also dreimal "gezykelt" und sind bei der Identität gelandet (d.h. dreimal "zykeln" ändert nichts an der Anordnung der Permutation, die 1 steht an Stelle der 1, die 2 an Stelle der 2, usw.). Insgesamt nochmal, was in den drei Durchgängen passiert ist:

$1\mapsto2\mapsto4\mapsto1$ $2\mapsto4\mapsto1\mapsto2$ $4\mapsto1\mapsto2\mapsto4$

Daran kann man auch ganz schön sehen, warum genau sich nichts geändert hat.

Wenn aber doch einfach drei solche gleichen 3-Zykel zusammen wieder alles beim Alten lassen, könnten wir doch - und das ist der Trick - die 73 Zykel, die du hier zusammenmultiplizieren willst, soweit möglich in Dreiergruppen unterteilen und dann alle vollständigen Dreierguppen rausstreichen? Denn zusammen ändern sie ja nichts. Mit anderen Worten, wenn - wie wir gerade gesehen haben -

$\left(1\ 2\ 4\right)^3=\left(1\right)\left(2\right)\left(4\right)=\text{id}\$

gilt, können wir uns Dreierpotenzen der Zykel eigentlich schenken. Gesagt, getan,

$\pi^{73}=\left(1\ 2\ 4\right)^{73}=\left(1\ 2\ 4\right)^{72}\left(1\ 2\ 4\right)^1=\left(\left(1\ 2\ 4\right)^3\right)^{24}\left(1\ 2\ 4\right)=\left(1\ 2\ 4\right)$

und der Zykel mit dem Exponenten 1 bleibt übrig. Ist aber auch klar, denn wenn wir 24 Mal identisch permutieren (d.h. wir schieben insgesamt die 1 auf die 1, die 2 auf die 2, etc.), können wir auch einfach 24 Mal gar nichts machen. Übrig bleibt ein einzelner Zykel,

$\pi^{73}=\left(1\ 2\ 4\right)^{73}=\left(1\ 2\ 4\right)$

und wir sind fertig. Das heißt also, ob wir jetzt 73 Mal auf diese Weise rumzykeln oder nur einmal, macht keinen Unterschied. Denn wir wissen, wenn wir dreimal rumzykeln, kommen wir zur Identität, d.h. auch nach 72 Mal rumzykeln sind wir bei der Identität und das einzige, was jetzt noch etwas ändert, ist der einzelne Zykel dahinter. Und der bleibt übrig.

Und genau das ist die Ordnung einer Permutation: Nämlich die (kleinste) natürliche Zahl k, sodass k Mal permutieren einfach die Identität ergibt. Hier ist das genau die 3 (beachte, dass ein Zykel auch eine Permutation ist). Zerlegen wir eine Permutation in disjunkte Zykel, ist die Ordnung der gesamten Permutation das kleinste gemeinsame Vielfache der Ordnungen der einzelnen Zyklen (überlege dir mal, warum das so sein muss).

Mit dem Begriff der Ordnung ginge die Aufgabe ganz schnell. Wir bestimmen erst die Ordnung der Permutation, zerlegen dazu in zwei disjunkte Zykel (das haben wir oben sogar gemacht), sehen, dass die Ordnung das kgV von 3 und 1, also 3 ist und erhalten dann einfach

$\pi^{73}=\left(\pi^3\right)^{24}\pi=1^{24}\cdot\pi=\pi$

und sind fertig. Im Prinzip haben wir das auch genau so gemacht - nur eben ohne den Begriff der Ordnung und ein bisschen langsamer. Aber wir kommen auf's selbe Ergebnis.

LG

Comments

[Jathe677]

Gute Antwort.

Answer 2

[PhotonX]

Tipp: Schreibe die Permutation in Zykelschreibweise und bestimme ihre Ordnung. Bringt dich das auf Ideen?

Woher ich das weiß: Studium / Ausbildung – Masterabschluss Theoretische Physik

Comments

[Qualle12]

Hi, danke für die Antwort. ich kannte diese Schreibweise bisher noch nicht, aber würde dass dann so funktioneren, dass ich (124)^73(3)^73=... berechnen müsste?

Dann würde ja die drei so bleiben, aber könntest du mir vielleicht sagen, was ich mit den (124) machen muss?

[PhotonX]

@Qualle12

Sagt dir denn der Begriff "Ordnung eines Elements" etwas?

[Qualle12]

@PhotonX

Nein, dass sagt mir leider noch nichts. Ich dachte eigentlich, die Aufgabe wäre schnell erledigt, aber ich habe anscheinend noch nicht genug Wissen, um die Aufgabe erledigen zu können. Ich versuche erst mal die Grundlagen zu permutationen besser zu verstehen. Trotzdem vielen dank für deine Hilfe:)