Kreispermutation

Sitzordnungen am runden Tisch vergleichen

Wenn an einem runden Tisch jede Person einen Platz im Uhrzeigersinn weiterrückt, bleiben die Sitznachbarn gleich. Eine $Kreispermutation$ zählt daher $jede relative Sitzreihenfolge einmal$ . Drehungen derselben Reihenfolge gehören zur gleichen Anordnung.

Das unterscheidet sie von einer linearen Permutation. In einer Reihe sind der erste und der letzte Platz eindeutig. Im Kreis gibt es keinen ausgezeichneten Startpunkt.

Jedes Objekt kann daher als Bezugspunkt dienen. Lineare Reihenfolgen, die sich nur durch eine Drehung unterscheiden, beschreiben dieselbe Anordnung im Kreis.

Formel der Kreispermutation

Für $n$ verschiedene Objekte gilt:

P_n = (n-1)!

Dabei gilt:

$P_n$ = Anzahl der Kreispermutationen von $n$ Objekten
$n$ = Anzahl der anzuordnenden Objekte
$(n-1)!$ = Fakultät von $(n-1)$

Warum ist die Formel $(n-1)!$ ?

Eine gemeinsame Drehung aller Objekte erzeugt keine neue Anordnung. Das lässt sich an einem runden Tisch leicht erkennen.

Angenommen, $3$ Kinder, $A$ , $B$ und $C$ , sitzen um einen runden Tisch. Die Reihenfolgen $ABC$ , $BCA$ und $CAB$ sind $dieselbe Anordnung$ , denn sie gehen durch Drehung ineinander über und ihre relativen Positionen bleiben gleich.

Die Tabelle gruppiert alle sechs linearen Reihenfolgen. Lies jede Reihenfolge im Uhrzeigersinn. $Eine Drehung bleibt in derselben Zeile$ , eine Spiegelung wechselt die Zeile.

Kreisanordnung	Gleichwertige lineare Reihenfolgen
1	ABC, BCA, CAB
2	ACB, CBA, BAC

So entsteht die Formel:

Fixiere ein Objekt als $Bezugspunkt$ , zum Beispiel Kind A.
Ordne alle übrigen Objekte relativ zu diesem Bezugspunkt an.
Es bleiben $n-1$ Objekte zum Anordnen.
Dafür gibt es $(n-1)!$ Möglichkeiten.

Für $3$ Kinder ergibt sich $P_3 = (3-1)! = 2! = 2 \times 1 = 2 \text{ Anordnungen}$ .

Die Formel $(n-1)!$ fasst gedrehte Anordnungen zusammen, zählt Spiegelbilder aber weiterhin getrennt. Das passt zu Personen, die zur Tischmitte schauen, denn eine gespiegelte Reihenfolge vertauscht die linken und rechten Nachbarn. Ein Armband lässt sich dagegen umdrehen. Bei $n\geq3$ verschiedenen Perlen bildet jede Kreisreihenfolge mit einem anderen Spiegelbild ein Paar. Daher bleiben $\frac{(n-1)!}{2}$ Anordnungen.

Kreisförmige Anordnungen zählen

Dieselbe Formel zählt $kreisförmige Sitzordnungen$ und andere Formationen um einen Mittelpunkt. Halte eine Person als Bezugspunkt fest und zähle die Reihenfolge der übrigen Personen relativ zu ihr. Bei festen Paaren werden stattdessen die Paare als Einheiten angeordnet.

Sitzordnung am runden Tisch

Fünf Lernende sitzen für eine Diskussion $an einem runden Tisch$ . Die Anzahl der Sitzordnungen beträgt:

\begin{aligned} P_5 &= (5-1)! \\ &= 4! \\ &= 4 \times 3 \times 2 \times 1 \\ &= 24 \text{ Anordnungen} \end{aligned}

Ein Spiel im Kreis

Acht Kinder stellen sich für ein Spiel $im Kreis$ auf. Die Anzahl der verschiedenen Formationen ist:

\begin{aligned} P_8 &= (8-1)! \\ &= 7! \\ &= 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\ &= 5\,040 \text{ Anordnungen} \end{aligned}

Paare auf benachbarten Plätzen

Bei $Zusatzbedingungen$ , etwa wenn bestimmte Objekte nebeneinanderliegen müssen, hilft die $Blockmethode$ :

Beispiel: $4$ Ehepaare sitzen im Kreis, wobei die beiden Personen jedes Paares nebeneinandersitzen müssen.

$Lösungsstrategie$ :

$Fasse$ jedes Paar zu einem Block zusammen: $4 \text{ Blöcke}$ .
$Ordne die Blöcke$ im Kreis an: $(4-1)! = 3! = 6 \text{ Anordnungen}$ .
$Vertausche die Plätze$ innerhalb jedes Paares: $2! \text{ Möglichkeiten}$ pro Paar.
$Multipliziere$ : $3! \times (2!)^4 = 6 \times 2^4 = 6 \times 16 = 96 \text{ Anordnungen}$ .

Übungsaufgaben

Die vier Aufgaben vergleichen einen einfachen Kreis, ein Armband mit $gleichwertigen Spiegelbildern$ , Paare mit benachbarten Plätzen und zwei Personen ohne benachbarte Plätze. Wähle vor dem Rechnen die passende Formel.

Es gibt $6$ Freunde, die am Lagerfeuer sitzen. Auf wie viele Arten können sie sitzen?
Aus $8$ Perlen in verschiedenen Farben wird ein Armband gefertigt. Wenn Drehungen und umgedrehte Spiegelbilder als dasselbe Armband gelten, wie viele Anordnungen sind dann möglich?
$5$ Ehepaare sitzen an einem runden Tisch. Die beiden Personen jedes Paares sollen nebeneinandersitzen. Wie viele Sitzordnungen sind möglich?
$7$ Lernende stellen sich im Kreis auf. Zwei bestimmte Personen dürfen nicht nebeneinanderstehen. Wie viele Anordnungen sind möglich?

Lösungen

$Aufgabe 1$

120 \text{ Wege}

Rechenweg:

Gegeben: $n = 6 \text{ Personen}$ Formel der Kreispermutation: $P_n = (n-1)!$

P_6 = (6-1)! = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120

Die $6 \text{ Personen}$ können also in $120$ verschiedenen Sitzordnungen am Lagerfeuer sitzen.

$Aufgabe 2$

2\,520 \text{ Wege}

Rechenweg:

Zunächst zählen gedrehte Anordnungen als gleich: $P_8 = (8-1)! = 7!$

7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5\,040

Durch Umdrehen des Armbands wird jede Reihenfolge im Uhrzeigersinn mit ihrem Spiegelbild gegen den Uhrzeigersinn identisch. Da alle Perlen verschieden sind, bilden diese Anordnungen Paare. Deshalb teilen wir durch $2$ .

\frac{5\,040}{2} = 2\,520

Es gibt $2\,520$ verschiedene Armbänder.

$Aufgabe 3$

768 \text{ Wege}

Rechenweg:

Gegeben: $5$ Ehepaare, also $10 \text{ Personen}$ . Jedes Paar soll zusammensitzen. $Blockmethode$ : Jedes Paar bildet einen Block: $5 \text{ Blöcke}$ .

Kreispermutation der $5 \text{ Blöcke}$ : $(5-1)! = 4! = 4 \times 3 \times 2 \times 1 = 24$ . Innerhalb jedes Paares sind $2! = 2 \text{ Anordnungen}$ möglich.

Gesamt: $24 \times 2^5 = 24 \times 32 = 768$

Damit erfüllen $768$ Sitzordnungen die Bedingung.

$Aufgabe 4$

480 \text{ Wege}

Rechenweg mit der $Komplementmethode$ :

Ohne Einschränkung gibt es $(7-1)! = 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$ Anordnungen. Für die unerwünschten Fälle fassen wir die $2 \text{ Lernenden}$ zu einem Block zusammen.

Damit liegen $6$ Blöcke im Kreis. Sie lassen sich auf $(6-1)! = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ Arten anordnen. Die $2 \text{ Lernenden}$ im Block können ihre Plätze tauschen. Das ergibt $2! = 2$ innere Anordnungen.

Gesamtzahl benachbarter Anordnungen: $120 \times 2 = 240$ $Gesuchte Anordnungen$ : $720 - 240 = 480$

Somit gibt es $480 \text{ Anordnungen}$ , bei denen die beiden Lernenden nicht nebeneinanderstehen.

Sitzordnungen am runden Tisch vergleichen

Das unterscheidet sie von einer linearen Permutation. In einer Reihe sind der erste und der letzte Platz eindeutig. Im Kreis gibt es keinen ausgezeichneten Startpunkt.

Jedes Objekt kann daher als Bezugspunkt dienen. Lineare Reihenfolgen, die sich nur durch eine Drehung unterscheiden, beschreiben dieselbe Anordnung im Kreis.

Formel der Kreispermutation

Für $n$ verschiedene Objekte gilt:

P_n = (n-1)!

Dabei gilt:

$P_n$ = Anzahl der Kreispermutationen von $n$ Objekten
$n$ = Anzahl der anzuordnenden Objekte
$(n-1)!$ = Fakultät von $(n-1)$

Warum ist die Formel $(n-1)!$ ?

Eine gemeinsame Drehung aller Objekte erzeugt keine neue Anordnung. Das lässt sich an einem runden Tisch leicht erkennen.

Die Tabelle gruppiert alle sechs linearen Reihenfolgen. Lies jede Reihenfolge im Uhrzeigersinn. $Eine Drehung bleibt in derselben Zeile$ , eine Spiegelung wechselt die Zeile.

