Permutationen mit identischen Objekten

Warum identische Objekte die Anzahl ändern

Eine $Permutation mit identischen Objekten$ zählt Anordnungen, bei denen sich einige Objekte nicht voneinander unterscheiden lassen. Ihre Anzahl ist kleiner als bei einer gewöhnlichen Permutation, denn der Austausch $identischer Objekte$ erzeugt keine neue Anordnung.

Das Wort „MAMA“ zeigt den Grund. Es besteht aus $4$ Buchstaben, aber die beiden $M$ sind ebenso wenig unterscheidbar wie die beiden $A$ . Würden wir die Kopien vorübergehend beschriften, zählte ein Tausch der Beschriftungen als neue Permutation, obwohl das sichtbare Wort unverändert bliebe.

Alle Ergebnisse lassen sich ohne vorübergehende Beschriftungen auflisten. Wähle zwei Positionen für M und fülle die beiden übrigen Positionen mit A.

Positionen von M	Sichtbare Anordnung
1, 2	MMAA
1, 3	MAMA
1, 4	MAAM
2, 3	AMMA
2, 4	AMAM
3, 4	AAMM

Es gibt sechs Ergebnisse. Sind alle Kopien beschriftet, wird jedes sichtbare Ergebnis $2!\times2!=4$ -mal gezählt. Daher gilt $4!/(2!\times2!)=24/4=6$ .

Formel für Permutationen mit identischen Objekten

Sind $n$ Objekte in Gruppen identischer Objekte aufgeteilt, ergibt sich $die Anzahl der verschiedenen Anordnungen$ aus:

P = \frac{n!}{r_1! \times r_2! \times r_3! \times \cdots \times r_k!}

Die Symbole in der Formel bedeuten:

$n$ = Gesamtzahl der Objekte
$r_1, r_2, r_3, \ldots, r_k$ = Anzahl identischer Objekte in jeder Gruppe
$k$ = Anzahl der Gruppen identischer Objekte
Die Häufigkeiten umfassen jedes Objekt, also $r_1 + r_2 + \cdots + r_k = n$

Wir zählen, wie oft jedes unterschiedliche Objekt vorkommt. Die Division durch $r_i!$ entfernt die Mehrfachzählungen, die durch den Tausch identischer Kopien innerhalb einer Gruppe entstehen.

Anwendung auf Wörter und Buchstaben

Dieselbe Division funktioniert bei Wörtern, weil ein $wiederholter Buchstabe$ identische Kopien erzeugt. Das Beispiel unten zählt die Buchstaben von KALIMANTAN und teilt durch die wiederholten Gruppen.

Beispielwort KALIMANTAN

Am Wort „KALIMANTAN“ lässt sich der Rechenweg vollständig verfolgen.

Wir schreiben die Buchstaben der Reihe nach auf: K-A-L-I-M-A-N-T-A-N

Gesamtzahl der Buchstaben: $10$

Die wiederholten Buchstaben sind $A$ mit $3$ Vorkommen und $N$ mit $2$ Vorkommen. Alle übrigen Buchstaben kommen jeweils einmal vor.

$Berechnung$ :

P = \frac{10!}{1! \times 3! \times 1! \times 1! \times 1! \times 2! \times 1!}

Zuerst kürzen wir die gemeinsamen Faktoren:

= \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3!}{3! \times 2!}

Nun rechnen wir schrittweise:

Zuerst teilen wir $10$ durch $2$ : $\frac{10}{2} = 5$
Das verbleibende Produkt ist $5 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 = 302\,400$

Beispielwort PALAPA

Das Wort „PALAPA“ hat $6$ Buchstaben: Wir schreiben sie der Reihe nach auf: P-A-L-A-P-A

$Häufigkeiten$ : $P$ kommt $2 \text{ Mal}$ vor (Positionen $1, 5$ ), $A$ kommt $3 \text{ Mal}$ vor (Positionen $2, 4, 6$ ) und $L$ kommt $1 \text{ Mal}$ vor.

Die benötigten Fakultäten sind:

$6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$
$2! = 2 \times 1 = 2$
$3! = 3 \times 2 \times 1 = 6$

Die Berechnung lautet also:

