Anzahl der Zykel einer Ordnung

21.02.2011, 17:05

Gast11022013

Anzahl der Zykel einer Ordnung

Meine Frage:
(a) Wie kann man bestimmen, wieviele Zykel eines bestimmten Zykeltyps es in der $\begin{eqnarray*} S_n \end{eqnarray*}$ gibt?

(b) Wie kann man bestimmen, wieviele Zykel einer bestimmten Ordnung es in der $\begin{eqnarray*} S_n \end{eqnarray*}$ gibt?

Meine Ideen:
Ich weiß nur eine Formel, mit der man bestimmen kann, wieviele Zykel einer bestimmten Länge t es in der $\begin{eqnarray*} S_n \end{eqnarray*}$ gibt, nämlich:

$\begin{eqnarray*} \frac{n\cdot (n-1)\cdot ...(n-t+1)}{t} \end{eqnarray*}$

Aber zu (a) und (b) habe ich leider keine Ahnung...

21.02.2011, 18:40

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl der Zykel einer Ordnung

Zitat:

Original von Dennis2010
Aber zu (a) und (b) habe ich leider keine Ahnung...

Das gilt auch für mich... Mehr noch: Ich glaube nicht, dass es zu diesen Fragen eine Antwort in dieser Allgemeinheit gibt... Es würde mich daher nicht wundern, wenn du dir diese Fragen - in Unkenntnis ihrer Schwierigkeit - selbst ausgedacht hättest, lasse mich aber auch gerne eines Besseren belehren... Augenzwinkern

21.02.2011, 18:47

Gast11022013

Auf diesen Beitrag antworten »

RE: Anzahl der Zykel einer Ordnung
Diese Fragen stammen von mir, ja.

Achso, das hätte ich dazu schreiben sollen.

Hier ist eine Aufgabe, bei der ich gerade versuche, die Anzahl der Zykel eines Zykeltyps in der $\begin{eqnarray*} S_{15} \end{eqnarray*}$ auszurechnen. Da merke ich gerade, dass es keine Formel geben kann.

Ordnung Zentralisator

Vielleicht kannst Du ja dort weiterhelfen, wenn Du Lust hast.
Sich den letzten Beitrag zu betrachten, ist ausreichend. :-)

26.01.2013, 13:08

BoehserOnkelNico

Auf diesen Beitrag antworten »

Ich weiß, der Thread ist schon alt, aber ich bin gerade über die gleiche Frage in einem Buch (Einführung in die Kombinatorik - Jacobs & Jungnickel) gestolpert. Habe auch einen Ansatz, vielleicht ist die Lösung ja noch interessant oder fehlerhaft, ich wäre auf jeden Fall über Rückmeldung erfreut.
Die Formulierung in dem o.g. Buch:
Seien $\begin{eqnarray*} n \in \mathbb N, b_1\ldots b_k\in\mathbb N \end{eqnarray*}$ , sodass $\begin{eqnarray*} b_1+2b_2+\cdots kb_k=n \end{eqnarray*}$ . Man bestimme die Anzahl derjenigen Permutationen in $\begin{eqnarray*} S_n \end{eqnarray*}$ , die genau $\begin{eqnarray*} b_1 \end{eqnarray*}$ Fixpunkte, $\begin{eqnarray*} b_2 \end{eqnarray*}$ Zweierzykel usw. besitzen.

Mein Ansatz sieht wie folgt aus:
Es gibt insgesamt $\begin{eqnarray*} n! \end{eqnarray*}$ Anordnungen. Von diesen werden nun die ersten $\begin{eqnarray*} b_1 \end{eqnarray*}$ in Einserzykel eingeordnet, die nächsten $\begin{eqnarray*} 2b_2 \end{eqnarray*}$ in Zweierzykel usw.
Gefragt ist also, wieviele der $\begin{eqnarray*} n! \end{eqnarray*}$ Anordnungen dieselbe Zerlegung liefern.
Die ersten $\begin{eqnarray*} b_1 \end{eqnarray*}$ Elemente können alle untereinander permutiert werden, dies liefert den Faktor $\begin{eqnarray*} \frac 1 {b_1!} \end{eqnarray*}$ .
Die nächsten $\begin{eqnarray*} b_2 \end{eqnarray*}$ Elemente können nun nur noch in entsprechenden "Zweiergruppen" untereinandervertauscht werden. Weiterhin können die beiden Elemente, die in einem Zykel sind, untereinander vertauscht werden. Dies liefert also den Faktor $\begin{eqnarray*} \frac 1{b_2!2^{b_2}} \end{eqnarray*}$ .
Betrachtet man nun die nächsten $\begin{eqnarray*} 3b_3 \end{eqnarray*}$ Elemente, können diese wieder in den jeweiligen "Dreiergruppen" vertauscht werden, die Elemente in einem Zykel können zyklisch untereinander vertauscht werden (also pro Zykel $\begin{eqnarray*} 3 \end{eqnarray*}$ Möglichkeiten, diese anzuordnen).
Dies liefert dann den Faktor $\begin{eqnarray*} \frac 1 {b_3!3^{b_3}} \end{eqnarray*}$

Dieses vorgehen lässt sich dann auch auf die Zykel größerer Länge verallgemeinern, so dass ich insgesamt auf folgenden Ausdruck komme:
$\begin{eqnarray*} \frac{n!}{\prod_{i=1}^k b_i\cdot i^{b_i}} \end{eqnarray*}$

27.01.2013, 15:07

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von BoehserOnkelNico
Dieses vorgehen lässt sich dann auch auf die Zykel größerer Länge verallgemeinern, so dass ich insgesamt auf folgenden Ausdruck komme:
$\begin{eqnarray*} \frac{n!}{\prod_{i=1}^k b_i \textcolor{red}{!}\cdot i^{b_i}} \end{eqnarray*}$

Sorry wegen der verspäteten Antwort, aber ich konnte lange einfach nicht glauben, dass du recht hast mit deiner Formel (mit Ausnahme obigen Flüchtigkeitsfehlersl)... Ich muss aber muss nun endgültig eingestehn, dass ich diese einfache Lösung, zumindestens was den Aufgabenteil a) betrifft, glatt übersehen hatte... unglücklich

Neue Frage »

Antworten »

Anzahl der Zykel einer Ordnung

Verwandte Themen