Permutationen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:49 Mo 10.01.2011 | | Autor: | dennis2 |
| Aufgabe | 1.) Wie viele Zyklen der Länge t gibt es in der [mm] S_n?
[/mm]
2.) Ist die Permutation [mm] \pmat{1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 5 & 8 & 2 & 9 & 1 & 6 & 4 & 3} [/mm] in der alternierenden Gruppe?
3. Beschreiben Sie die Ordnung einer Permutation mithilfe ihres Zykeltyps. |
Hallo, liebe hilfsbereite Forumsbesucher!
Zu dieser Aufgabe benötige ich Eure Hilfe!
Ich schlage mal vor, was ich mir (bisher) gedacht habe:
zu 3.)
Ist hier gemeint:
Die Ordnung einer Permutation ist das kleinste gemeinsame Vielfache der Zyklenlängen der eindeutigen Zyklenzerlegung?
Besteht die Partition einer Permutation z.B. aus einem 2-er und einem 3-er Zyklus, so ist die Ordnung 6=kgV(2,3).
Eine andere Antwort auf die Frage fällt mir jedenfalls nicht ein.
zu 2.)
in Zykelschreibweise: (176)(256384)
Ich weiß, dass die alternierende Gruppe von den 3-er Zyklen erzeugt wird. Hier liegt aber ein 6-er Zyklus vor (den ich nicht weiter zerlegt bekommen habe). Demnach würde ich sagen, dass die genannte Permutation nicht in der alternierenden Gruppe enthalten ist?
zu 1.)
Mir fehlt noch eine Idee, wie man das angehen kann.
Hat jemand hier einen Tipp?
Dankesehr!
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:01 Mo 10.01.2011 | | Autor: | dennis2 |
| Aufgabe | | Ich würde mich sehr freuen, wenn mir jemand helfen könnte, speziell bei Aufgabenteil a) |
Verstehe ich das korrekt, wenn ich jetzt dort zeigen soll, wieviele Zyklen der Länge t=n,n-1,...,1 es gibt?
Ich wüsste nämlich nicht, was das t hier ansonsten bedeuten soll...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:40 Di 11.01.2011 | | Autor: | statler |
Guten Morgen!
> Ich würde mich sehr freuen, wenn mir jemand helfen
> könnte, speziell bei Aufgabenteil a)
> Verstehe ich das korrekt, wenn ich jetzt dort zeigen soll,
> wieviele Zyklen der Länge t=n,n-1,...,1 es gibt?
>
> Ich wüsste nämlich nicht, was das t hier ansonsten
> bedeuten soll...
Das sehe ich auch so. Erkennst du, welchem kombinatorischen Vorgang (Urnenmmodell) das entspricht? Du ziehst t Kugeln aus n Kugeln ohne Zurücklegen und mit Reihenfolge. Es bleibt jetzt noch zu berücksichtigen, daß du denselben Zyklus auf verschiedene Weise hinschreiben kannst, z. B. (123) = (231). Also wird die Anzahl der verschiedenen Zyklen kleiner.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 08:26 Di 11.01.2011 | | Autor: | dennis2 |
Zunächst bestimme ich mal die Konjugationsklassen und ihre Ordnungen:
[mm] \bruch{n!}{\produkt_{m\in [1,n]} m^{u_m}*u_m!}, [/mm] wobei
[mm] n!=|S_n| [/mm]
[mm] u_m=Anzahl [/mm] der m-Zyklen
Also mal anhand eines Beispiels: [mm] S_4
[/mm]
Ich nehme immer einen Repräsentanten für eine Konjugationsklasse und berechne die Ordnung der jeweiligen Konjugationsklasse.
(1 2 3 4), [mm] \bruch{4!}{4^1*1!}=6, [/mm] d.h. es gibt sechs Permutationen diesen Typs
(12), [mm] \bruch{4!}{(2^1*1!)(1^2*2!)}=6, [/mm] d.h. es gibt sechs Permutationen diesen Typs
[mm] (12)(34),\bruch{4!}{2^2*2!}=3, [/mm]
(123).... =8, also 8 Permutationen diesen Typs
und dann noch die Identitat, also noch eine Permutation.
Aber es ist ja nach der Anzahl t der Zyklen gefragt
da würde ich jetzt sagen:
4 1er Zyklen
6 2er Zyklen
8 3er Zyklen
6 4er Zyklen
Also der Typ (12)(34) setzt sich ja aus 2er Zyklen zusammen, deswegen habe ich die jetzt nicht mitgezählt....
Allgemein würde ich sagen:
Für die Zyklen der Länge n und n-1 kann man die obige Formel so verwenden und hat schon die Anzahl der jeweiligen Zykel.
Für die Zykel der Länge ab n-2 wirds schwerer, weil sie ja mehrfach in den verschiedenen Zykeltypen auftauchen. Da würde ich sagen, die Anzahl ist das Maximum (Ich versuchs mal zu erläutern, was ich damit meine):
Also wenn z.B. vom Typ (12)(23) so und so viel existieren und vom Typ (12)(3)(4) so und so viel, dann ist ja noch obiger Formel die Anzahl der Zyklen vom Typ (12)(3)(4) größer und zwar im obigen Beispiel 6. Wohingegen bei (12)(34) ja 3 rauskommt. Und da nun in beiden Zykeltypen Zyklen der Länge 2 vorkommen, würde ich sagen: Man nimmt die größere Zahl, es gibt also 6 Zykeln der Länge 2.
Ich hoffe es versteht jemand, was ich meine!
Stimmt das so?!
[Oder muss man hier irgendwie mit der Bahnformel argumentieren, denn die Konjugationsklassen sind ja Bahnen.]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:33 Di 11.01.2011 | | Autor: | statler |
Hi!
Irgendwie bin ich enttäuscht, daß du auf meinen Vorschlag so gar nicht eingehst :-(
> Aber es ist ja nach der Anzahl t der Zyklen gefragt
>
> da würde ich jetzt sagen:
> 4 1er Zyklen
> 6 2er Zyklen
> 8 3er Zyklen
> 6 4er Zyklen
Bei einem Zyklus der Länge t hast du für die 1. Stelle n Möglichkeiten, für die 2. dann noch n-1 usw. und für die t. schließlich n-t+1, insgesamt also das Produkt daraus. Nun kannst du den Zyklus mit jeder der t Stellen anfangen, also mußt du diese Anzahl noch durch t teilen, um alle voneinander verschiedenen Zyklen zu erhalten.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:38 Di 11.01.2011 | | Autor: | dennis2 |
| Aufgabe | Entschuldige, dass ich darauf nicht eingegangen war.
Dafür jetzt:
Ich möchte das, was Du schreibst, gerne wieder an der [mm] S_4 [/mm] probieren:
So, wie ich Deine Antwort verstehe, müsste man jetzt rechnen:
4er-Zykel: 4!/4=6
3er-Zykel: 4!/3=8
Für die 2er- und 1er-Zykeln kann man doch jetzt aber so nicht rechnen, denn erhielte man:
2-er-Zykeln: 4!/2=12
1er-Zykeln: 4!/1=24
Stattdessen muss man wohl rechnen:
2-er-Zyklen: 4!/4=6
1er-Zykeln: 4!/4!=1 |
Stimmt das so?...
Was war an meinem eigenen Vorschlag verkehrt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:58 Di 11.01.2011 | | Autor: | statler |
> Entschuldige, dass ich darauf nicht eingegangen war.
So ernst war der Anwurf nicht gemeint.
> Dafür jetzt:
>
> Ich möchte das, was Du schreibst, gerne wieder an der [mm]S_4[/mm]
> probieren:
>
> So, wie ich Deine Antwort verstehe, müsste man jetzt
> rechnen:
>
> 4er-Zykel: 4!/4=6
OK
> 3er-Zykel: 4!/3=8
Eigentlich 4*3*2/3 gemäß Formel
> Für die 2er- und 1er-Zykeln kann man doch jetzt aber so
> nicht rechnen, denn erhielte man:
>
> 2-er-Zykeln: 4!/2=12
Jetzt wird dein Gerechne falsch: 4*3/2 = 6
und
> 1er-Zykeln: 4!/1=24
4/1 = 4
> Stattdessen muss man wohl rechnen:
> 2-er-Zyklen: 4!/4=6
> 1er-Zykeln: 4!/4!=1
> Stimmt das so?...
s. o.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:13 Di 11.01.2011 | | Autor: | dennis2 |
> > 2-er-Zykeln: 4!/2=12
> Jetzt wird dein Gerechne falsch: 4*3/2 = 6
> und
> > 1er-Zykeln: 4!/1=24
> 4/1 = 4
Ja, stimmt! Für die erste Position habe ich 4 Möglichkeiten, für die zweite 3 Möglichkeiten, also steht im Zähler natürlich 4*3.
Ich denke, das habe ich verstanden.
Wenn ich die Frage: "Wie viele Zykeln der Länge t gibt es in [mm] S_n?" [/mm] also folgendermaßen beantworte:
Es gibt [mm] \bruch{n*(n-1)*...*(n-t+1)}{t} [/mm] Zykel der Länge t in [mm] S_n, [/mm] denkst Du dann, dass ich die 2 Punkte, die die Aufgabe wert ist, bekäme? Oder muss man noch was erläutern, beweisen, ergänzen...?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:23 Di 11.01.2011 | | Autor: | statler |
Mahlzeit!
> Wenn ich die Frage: "Wie viele Zykeln der Länge t gibt es
> in [mm]S_n?"[/mm] also folgendermaßen beantworte:
>
> Es gibt [mm]\bruch{n*(n-1)*...*(n-t+1)}{t}[/mm] Zykel der Länge t
> in [mm]S_n,[/mm] denkst Du dann, dass ich die 2 Punkte, die die
> Aufgabe wert ist, bekäme? Oder muss man noch was
> erläutern, beweisen, ergänzen...?
In Mathe muß man jede Auss. beweisen. 'Warum?' ist die wichtigste Frage der Mathematik. Oder man fängt die Antwort mit 'Offenbar ist ... ' an.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:25 Di 11.01.2011 | | Autor: | dennis2 |
| Aufgabe | | Beweis per Induktion? |
Wäre jetzt so meine erste Idee.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:37 Do 13.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:18 Mo 10.01.2011 | | Autor: | Lippel |
Nabend,
> 1.) Wie viele Zyklen der Länge t gibt es in der [mm]S_n?[/mm]
> 2.) Ist die Permutation [mm]\pmat{1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 5 & 8 & 2 & 9 & 1 & 6 & 4 & 3}[/mm]
> in der alternierenden Gruppe?
> 3. Beschreiben Sie die Ordnung einer Permutation mithilfe
> ihres Zykeltyps.
> Hallo, liebe hilfsbereite Forumsbesucher!
>
> Zu dieser Aufgabe benötige ich Eure Hilfe!
>
> Ich schlage mal vor, was ich mir (bisher) gedacht habe:
>
> zu 3.)
>
> Ist hier gemeint:
> Die Ordnung einer Permutation ist das kleinste gemeinsame
> Vielfache der Zyklenlängen der eindeutigen
> Zyklenzerlegung?
>
> Besteht die Partition einer Permutation z.B. aus einem 2-er
> und einem 3-er Zyklus, so ist die Ordnung 6=kgV(2,3).
>
> Eine andere Antwort auf die Frage fällt mir jedenfalls
> nicht ein.
Stimmt auch, musst es nur sauber begründen.
> zu 2.)
>
> in Zykelschreibweise: (176)(256384)
>
> Ich weiß, dass die alternierende Gruppe von den 3-er
> Zyklen erzeugt wird. Hier liegt aber ein 6-er Zyklus vor
> (den ich nicht weiter zerlegt bekommen habe). Demnach
> würde ich sagen, dass die genannte Permutation nicht in
> der alternierenden Gruppe enthalten ist?
Ich denke es ist schwierig den Zykel in 3-er Zykel zu zerlegen. Aber es gibt ja noch andere Kriterien. Zähle die Anzahle der Fehlstände, oder arbeite mit dem Signunmshomomorphismus. Ein Zykel ist gerade, wenn die Anzahl der Fehlstände gerade ist bzw. das Signum des Zykels 1 ist.
> zu 1.)
>
> Mir fehlt noch eine Idee, wie man das angehen kann.
>
> Hat jemand hier einen Tipp?
Wir wollen beispielsweise die Anzahl der 2-Zykel in der [mm] $S_3$. [/mm] Es gibt [mm] $\binom{3}{2}=3$ [/mm] Möglichkeiten, zwei verschiedene Elemente aus dreien zu wählen. Das ist aber noch ein einfacher Fall, betrachten wir nämlich die Anzahl der 3-Zykel in der [mm] $S_4$, [/mm] muss man noch beachten, dass die Reihenfolge der Elemente Im Zykel eine Rolle spielt. Dieses Problem hat man natürlich bei 2-Zykeln nicht. Hast du eine Idee, wie man das einbeziehen kann?
LG Lippel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:30 Di 11.01.2011 | | Autor: | dennis2 |
Meine Idee hierzu habe ich als Frage formuliert (s.oben).
|
|
|
|
