Anzahl der Typen - Permutation

14.02.2013, 18:20

mbbm

Anzahl der Typen - Permutation

Hallo,

ich gehe gerade folgende Aufgabe durch:

Sei $\begin{eqnarray*} \sigma = \tau_1 \ldots \tau_K \in S_n \end{eqnarray*}$ ohne die Identität, wobei $\begin{eqnarray*} \tau_i \end{eqnarray*}$ paarweise disjunkte Zykel der Längen $\begin{eqnarray*} l_i \geq 2 \end{eqnarray*}$ sind. OEdA kann man $\begin{eqnarray*} l_1\geq \ldots \geq l_k \end{eqnarray*}$ annehmen. Man nennt dann $\begin{eqnarray*} (l_1,...l_k) \end{eqnarray*}$ den Typ von $\begin{eqnarray*} \sigma \end{eqnarray*}$ .

Gib an, wieviele Permutationen im Fall n=4 zu den einzelnen Typen gehören.

Lösung:

k=1:
(4)-Anzahl: 6
(3)-8
(2)-6
k=2:
(2)(2)-3

Wie berechnet man diese Anzahl? Der Fall k=1 bedeutet doch, dass ich meine Permutation als einen Zykel darstelle richtig? Das bedeutet doch, dass der Zykel mit vier Elementen diese Form hat (a,b,c,d). Und davon gibt es doch schon 4! Elemente. Warum sind es aber nur 6?

Hoffe mir kann hierbei jemand weiterhelfen.

mfg

14.02.2013, 18:34

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl der Typen - Permutation

Zitat:

Original von mbbm
Wie berechnet man diese Anzahl? Der Fall k=1 bedeutet doch, dass ich meine Permutation als einen Zykel darstelle richtig? Das bedeutet doch, dass der Zykel mit vier Elementen diese Form hat (a,b,c,d). Und davon gibt es doch schon 4! Elemente. Warum sind es aber nur 6?

Weil jeder Zyklus mit seinem kleinsten Element beginnt, d.h., das kann man sich nicht aussuchen, sondern erst die nachfolgenden Elemente...

14.02.2013, 19:44

mbbm

Auf diesen Beitrag antworten »

RE: Anzahl der Typen - Permutation
Ok, das bedeutet also, dass dieser Zykel mit 1 beginnen muss, also habe ich noch 3!=6 Möglichkeiten.

Der Fall (a,b,c)(d) muss somit mit 1 oder 2 beginnen, dann komme ich aber auf 12 Möglichkeiten:

(123),(132),(124),(142),(134),(143) Fixpunkt nicht mitgschrieben=6 Möglichkeiten

und das mal 2, wenn ich mit 2 anfange, gibt 12. verwirrt

14.02.2013, 21:14

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl der Typen - Permutation
Du musst dir das für Dreierzyklen anders überlegen, nämlich so:

Zuerst wählst aus {1,2,3,4} eine 3-elementige Menge aus, dafür gibt es $\begin{eqnarray*} \binom 43 \end{eqnarray*}$ , also 4 Möglichkeiten, dann stellst du das kleinste Element von den dreien an den Anfang des Zyklus und für die restlichen 2 Elemente hast du dann noch 2! Möglichkeiten sie anzuordnen, macht dann insgesamt 8 Möglichkeiten, nämlich:

(123),(132),(124),(142),(134),(143),(234),(243)

Alles klar? Augenzwinkern

14.02.2013, 21:38

mbbm

Auf diesen Beitrag antworten »

RE: Anzahl der Typen - Permutation
Achso ja jetzt ist es klar. Ich habe bei meiner Berechnung vergessen die Zykel, welche mit 2 beginnen und 1 enthalten zu streichen, da diese bereits gezählt wurden.

Ok im Fall mit einem Zweier Zykel wähle ich also eine 2 elementige Teilmenge aus. Das sind $\begin{eqnarray*} \begin{pmatrix} 4\\2 \end{pmatrix} \end{eqnarray*}$ Möglichkeiten. Wenn ich dann wieder das kleinere an den Beginn stelle, gibt es noch eine Möglichkeit für die Anordnung und somit ist die Anzahl 6.

Jetzt noch der fall k=2.

Ich wähle also diesmal zwei 2 elementige Teilmengen aus, das heißt also wieder $\begin{eqnarray*} \begin{pmatrix} 4\\2 \end{pmatrix} \end{eqnarray*}$ Möglichkeiten.

Das gibt folgende 6 Zykel:

(12),(13),(14),(23),(24),(34)

Nun muss ich 6 allerdings halbieren, da bei der Auswahl von (12) automatisch (34) dabei ist und somit haben wir 3 Möglichkeiten.

Stimmt das?

14.02.2013, 23:29

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl der Typen - Permutation
Ja, stimmt so... Freude

15.02.2013, 17:49

mbbm

Auf diesen Beitrag antworten »

RE: Anzahl der Typen - Permutation
Super Danke smile

Neue Frage »

Antworten »

Anzahl der Typen - Permutation

Verwandte Themen