Permutationen der Länge n die einen bestimmten Zyklus enthalten

Neue Frage »

Garnier Auf diesen Beitrag antworten »
Permutationen der Länge n die einen bestimmten Zyklus enthalten
Meine Frage:
n>= 3
Bestimmen Sie die Anzahl der Permutationen der Länge n,
a.) die einen n-Zyklus enthalten.
b.) die einen (n-1)-Zyklus enthalten.
c.) die einen (n-2)-Zyklus enthalten.
d.) die fixpunktfrei sind und weder einen n-Zyklus, noch einen (n-1)-Zyklus, noch einen (n-2)-Zyklus enthalten.
e.) die einen (n-k)-Zyklus enthalten mit n>= 2k+1

Meine Ideen:
Meine Ergebnisse sind:
a.) 1
b.) (n über 2)
c.) 1/24 * n*(n-1)*(n-2)*(3n-1)
d.) ist meine Überlegung das ich fixpunktfreie Permutation ausrechne und n-Zyklus, (n-1)-Zyklus und (n-2)-Zyklus davon abziehe, dies ist aber sicher nicht richtig oder?
e.) ist meine Überlegeung 1/(2^k*k!) * n *(n-1)*(n-2)...*(n-k+1) aber ich bin mir nicht sicher ob ich da richtig liege?
Gast11022013 Auf diesen Beitrag antworten »

Hallo, ich habe eine kleine Rückfrage:

Was genau meinst Du mit "Länge einer Permutation"?
Garnier Auf diesen Beitrag antworten »

zum Beispiel: Permutation:
(1 2 3 4 5 6 7 8 9 10 11 12)
(5 4 2 1 6 3 9 7 8 12 10 11)

hier wäre die Länge n = 12
Gast11022013 Auf diesen Beitrag antworten »

Ist das wirklich mit Länge der Permutation gemeint?

Würde man in Deinem Beispiel nicht eher sagen: Es liegt ein Zykel der Länge 12 vor?



Ist die Länge einer Permutation nicht vielemehr die kleinstmögliche Anzahl an Transpositionen, mit denen man die Permutation darstellen kann?

(So hätte ich mir den Begriff jetzt gedacht.)
Mystic Auf diesen Beitrag antworten »

@Dennis2010

Tu den armen Fragesteller nicht noch mehr verwirren... geschockt

Natürlich ist n die Mächtigkeit der Menge {1,2,....,n}, auf der die Permutation "stattfindet", alles andere macht hier schlicht keinen Sinn...
Gast11022013 Auf diesen Beitrag antworten »

Okay, also verwirrten möchte ich niemanden, ich wollte nur den Begriff geklärt haben.

Mit der Länge einer Permutation ist also die Mächtigkeit der Menge gemeint, auf der man die Permutationen betrachtet?


Also etwa und dann möchte man wissen, wie viele Permutationen davon z.B. einen 3-er Zykel haben?


Dann stimmt die Antwort des Fragestellers (er sagt: 1) nicht.


Ich komme auf 2.
 
 
Mystic Auf diesen Beitrag antworten »

Ja, seine Anwort zu a) stimmt nicht... Allgemeiner kann man in einem Zyklus der Länge n o.B.d.A. annehmen, dass er mit 1 beginnt, während die restlichen n-1 Elemente dann beliebig angeordnet sein können...
HAL 9000 Auf diesen Beitrag antworten »

Da es hier nicht so richtig weitergeht...

Abgesehen mal von der "zusammengesetzen" Problemstellung d) läuft doch alles auf Frage e) hinaus. Und dort lautet die Antwort



mit

(1) Anzahl der Auswahlmöglichkeiten der Positionen, die nicht im -Zyklus enthalten sein sollen
(2) Permutationsmöglichkeiten dieser Elemente aus (1)
(3) Anzahl der möglichen -Zyklen auf den nunmehr feststehenden Restpositionen.


Mit geeignet gewählten hat man dann auch a),b), und im wesentlichen auch c) im Sack.
LuciaSera Auf diesen Beitrag antworten »

Ich weiß dieser Thread ist schon älter, aber vielleicht bekomme ich ja doch eine Antwort smile

Ich habe nämlich ebenfalls die Aufgabe bekommen, welche ident zur Aufgabe a) hier ist.

Ist die Antwort für a) (n-1)! Permutationen?

Lg
HAL 9000 Auf diesen Beitrag antworten »

Ja, das ist der Fall in der von mir oben (vor fünf Jahren Augenzwinkern ) erläuterten Formel.
LuciaSera Auf diesen Beitrag antworten »

Wenn ich jetzt aber sage, ich habe nur n!/n, weil ich nur den Fall für k=0 betrachte, wie könnte man das dann am besten beweisen?

Kann ich einfach mit Induktion zeigen, dass n!/n = (n-1)! ist? Oder ist das zu wenig?

Lg
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von LuciaSera
Kann ich einfach mit Induktion zeigen, dass n!/n = (n-1)! ist?

Da muss ich ein wenig schmunzeln: ist einfaches Kürzen.

Aber ich gebe dir insoweit recht, dass meine obige allgemeinere Erklärung für den Fall allein etwas übertrieben ist:

Dort haben wir nur einen Zyklus der Länge , der demnach alle Elemente enthalten muss. Wir betrachten irgendein beliebiges, aber festgewähltes Element und setzen dies dann o.B.d.A. an die erste Stelle der Zykelschreibweise, und die anderen Elemente können wir dahinter beliebig platzieren, also auf verschiedene Weisen - und das ist dann auch die gesuchte Anzahl zyklischer Permutationen, fertig. Augenzwinkern
LuciaSera Auf diesen Beitrag antworten »

Jaa natürlich! Das ist mir klar. Ich dachte nur, dass ich es so zeigen könnte, dass wenn es für n gilt es auch für n+1 gelten muss, und somit immer gilt...
Das ist nach meiner Auffassung ja der Sinn der einer Induktion, oder liege ich da falsch?

So, nun habe ich eine kleiner Verständnisfrage:

Nehmen wir an ich habe:



Sprich der obige Wert wird immer auf den darunterstehenden abgebildet. Habe ich dann nicht insgesamt 6 verschiedene Möglichkeiten?

Also:








Oder fallen die Fälle, wo ich 'nur' die Reihenfolge vertausche, aber immer noch auf die gleichen Elemente abbilde weg?

Und eine weitere Frage die sich mir gestellt hat, warum ich dann durch n dividiere (in meinem Fall nun - allgemein ja durch n-k)
HAL 9000 Auf diesen Beitrag antworten »

Du hast beide 3-zyklischen Permutationen jeweils dreimal aufgeschrieben:

a) , und sind jeweils dieselbe Permutation, in Zykelschreibweise .

b) , und sind ebenfalls dieselbe Permutation, diesmal in Zykelschreibweise .
LuciaSera Auf diesen Beitrag antworten »

Aaah okay! Super danke! Dann habe ichs jetzt verstanden Freude smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »