Frage von StormRider00, 36

Kombinatorik: Permutation mit zyklischen Randbedingungen?

Hallo Liebe Community,

ich habe eine Frage aus dem Bereich Kombinatorik. Wie viele Möglichkeiten gibt es n paarweise verschiedene Objekte in einer zyklischen Anordnung (d.h. dass das 1-te und n-te wieder nebeneinander liegen) zu permutieren? Muss ich berücksichtigen, dass die verschiedenen Anordnungen bei einer Rotation wieder in sich selbst übergehen?

Vielen Dank!

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von iokii, 13

Es gibt n! Möglichkeiten, die Dinger anzuordnen, von denen kommen aber alle in n-Facher Ausführung vor, also gibt es n!/n=(n-1)! Möglichkeiten.

Antwort
von Maarduck, 33

Das kommt auf die Aufgabenstellung an. Z.B. bei einem Stuhlkreis in einem Zimmer mit Fenster oder Tür, gehen die verschiedenen Anordnungen ja nicht bei Rotation in sich selbst über (bleiben unterscheidbar), ansonsten schon. Außerdem ist die Frage, ob es bei den Stühlen egal ist, welche Objekte du dort platzierst oder ob es nicht egal ist. Sollen Menschen auf den Stüheln sitzen, so ist die Susanne sicherlich vom Martin individuell unterscheidbar. Sollen Atome in einem Ring platziert werden, so sind z.B. alle C-Atome ununterscheidbar. 

Kommentar von StormRider00 ,

Vielen Dank, 

dann werde ich meine Frage noch etwas präzisieren. Die Objekte sollen paarweise verschieden sein, also alle unterscheidbar. Die Positionen sollen ununterscheidbar sein.

Kommentar von Maarduck ,

Also z.B.

Wie viele Möglichkeiten gibt es 3 N-Atome in einem 12-atomigen Ring zu verteilen, der ansonsten nur aus C-Atomen besteht?

Für das erste Atom 1 Möglichkeit, für das zweite 11 Möglichkeiten, für das dritte 10 Möglichkeiten, geteilt durch 2 wegen der Vertauschungsmöglichkeit der N-Atome.

1 * 11 * 10 / 2 = 55

Kommentar von Maarduck ,

Die Objekte sollen paarweise verschieden sein, also alle unterscheidbar.

Ich glaube da habe ich dich zuvor falsch verstanden. Verteilen wir also Menschen auf einen Kreis in einem runden Zimmer ohne Markierung. 4 Menschen auf 12 Stühle:

1 * 11 * 10 * 9 = 990

Fertig

Kommentar von StormRider00 ,

Nein, ich meine etwas Anderes. Hier mal ein Beispiel:

Du hast einen kreisförmigen Teller in drei identische Kreissektoren aufgeteilt. Jetzt hast du drei verschiedene Farben (rot, grün, gelb) und möchtest diese auf dem Teller verteilen. Dann gibt es folgende Möglichkeiten:

a) (rot,grün,gelb), (gelb,rot,grün), (grün,gelb,rot)

b) (rot,gelb,grün), (grün,rot,gelb), (gelb,grün,rot)

Es gibt aber nicht 3! Möglichkeiten, weil alle Kombinationen aus a) und b) durch zyklisches permutieren ineinander überführbar sind (man dreht den Teller einfach um 120°).

Kommentar von StormRider00 ,

Meine Hypothese ist, dass es (n-1)! Permutationen gibt, aber ich finde leider nicht den richtigen Induktionsbeweis.

Kommentar von Maarduck ,

Dein Beispiel: Für die erste Farbe hast du genau eine Möglichkeit. Für die zweite Farbe zwei, und für die dritte Farbe wieder eine. Es gibt also genau 2 Möglichkeiten. 

Anderes Beispiel: Wir verteilen 4 Farben auf 6 Sektoren. 

1 * 5 * 4 * 3 = 60 Möglichkeiten

Wenn n die Anzahl der Sektoren ist und m die Anzahl der Elemente, dann beträgt die Anzahl der Möglichkeiten

(n-1)! / ( n-m)!

Keine passende Antwort gefunden?

Fragen Sie die Community