Kreisanordnung	Gleichwertige lineare Reihenfolgen
1	ABC, BCA, CAB
2	ACB, CBA, BAC

So entsteht die Formel:

Fixiere ein Objekt als $Bezugspunkt$ , zum Beispiel Kind A.
Ordne alle übrigen Objekte relativ zu diesem Bezugspunkt an.
Es bleiben $n-1$ Objekte zum Anordnen.
Dafür gibt es $(n-1)!$ Möglichkeiten.

Für $3$ Kinder ergibt sich $P_3 = (3-1)! = 2! = 2 \times 1 = 2 \text{ Anordnungen}$ .

Kreisförmige Anordnungen zählen

Sitzordnung am runden Tisch

Fünf Lernende sitzen für eine Diskussion $an einem runden Tisch$ . Die Anzahl der Sitzordnungen beträgt:

\begin{aligned} P_5 &= (5-1)! \\ &= 4! \\ &= 4 \times 3 \times 2 \times 1 \\ &= 24 \text{ Anordnungen} \end{aligned}

Ein Spiel im Kreis

Acht Kinder stellen sich für ein Spiel $im Kreis$ auf. Die Anzahl der verschiedenen Formationen ist:

\begin{aligned} P_8 &= (8-1)! \\ &= 7! \\ &= 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\ &= 5\,040 \text{ Anordnungen} \end{aligned}

Paare auf benachbarten Plätzen

Bei $Zusatzbedingungen$ , etwa wenn bestimmte Objekte nebeneinanderliegen müssen, hilft die $Blockmethode$ :

Beispiel: $4$ Ehepaare sitzen im Kreis, wobei die beiden Personen jedes Paares nebeneinandersitzen müssen.

$Lösungsstrategie$ :

$Fasse$ jedes Paar zu einem Block zusammen: $4 \text{ Blöcke}$ .
$Ordne die Blöcke$ im Kreis an: $(4-1)! = 3! = 6 \text{ Anordnungen}$ .
$Vertausche die Plätze$ innerhalb jedes Paares: $2! \text{ Möglichkeiten}$ pro Paar.
$Multipliziere$ : $3! \times (2!)^4 = 6 \times 2^4 = 6 \times 16 = 96 \text{ Anordnungen}$ .

Übungsaufgaben

Es gibt $6$ Freunde, die am Lagerfeuer sitzen. Auf wie viele Arten können sie sitzen?
Aus $8$ Perlen in verschiedenen Farben wird ein Armband gefertigt. Wenn Drehungen und umgedrehte Spiegelbilder als dasselbe Armband gelten, wie viele Anordnungen sind dann möglich?
$5$ Ehepaare sitzen an einem runden Tisch. Die beiden Personen jedes Paares sollen nebeneinandersitzen. Wie viele Sitzordnungen sind möglich?
$7$ Lernende stellen sich im Kreis auf. Zwei bestimmte Personen dürfen nicht nebeneinanderstehen. Wie viele Anordnungen sind möglich?

Lösungen

$Aufgabe 1$

120 \text{ Wege}

Rechenweg:

Gegeben: $n = 6 \text{ Personen}$ Formel der Kreispermutation: $P_n = (n-1)!$

P_6 = (6-1)! = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120

Die $6 \text{ Personen}$ können also in $120$ verschiedenen Sitzordnungen am Lagerfeuer sitzen.

$Aufgabe 2$

2\,520 \text{ Wege}

Rechenweg:

Zunächst zählen gedrehte Anordnungen als gleich: $P_8 = (8-1)! = 7!$

7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5\,040

\frac{5\,040}{2} = 2\,520

Es gibt $2\,520$ verschiedene Armbänder.

$Aufgabe 3$

768 \text{ Wege}

Rechenweg:

Gegeben: $5$ Ehepaare, also $10 \text{ Personen}$ . Jedes Paar soll zusammensitzen. $Blockmethode$ : Jedes Paar bildet einen Block: $5 \text{ Blöcke}$ .

Kreispermutation der $5 \text{ Blöcke}$ : $(5-1)! = 4! = 4 \times 3 \times 2 \times 1 = 24$ . Innerhalb jedes Paares sind $2! = 2 \text{ Anordnungen}$ möglich.

Gesamt: $24 \times 2^5 = 24 \times 32 = 768$

Damit erfüllen $768$ Sitzordnungen die Bedingung.

$Aufgabe 4$

480 \text{ Wege}

Rechenweg mit der $Komplementmethode$ :

Gesamtzahl benachbarter Anordnungen: $120 \times 2 = 240$ $Gesuchte Anordnungen$ : $720 - 240 = 480$

Somit gibt es $480 \text{ Anordnungen}$ , bei denen die beiden Lernenden nicht nebeneinanderstehen.