exponent sym. gruppe < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
moin,
Ich bereite grad ein wenig was zur Zykelschreibweise von Permutationen (endlicher Mengen) vor und was man damit alles tolles machen kann.
Unter anderem kann man an der Zykelschreibweise ja ohne Probleme die Ordnung eines Elementes der [mm] $S_n$ [/mm] ablesen, diese ist dann ja einfach das kgV der Zykellängen.
Dann hat sich mir die Frage gestellt, wie es mit dem Exponenten der [mm] $S_n$ [/mm] aussieht, also wie man mit diesem Wissen ggf. die größte auftretende Ordnung berechnen könnte.
Als "Formel" habe ich folgendes:
Es definiere $P(n)$ die Menge aller Partitionen einer natürlichen Zahl $n$.
Damit es hübscher wird, lasse ich 0 als Summanden zu und erhalte:
$P(n) := [mm] \{ x \in \IN_0^n | \summe_{k=1}^n x_k = n \}$
[/mm]
Für $x [mm] \in \IN_0^n$ [/mm] definiere $kgV(x) := [mm] kgV(x_1,x_2,\ldots,x_n)$.
[/mm]
Dann ist [mm] $exp(S_n) [/mm] = [mm] max\{ kgv(x) | x \in P(n) \}$.
[/mm]
Nun bin ich zwar der Meinung das stimmt, aber wenn nicht wäre es nett, wenn ihr mir sagen könntet wo der Fehler liegt.
Was mich aber momentan noch mehr interessiert:
Die obige Formel ist ja nichtmal ansatzweise effizient zu berechnen, deshalb würde ich gerne wissen, ob jemand eine halbwegs schöne Formel kennt oder wenn nicht, in welchem Teilgebiet der Mathematik man sich mit sowas beschäftigt (Gruppentheorie, Zahlentheorie, ggf. Unterbereiche; oder doch ganz wo anders)?
lg und thx schomal
Schadow
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:39 Sa 04.02.2012 | | Autor: | felixf |
Moin Schadow
> Ich bereite grad ein wenig was zur Zykelschreibweise von
> Permutationen (endlicher Mengen) vor und was man damit
> alles tolles machen kann.
> Unter anderem kann man an der Zykelschreibweise ja ohne
> Probleme die Ordnung eines Elementes der [mm]S_n[/mm] ablesen, diese
> ist dann ja einfach das kgV der Zykellängen.
![[ok]](/images/smileys/ok.gif "[ok]")
> Dann hat sich mir die Frage gestellt, wie es mit dem
> Exponenten der [mm]S_n[/mm] aussieht, also wie man mit diesem Wissen
> ggf. die größte auftretende Ordnung berechnen könnte.
>
> Als "Formel" habe ich folgendes:
> Es definiere [mm]P(n)[/mm] die Menge aller Partitionen einer
> natürlichen Zahl [mm]n[/mm].
> Damit es hübscher wird, lasse ich 0 als Summanden zu und
> erhalte:
> [mm]P(n) := \{ x \in \IN_0^n | \summe_{k=1}^n x_k = n \}[/mm]
> Für
> [mm]x \in \IN_0^n[/mm] definiere [mm]kgV(x) := kgV(x_1,x_2,\ldots,x_n)[/mm].
>
> Dann ist [mm]exp(S_n) = max\{ kgv(x) | x \in P(n) \}[/mm].
>
> Nun bin ich zwar der Meinung das stimmt, aber wenn nicht
> wäre es nett, wenn ihr mir sagen könntet wo der Fehler
> liegt.
Wenn du den Exponent als die groesste auftretende Ordnung definierst, dann stimmt das. Normalerweise ist mit dem Exponenten jedoch das kgV aller auftretender Ordnungen gemeint. In dem Fall stimmt es nicht: du muesstest dann das kgV aller $kgV(x), x [mm] \in [/mm] P(n)$ nehmen.
Das waere bereits viel einfacher zu berechnen: das kgV ist gleich [mm] $\prod_p p^{\lfloor \frac{\log n}{\log p} \rfloor}$, [/mm] wobei das Produkt ueber alle Primzahlen geht.
> Was mich aber momentan noch mehr interessiert:
> Die obige Formel ist ja nichtmal ansatzweise effizient zu
> berechnen,
Du musst uebrigens nur die Partitionen $x$ von $n$ anschauen, deren Komponenten [mm] $x_1, \dots, x_k$ [/mm] aus Primzahlpotenzen zu paarweise verschiedenen Primzahlen, aufgefuellt mit Einsen, bestehen. Damit kannst du das Maximum der Ordnungen schon einfacher berechnen.
> deshalb würde ich gerne wissen, ob jemand eine
> halbwegs schöne Formel kennt oder wenn nicht, in welchem
> Teilgebiet der Mathematik man sich mit sowas beschäftigt
> (Gruppentheorie, Zahlentheorie, ggf. Unterbereiche; oder
> doch ganz wo anders)?
Ich wuerde am ehesten auf Kombinatorik tippen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 So 12.02.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