P = \frac{6!}{2! \times 3! \times 1!}

Wir vereinfachen, indem wir $6$ durch $2$ teilen:

$\frac{6}{2} = 3$
Damit erhalten wir $3 \times 5 \times 4 = 60 \text{ Anordnungen}$ .

Anordnungen mit identischen Objekten zählen

Für jede Anordnung mit wiederholten Objekten gelten dieselben Schritte:

$Gesamtzahl bestimmen$ : Lies den Wert von $n$ ab.
$Identische Objekte gruppieren$ : Fasse gleiche Objekte zusammen.
$Häufigkeiten zählen$ : Bestimme, wie oft jedes Objekt vorkommt.
$Formel einsetzen$ : Übertrage die Häufigkeiten in die Permutationsformel.
$Fakultäten berechnen$ : Kürze zuerst und rechne dann sorgfältig aus.

Anordnungen von BANANA

Wir wenden die Schritte auf das Wort „BANANA“ an:

$Schritt 1$ : Gesamtzahl der Objekte

Wir schreiben die Buchstaben der Reihe nach auf: B-A-N-A-N-A

Gesamtzahl der Buchstaben: $n = 6$

Buchstabengruppen und Häufigkeiten lassen sich gemeinsam ablesen. Die drei Zeilen erfassen alle $1+3+2=6$ Buchstaben.

Buchstabe	Gruppenmitglieder	Häufigkeit
B	B	1
A	A, A, A	3
N	N, N	2

$Schritt 2$ : Formel anwenden

Wir setzen die Häufigkeiten in die Formel ein:

P = \frac{n!}{r_1! \times r_2! \times r_3!}

$Schritt 3$ : Fakultät berechnen

Zuerst vereinfachen wir den Bruch:

P = \frac{6!}{1! \times 3! \times 2!}

Nach dem Kürzen rechnen wir aus:

Wir teilen $6$ durch $2$ : $\frac{6}{2} = 3$
Es bleibt: $3 \times 5 \times 4 = 60$

Das Wort „BANANA“ besitzt also $60$ .

Unterschied zur gewöhnlichen Permutation

$Gewöhnliche Permutation$ : Alle Objekte sind verschieden. Die Formel lautet $n!$ .

$Permutation mit identischen Objekten$ : Gleiche Objekte erzeugen keine neue sichtbare Anordnung. Die Formel lautet:

\frac{n!}{r_1! \times r_2! \times \cdots \times r_k!}

$Vergleichsbeispiel$ :

Die verschiedenen Buchstaben A, B, C, D lassen sich auf $4! = 24 \text{ Arten}$ anordnen.

Bei den Buchstaben $A, A, B, C$ sind zwei Objekte identisch:

\frac{4!}{2!} = \frac{24}{2} = 12 \text{ Anordnungen}

Identische Objekte $verringern$ die Anzahl, weil ihr Austausch keine neue sichtbare Anordnung erzeugt.

Übungen

Jede Aufgabe ordnet eine Multimenge an, sodass wiederholte Buchstaben, Farben oder Ziffern herausgeteilt werden müssen. Zähle zuerst alle Anordnungen und $teile dann durch die Fakultäten der wiederholten Gruppen$ .

Wie viele Buchstabenanordnungen können aus dem Wort „MATEMATIKA“ gebildet werden?
Ein Blumenladen ordnet $8$ Rosen in einer Reihe. Nur die Farbe zählt: $3$ sind rot, $3$ sind weiß und $2$ sind gelb. Wie viele Farbanordnungen sind möglich?
Wie viele Zahlen lassen sich aus den Ziffern $1, 1, 2, 2, 2, 3$ als $6$ -stellige Zahlen bilden?
Wie viele verschiedene Buchstabenanordnungen hat das Wort „INDONESIA“?

Lösungen

$Aufgabe 1$

Das Wort „MATEMATIKA“ hat $10$ Buchstaben

$Buchstaben nacheinander$ : M-A-T-E-M-A-T-I-K-A

