Größte Ordnung eines Elementes < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:56 Mo 14.05.2007 | | Autor: | Moe007 |
| Aufgabe | | Bestimme für 1 [mm] \le [/mm] n [mm] \le [/mm] 11 die größte Ordnung eines Elementes in der n-ten symmetrischen Gruppe [mm] S_{n} [/mm] |
Hallo,
ich hab ein paar Fragen zu dieser Aufgabe. Muss man hier die Ordnung von jedem Element bestimmen? Oder was heißt genau die größte Ordnung eines Elementes in [mm] S_{n}. [/mm] Mir ist das nicht klar. Die Ordnung eines Elementes ist ja so definiert: [mm] x^{n} [/mm] = e. Ist hier bei der Aufgabe e = 1? Oder was heißt genau die Ordnung eines Elementes in der Permutationsgruppe?
Ich hoffe, es kann mir jemand das näher erläutern.
Ich hab so angefangen: [mm] S_{n} [/mm] ist ja die Permutationsgruppe von {1,...,n}.
n = 1.
Dann ist [mm] S_{1} [/mm] = {1}, ist dann die Ordnung von 1 gleich 0?
n=2.
[mm] S_{2} [/mm] = {1,2}. Hier handelt es sich doch um die Transposition von 1 und 2 oder. Dann hab ich mir gedacht, die Ordnung von 1 ist wieder 0 und die Ordnung von 2 ist 2, weil man 2 mal vertauschenmuss, bis man wieder bei der 1 ist.
Stimmt meine Überlegung so?
Ab n [mm] \ge [/mm] 3 hab ich nun Probleme, weil ich nicht weiß, wie die Elemente vertauscht werden.
Aber vielleicht habe ich auch einen Denkfehler und bin voll auf dem falschen Trip. Ich hoffe, dass mir jemand weiter helfen kann.
Vielen Dank und viele Grüße,
Moe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:43 Di 15.05.2007 | | Autor: | felixf |
Hallo Moe!
> Bestimme für 1 [mm]\le[/mm] n [mm]\le[/mm] 11 die größte Ordnung eines
> Elementes in der n-ten symmetrischen Gruppe [mm]S_{n}[/mm]
> Hallo,
> ich hab ein paar Fragen zu dieser Aufgabe. Muss man hier
> die Ordnung von jedem Element bestimmen? Oder was heißt
> genau die größte Ordnung eines Elementes in [mm]S_{n}.[/mm] Mir ist
> das nicht klar. Die Ordnung eines Elementes ist ja so
> definiert: [mm]x^{n}[/mm] = e. Ist hier bei der Aufgabe e = 1? Oder
$e$ ist hier die Identitaetspermutation, also die, die nichts tut.
> was heißt genau die Ordnung eines Elementes in der
> Permutationsgruppe?
Die Ordnung eines Elementes $g$ ist das kleinste positive $n$ mit [mm] $g^n [/mm] = e$.
Die groesste Ordnung eines Elementes in [mm] $S_n$ [/mm] ist [mm] $\max\{ \mathop{\mathrm{ord}}(g) \mid g \in S_n \}$, [/mm] also die groesste Ordnung eines Elementes aus [mm] $S_n$.
[/mm]
> [...]
>
> Aber vielleicht habe ich auch einen Denkfehler und bin voll
> auf dem falschen Trip. Ich hoffe, dass mir jemand weiter
> helfen kann.
Versuch es lieber so:
- Ein Zykel der Laenge $k$ hat die Ordnung $k$.
- Jede Permutation kann als Produkt von disjunkten Zyklen geschrieben werden.
- Ist eine Permutation das Produkt von disjunkten Zyklen der Laengen [mm] $k_1, \dots, k_\ell$, [/mm] so ist die Ordnung der Permutation gerade [mm] $kgV(k_1, \dots, k_\ell)$.
[/mm]
Versuch das erstmal nachzuvollziehen.
Danach versuch fuer jedes $n [mm] \in \{ 1, 2, \dots, 11 \}$ [/mm] dir zu ueberlegen, in wieviele disjunkte Zyklen mit welchen Laengen du eine Permutation aufteilen musst, um die Ordnung zu maximieren. Damit bekommst du dann fuer jedes $n$ die groesste Ordnung eines Elementes in [mm] $S_n$.
[/mm]
Beispiel $n = 3$:
- Ein Zykel der Laenge 3 hat natuerlich Ordnung 3.
- Wenn du einen Zykel der Laenge 2 hast, muss es einen weiteren Zykel der Laenge 1 geben. Damit ist die Ordnung $kgV(2, 1) = 2$, also kleiner 3.
- Wenn du einen Zykel der Laenge 1 hast, dann hast du entweder einen weiteren der Laenge 2 (hatten wir schon) oder zwei weitere der Laenge 1. Im zweiteren Fall ist $kgV(1, 1, 1) = 1$, also kleiner $3$.
Damit ist $3$ die groesste Ordnung eines Elementes in [mm] $S_3$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:44 Di 15.05.2007 | | Autor: | Moe007 |
Hallo felixf,
vielen Dank für deine Antwort.
> Versuch es lieber so:
>
> - Ein Zykel der Laenge [mm]k[/mm] hat die Ordnung [mm]k[/mm].
> - Jede Permutation kann als Produkt von disjunkten Zyklen
> geschrieben werden.
> - Ist eine Permutation das Produkt von disjunkten Zyklen
> der Laengen [mm]k_1, \dots, k_\ell[/mm], so ist die Ordnung der
> Permutation gerade [mm]kgV(k_1, \dots, k_\ell)[/mm].
>
> Versuch das erstmal nachzuvollziehen.
D.h. doch wenn [mm] \sigma [/mm] meine Permutation ist, und [mm] \gamma_{i} [/mm] ein Zykel, dann ist [mm] \sigma [/mm] = [mm] \produkt_{i=1}^{l} \gamma_{i}, [/mm] wobei [mm] k_{1} [/mm] die Länge von [mm] \gamma_{1},..., k_{l} [/mm] die Länge von [mm] \gamma_{n} [/mm] ist.
Versteh ich das richtig?
>
> Danach versuch fuer jedes [mm]n \in \{ 1, 2, \dots, 11 \}[/mm] dir
> zu ueberlegen, in wieviele disjunkte Zyklen mit welchen
> Laengen du eine Permutation aufteilen musst, um die Ordnung
> zu maximieren. Damit bekommst du dann fuer jedes [mm]n[/mm] die
> groesste Ordnung eines Elementes in [mm]S_n[/mm].
>
> Beispiel [mm]n = 3[/mm]:
> - Ein Zykel der Laenge 3 hat natuerlich
> Ordnung 3.
> - Wenn du einen Zykel der Laenge 2 hast, muss es einen
> weiteren Zykel der Laenge 1 geben. Damit ist die Ordnung
> [mm]kgV(2, 1) = 2[/mm], also kleiner 3.
> - Wenn du einen Zykel der Laenge 1 hast, dann hast du
> entweder einen weiteren der Laenge 2 (hatten wir schon)
> oder zwei weitere der Laenge 1. Im zweiteren Fall ist
> [mm]kgV(1, 1, 1) = 1[/mm], also kleiner [mm]3[/mm].
>
> Damit ist [mm]3[/mm] die groesste Ordnung eines Elementes in [mm]S_3[/mm].
Ich hab versucht jetzt genauso vorzugehen.
Für n = 1 haben wir nur {1} und der Zykel hat die Länge 1, also auch die Ordnung 1. Also ist auch die Ordnung der Permutation = 1.
Stimmt das?
n=2: Wenn man ein Zykel der Länge 2 hat, dann hat er auch ordnung 2.
Wenn man einen Zykel der Länge 1 hat, muss es noch einen weiteren der Länge 1 geben. Damit ist die Ordnung kgV(1,1) = 1 < 2. Also ist 2 die größte Ordnung eines Elementes in [mm] S_{2}.
[/mm]
Stimmt das?
n = 3, hast du gemacht.
n = 4, maximale Ordnung eines Elementes in [mm] S_{4} [/mm] ist 4.
n = 5, maximale Ordnung eines Elementes in [mm] S_{5} [/mm] ist 6, weil wenn ich ein Zykel der Länge 2 habe, dann habe ich einen weiteren Zykel der Länge 3, also kgV(2,3) = 6.
n = 6, maximale Ordnung eines Elementes in [mm] S_{6} [/mm] ist 6.
n = 7, maximale Ordnung eines Elementes in [mm] S_{7} [/mm] ist 12.
n = 8, maximale Ordnung eines Elementes in [mm] S_{8} [/mm] ist 15.
n = 9, maximale Ordnung eines Elementes in [mm] S_{9} [/mm] ist 20.
n = 10, maximale Ordnung eines Elementes in [mm] S_{10} [/mm] ist 21.
n = 11, maximale Ordnung eines Elementes in [mm] S_{11} [/mm] ist 30.
Stimmt das so?
Viele Grüße,
Moe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:56 Di 15.05.2007 | | Autor: | MicMuc |
> n = 10, maximale Ordnung eines Elementes in [mm]S_{10}[/mm] ist 21.
Du betrachtest scheinbar nur Permutationen bestehend aus 2 disjunkte Zyklen.
Hier solltest Du aber auch Permutationen bestehend aus 3 disjunkte Zyklen betrachten!
Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:18 Di 15.05.2007 | | Autor: | Moe007 |
Hallo micmuc,
Ich habe alle Fälle nochmal überprüft, und habe auch die 3-Zykel beachtet:
Bei mir stimmen alle Ergebnisse, so wie ich es jetzt habe, außer bei n=10:
Da habe ich jetzt als maximale Ordnung die Zahl 30. Stimmt das so? Stimmen die andere Ergebnisse oder nicht? (Weil du hast dich nicht dazu geäußert, nur den Fall n=10).
Dann wollte ich noch fragen, warum man hier nur 2- und 3-Zykel betrachten muss, und nicht 4-,5-usw...Zykel? Oder muss man Permutationen nur in 2 oder 3-Zykeln zerlegen?
Danke für deine Hilfe!
Viele Grüße,
Moe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:41 Di 15.05.2007 | | Autor: | MicMuc |
> Hallo micmuc,
> Ich habe alle Fälle nochmal überprüft, und habe auch die
> 3-Zykel beachtet:
> Bei mir stimmen alle Ergebnisse, so wie ich es jetzt habe,
> außer bei n=10:
> Da habe ich jetzt als maximale Ordnung die Zahl 30. Stimmt
> das so?
Das stimmt so.
> Dann wollte ich noch fragen, warum man hier nur 2- und
> 3-Zykel betrachten muss, und nicht 4-,5-usw...Zykel? Oder
> muss man Permutationen nur in 2 oder 3-Zykeln zerlegen?
Die Zerlegung von Permutationen in disjunkte Zyklen ist halt für die Fragestellung sehr sinnvoll, da Du dann über die Zyklenlänge auch die Ordnungen angeben kannst.
Letztendlich musst Du natürlich schon "alle Elemente" durchgehen.
Wenn Du nun aber z.B. für n= 6 alle Permutationen bestehend aus 3 disjunkten Zyklen durchgehst,
(Einschub: wir lassen triviale "Einerzykel" nicht zu, z.B. besteht die Identität aus 6 Einerzyklen:
(1)(2)(3)(4)(5)(6) )
dann muss ja jeder Zykel die Länge zwei besitzen (eine Art Abzählargument, wir haben nur 6 Elemente und die Zykel sind disjunkt)
Eine solche Permutation besitzt dann stets die Ordnung 2 und die ist nicht besonders gross ...
Nachtrag:
=======
Je gößer n ist, desto komplexer wird die Aufgabe.
Grundsätztlich sind hier übrigens Zyklen mit Primzahllänge recht interessant.
Betrachte z.B. den Fall n= 17:
Nun gilt: 2+3+5+7=17, d.h. Du hättest "Platz" für vier "schöne" disjunkte Zyklen ...
Für die Ordnung würde gelten: 2*3*5*7=420 (schon recht gross).
Letztendlich kann man die Aufgabe auch folgendermassen übersetzen:
------------------------------------------------------------------------------------------
Finde natürliche Zahlen [mm] $n_i$ [/mm] deren Summe kleiner oder gleich n ist und deren kGV maximal wird.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:53 Di 15.05.2007 | | Autor: | Moe007 |
Hallo MicMuc,
danke für deine hilfreichen Erklärungen!
Viele Grüße,
Moe
|
|
|
|
