infostudium.de

von **philipp** » 21.02.07 14:50

Ja eigentlich schon. Sonst wiederholt sich irgendwas zu schnell oder nicht oft genug.
Also es muessen immer die gleichen Anzahlen zu jeder Zykelnlaenge da sein.

von **p0llux** » 21.02.07 14:55

padde hat geschrieben:Nochmal zu der Aufgabe am Anfang zurück:

Kann man dementsprechend davon ausgehen, dass die gesuchten Permutationen nur dann existieren, wenn die beiden gegebenen Permutationen von den Zyklen her "zueinander passen"?

padde

Genau, die Permutationen sind genau dann konjugierbar, wenn sie die gleichen Zykeltypen haben.

von **bugs** » 21.02.07 23:34

noch eine aufgabe:

Für alle Permutationen auf 6 Elementen $\pi$ existiert eine Permutation $\sigma$ mit $\sigma^{-1} \pi \sigma = \pi^{11}$ ( $\pi$ hängt von $\sigma$ ab!)

das stimmt laut MC-Lösung, aber wie begründet man sowas

von **philipp** » 21.02.07 23:39

Wie kann es fuer jedes $\pi$ ein $\sigma$ geben und gleichzeitig $\pi$ von $\sigma$ abhaengen?
Es muesste $\sigma$ von $\pi$ abhaengen.
Ja und dann ginge es, weil dann kannst du ja wie oben bereits besprochen, dir dein sigma so waehlen, dass es genau die selben zykel-laengen und anzahlen hat, wie $\pi$ ...

von kb » 22.02.07 00:08

das ist nicht ganz korrekt. nicht $\sigma$ muss die gleichen zykellängen haben, sondern $\pi^{11}$ .
Das ist aber auch gegeben, denn man bedenke folgende Möglichkeiten:
Ordnung Pi = 6. Dann ist $\pi^{11}=\pi^{-1}$
Ordnung Pi = 5. Dann ist $\pi^{11}=\pi$
Ordnung Pi = 4. Dann ist $\pi^{11}=\pi^{-1}$
Ordnung Pi = 3. Dann ist $\pi^{11}=\pi^{-1}$
Ordnung Pi = 2. Dann ist $\pi^{11}=\pi$
Ordnung Pi = 1. Dann ist $\pi^{11}=id$
Also hat $\pi^{11}$ immer die gleiche Zykellängen wie $\pi$

von **philipp** » 22.02.07 00:45

kb hat geschrieben:das ist nicht ganz korrekt. nicht $\sigma$ muss die gleichen zykellängen haben, sondern $\pi^{11}$

Natuerlich muss $\sigma$ die gleiche Zykellaenge und -anzahl haben wie $\pi$ .
Und das $\pi^{n}$ die gleiche hat wie $\pi$ ist klar. Da braucht es auch kein Durchtesten. Das ist fuer alle Permutationen und $n \neq 0$ so. Daran kannst du ja durch hintereinanderausführung von sich selbst nix aendern...

von kb » 22.02.07 01:08

nein, eben nicht =]

Gegeben sind $\pi$ und $\pi^{11}$ , und $\sigma$ ist gesucht. Und die gegebenen Permutationen müssen gleiche Zykellängen haben, nicht die gesuchte.
Schon auf Seite1 dieses Threads siehst du, dass das Gesuchte in dem gerechneten Beispiel NICHT die gleiche Zykellängen hat.

Und um "Klar"heit zu schaffen:
$\pi = (1, 3, 5, 4)(2, 6) \\<br />\pi^2 = (1,5)(2)(3,4)(6)$
nix gleiche Zykellängen ;]

--edit--
und man kann sich das folgendermaßen für $\pi^n$ überlegen:
Sei i die Länge eines Zykels in $\pi$ . Wenn n|i , entstehen n neue Zyklen der Länge (i/n)

von **philipp** » 22.02.07 01:20

Verdammt du hast recht ^^
Ok und weil 11 ne Primzahl ist, stimmt es in dem Fall.

Aber trotzdem muss ich doch ein $\sigma$ suchen, dass dasselbe Zykelprofil hat um die Bed. zu erfuellen.

von kb » 22.02.07 01:21

Ne, muss nicht. Du "suchst" ja auch nicht, sondern berechnest quasi. Siehe Seite1 in diesem Thread, da wird ein Beispiel berechnet =]

--edit--
"Zykelprofil"...endlich n passendes Wort ^^

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[Diskrete] Online-Übung 5, Aufgabe 3/4