$Häufigkeiten$ : $M$ kommt $2 \text{ Mal}$ vor (Positionen $1, 5$ ), $A$ kommt $3 \text{ Mal}$ vor (Positionen $2, 6, 10$ ), $T$ kommt $2 \text{ Mal}$ vor (Positionen $3, 7$ ), $E$ kommt $1 \text{ Mal}$ vor, $I$ kommt $1 \text{ Mal}$ vor und $K$ kommt $1 \text{ Mal}$ vor.

Wir kürzen zunächst die gemeinsamen Faktoren:

P = \frac{10!}{2! \times 3! \times 2! \times 1! \times 1! \times 1!}

Danach rechnen wir aus:

Das Produkt ist $10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 = 604\,800$ .
Durch $4$ geteilt ergibt das $\frac{604\,800}{4} = 151\,200 \text{ Anordnungen}$ .

$Aufgabe 2$

Es gibt $8$ Farbpositionen: Rot kommt $3$ -mal vor, Weiß $3$ -mal und Gelb $2$ -mal.

Wir kürzen zunächst die gemeinsamen Faktoren:

P = \frac{8!}{3! \times 3! \times 2!}

Danach rechnen wir weiter:

Wir kürzen $6$ gegen $12$ : $\frac{6}{12} = \frac{1}{2}$ .
Es bleibt: $8 \times 7 \times \frac{1}{2} \times 5 \times 4$ .
$= 4 \times 7 \times 5 \times 4 = 560 \text{ Anordnungen}$

$Aufgabe 3$

Ziffern $1, 1, 2, 2, 2, 3$ (insgesamt $6$ Ziffern)

$Häufigkeiten$ : Die Ziffer $1$ kommt $2 \text{ Mal}$ vor, die Ziffer $2$ kommt $3 \text{ Mal}$ vor und die Ziffer $3$ kommt $1 \text{ Mal}$ vor.

Wir kürzen zunächst die gemeinsamen Faktoren:

P = \frac{6!}{2! \times 3! \times 1!}

Danach rechnen wir aus:

Wir teilen $6$ durch $2$ : $\frac{6}{2} = 3$ .
Damit erhalten wir $3 \times 5 \times 4 = 60 \text{ Zahlen}$ .

$Aufgabe 4$

Das Wort „INDONESIA“ hat $9$ Buchstaben

$Buchstaben nacheinander$ : I-N-D-O-N-E-S-I-A

$Häufigkeiten$ : $I$ kommt $2 \text{ Mal}$ vor (Positionen $1, 8$ ), $N$ kommt $2 \text{ Mal}$ vor (Positionen $2, 5$ ), $D$ kommt $1 \text{ Mal}$ vor, $O$ kommt $1 \text{ Mal}$ vor, $E$ kommt $1 \text{ Mal}$ vor, $S$ kommt $1 \text{ Mal}$ vor und $A$ kommt $1 \text{ Mal}$ vor.

Wir kürzen zunächst die gemeinsamen Faktoren:

P = \frac{9!}{2! \times 2! \times 1! \times 1! \times 1! \times 1! \times 1!}

Danach rechnen wir aus:

Wir teilen durch $2$ : $\frac{8}{2} = 4$ .
Es bleibt: $9 \times 4 \times 7 \times 6 \times 5 \times 4 \times 3$ .
$= 9 \times 4 \times 7 \times 6 \times 5 \times 4 \times 3 = 90\,720 \text{ Anordnungen}$

Warum identische Objekte die Anzahl ändern

Alle Ergebnisse lassen sich ohne vorübergehende Beschriftungen auflisten. Wähle zwei Positionen für M und fülle die beiden übrigen Positionen mit A.

Positionen von M	Sichtbare Anordnung
1, 2	MMAA
1, 3	MAMA
1, 4	MAAM
2, 3	AMMA
2, 4	AMAM
3, 4	AAMM

Es gibt sechs Ergebnisse. Sind alle Kopien beschriftet, wird jedes sichtbare Ergebnis $2!\times2!=4$ -mal gezählt. Daher gilt $4!/(2!\times2!)=24/4=6$ .

Formel für Permutationen mit identischen Objekten

Sind $n$ Objekte in Gruppen identischer Objekte aufgeteilt, ergibt sich $die Anzahl der verschiedenen Anordnungen$ aus:

P = \frac{n!}{r_1! \times r_2! \times r_3! \times \cdots \times r_k!}

Die Symbole in der Formel bedeuten:

$n$ = Gesamtzahl der Objekte
$r_1, r_2, r_3, \ldots, r_k$ = Anzahl identischer Objekte in jeder Gruppe
$k$ = Anzahl der Gruppen identischer Objekte
Die Häufigkeiten umfassen jedes Objekt, also $r_1 + r_2 + \cdots + r_k = n$

Wir zählen, wie oft jedes unterschiedliche Objekt vorkommt. Die Division durch $r_i!$ entfernt die Mehrfachzählungen, die durch den Tausch identischer Kopien innerhalb einer Gruppe entstehen.

Anwendung auf Wörter und Buchstaben

Beispielwort KALIMANTAN

Am Wort „KALIMANTAN“ lässt sich der Rechenweg vollständig verfolgen.

Wir schreiben die Buchstaben der Reihe nach auf: K-A-L-I-M-A-N-T-A-N

Gesamtzahl der Buchstaben: $10$

Die wiederholten Buchstaben sind $A$ mit $3$ Vorkommen und $N$ mit $2$ Vorkommen. Alle übrigen Buchstaben kommen jeweils einmal vor.

$Berechnung$ :

P = \frac{10!}{1! \times 3! \times 1! \times 1! \times 1! \times 2! \times 1!}

Zuerst kürzen wir die gemeinsamen Faktoren:

= \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3!}{3! \times 2!}

Nun rechnen wir schrittweise:

Zuerst teilen wir $10$ durch $2$ : $\frac{10}{2} = 5$
Das verbleibende Produkt ist $5 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 = 302\,400$

Beispielwort PALAPA

Das Wort „PALAPA“ hat $6$ Buchstaben: Wir schreiben sie der Reihe nach auf: P-A-L-A-P-A

$Häufigkeiten$ : $P$ kommt $2 \text{ Mal}$ vor (Positionen $1, 5$ ), $A$ kommt $3 \text{ Mal}$ vor (Positionen $2, 4, 6$ ) und $L$ kommt $1 \text{ Mal}$ vor.

Die benötigten Fakultäten sind:

$6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$
$2! = 2 \times 1 = 2$
$3! = 3 \times 2 \times 1 = 6$

Die Berechnung lautet also:

P = \frac{6!}{2! \times 3! \times 1!}

Wir vereinfachen, indem wir $6$ durch $2$ teilen:

$\frac{6}{2} = 3$
Damit erhalten wir $3 \times 5 \times 4 = 60 \text{ Anordnungen}$ .

Anordnungen mit identischen Objekten zählen

Für jede Anordnung mit wiederholten Objekten gelten dieselben Schritte:

$Gesamtzahl bestimmen$ : Lies den Wert von $n$ ab.
$Identische Objekte gruppieren$ : Fasse gleiche Objekte zusammen.
$Häufigkeiten zählen$ : Bestimme, wie oft jedes Objekt vorkommt.
$Formel einsetzen$ : Übertrage die Häufigkeiten in die Permutationsformel.
$Fakultäten berechnen$ : Kürze zuerst und rechne dann sorgfältig aus.

Anordnungen von BANANA

Wir wenden die Schritte auf das Wort „BANANA“ an:

$Schritt 1$ : Gesamtzahl der Objekte

Wir schreiben die Buchstaben der Reihe nach auf: B-A-N-A-N-A

Gesamtzahl der Buchstaben: $n = 6$

Buchstabengruppen und Häufigkeiten lassen sich gemeinsam ablesen. Die drei Zeilen erfassen alle $1+3+2=6$ Buchstaben.

Buchstabe	Gruppenmitglieder	Häufigkeit
B	B	1
A	A, A, A	3
N	N, N	2

$Schritt 2$ : Formel anwenden

Wir setzen die Häufigkeiten in die Formel ein:

P = \frac{n!}{r_1! \times r_2! \times r_3!}

$Schritt 3$ : Fakultät berechnen

Zuerst vereinfachen wir den Bruch:

P = \frac{6!}{1! \times 3! \times 2!}

Nach dem Kürzen rechnen wir aus:

Wir teilen $6$ durch $2$ : $\frac{6}{2} = 3$
Es bleibt: $3 \times 5 \times 4 = 60$

Das Wort „BANANA“ besitzt also $60$ .

Unterschied zur gewöhnlichen Permutation

$Gewöhnliche Permutation$ : Alle Objekte sind verschieden. Die Formel lautet $n!$ .

$Permutation mit identischen Objekten$ : Gleiche Objekte erzeugen keine neue sichtbare Anordnung. Die Formel lautet:

\frac{n!}{r_1! \times r_2! \times \cdots \times r_k!}

$Vergleichsbeispiel$ :

Die verschiedenen Buchstaben A, B, C, D lassen sich auf $4! = 24 \text{ Arten}$ anordnen.

Bei den Buchstaben $A, A, B, C$ sind zwei Objekte identisch:

\frac{4!}{2!} = \frac{24}{2} = 12 \text{ Anordnungen}

Identische Objekte $verringern$ die Anzahl, weil ihr Austausch keine neue sichtbare Anordnung erzeugt.

Übungen

Wie viele Buchstabenanordnungen können aus dem Wort „MATEMATIKA“ gebildet werden?
Ein Blumenladen ordnet $8$ Rosen in einer Reihe. Nur die Farbe zählt: $3$ sind rot, $3$ sind weiß und $2$ sind gelb. Wie viele Farbanordnungen sind möglich?
Wie viele Zahlen lassen sich aus den Ziffern $1, 1, 2, 2, 2, 3$ als $6$ -stellige Zahlen bilden?
Wie viele verschiedene Buchstabenanordnungen hat das Wort „INDONESIA“?

Lösungen

$Aufgabe 1$

Das Wort „MATEMATIKA“ hat $10$ Buchstaben

$Buchstaben nacheinander$ : M-A-T-E-M-A-T-I-K-A

Wir kürzen zunächst die gemeinsamen Faktoren:

P = \frac{10!}{2! \times 3! \times 2! \times 1! \times 1! \times 1!}

Danach rechnen wir aus:

Das Produkt ist $10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 = 604\,800$ .
Durch $4$ geteilt ergibt das $\frac{604\,800}{4} = 151\,200 \text{ Anordnungen}$ .

$Aufgabe 2$

Es gibt $8$ Farbpositionen: Rot kommt $3$ -mal vor, Weiß $3$ -mal und Gelb $2$ -mal.

Wir kürzen zunächst die gemeinsamen Faktoren:

P = \frac{8!}{3! \times 3! \times 2!}

Danach rechnen wir weiter:

Wir kürzen $6$ gegen $12$ : $\frac{6}{12} = \frac{1}{2}$ .
Es bleibt: $8 \times 7 \times \frac{1}{2} \times 5 \times 4$ .
$= 4 \times 7 \times 5 \times 4 = 560 \text{ Anordnungen}$

$Aufgabe 3$

Ziffern $1, 1, 2, 2, 2, 3$ (insgesamt $6$ Ziffern)

$Häufigkeiten$ : Die Ziffer $1$ kommt $2 \text{ Mal}$ vor, die Ziffer $2$ kommt $3 \text{ Mal}$ vor und die Ziffer $3$ kommt $1 \text{ Mal}$ vor.

Wir kürzen zunächst die gemeinsamen Faktoren:

P = \frac{6!}{2! \times 3! \times 1!}

Danach rechnen wir aus:

Wir teilen $6$ durch $2$ : $\frac{6}{2} = 3$ .
Damit erhalten wir $3 \times 5 \times 4 = 60 \text{ Zahlen}$ .

$Aufgabe 4$

Das Wort „INDONESIA“ hat $9$ Buchstaben

$Buchstaben nacheinander$ : I-N-D-O-N-E-S-I-A

Wir kürzen zunächst die gemeinsamen Faktoren:

P = \frac{9!}{2! \times 2! \times 1! \times 1! \times 1! \times 1! \times 1!}

Danach rechnen wir aus:

Wir teilen durch $2$ : $\frac{8}{2} = 4$ .
Es bleibt: $9 \times 4 \times 7 \times 6 \times 5 \times 4 \times 3$ .
$= 9 \times 4 \times 7 \times 6 \times 5 \times 4 \times 3 = 90\,720 \text{ Anordnungen}$