Permutationen

Betrachte eine Liste von Objekten. Eine Anordnung dieser Objekte (durch vertauschen) nennt man eine Permutation. Wir interessieren uns für die Anzahl der möglichen Permutationen, die gebildet werden können. Für diese Diskussion müssen wir zwischen dem Fall, dass alle Objekte unterschiedlich sind, und dem Fall, dass einige der Objekte ähnlich sein können, unterscheiden.

Alle Objekte sind unterschiedlich

Wir besprechen zunächst den Fall, dass alle Objekte unterschiedlich sind. Betrachten wir zum Beispiel das Wort TEA (die Objekte sind jetzt die Buchstaben T, E, A). Die Anzahl der möglichen Permutationen ist $6$:

TEA, TAE, ETA, EAT, AET, ATE

In der Tat, eine Möglichkeit, eine neue Permutation von TEA zu bilden, besteht darin, wiederholt einen Buchstaben aus TEA zu nehmen (ohne zurücklegen), um ein neues Wort zu bilden. Es gibt also $3$ Möglichkeiten, den ersten Buchstaben zu wählen, und für jede dieser drei Möglichkeiten gibt es zwei Möglichkeiten, den zweiten Buchstaben zu wählen, und für alle diese $3\cdot 2$ Möglichkeiten gibt es $1$ Möglichkeit, den letzten Buchstaben zu wählen. Insgesamt haben wir also

oder

mögliche Wege, das Wort umzustellen. Mit Hilfe eines Baumes können wir diesen Prozess auf elegante Weise darstellen:

Wenn wir das gleiche Argument für ein Wort mit $6$ verschiedenen Buchstaben verwenden, sehen wir, dass die Anzahl der möglichen Wörter, die wir bilden können,

ist, oder

Zusammenfassend gilt:

Einige Objekte sind gleich

Wenn einige der Objekte in der Liste identisch sind, ist es schwieriger, alle verschiedenen Anordnungen zu finden, da einige davon gleich sein werden.

Nehmen wir zum Beispiel das Wort "TESS". Wenn alle Buchstaben unterschiedlich wären, so wäre die Anzahl der möglichen Permutationen $4!=24$, aber da einige der Buchstaben in dem Wort gleich sind, werden einige dieser $24$ Wörter ebenfalls gleich sein (z.B. wenn man die letzten beiden Buchstaben vertauscht, erhält man zweimal das Wort TESS). Tatsächlich ist die Anzahl der verschiedenen Wörter, die man bilden kann, $12$:

TESS, TSES, TSSE, ETSS, ESTS, ESST, STES, STSE, SSTE, SSET, SETS, SEST

Wie kann man nun diese Zahl berechnen? Die Formel lautet

Die $4!$ im Zähler ist die Anzahl der Wörter, die wir bilden könnten, wenn alle Buchstaben unterschiedlich wären, und da jedes Wort verdoppelt wird (wegen der beiden "S"), müssen wir durch $2=2!$ dividieren

Schauen wir uns das Wort "MISSISSIPPI" an. Die Anzahl der verschiedenen Wörter ist

denn wenn alle Buchstaben unterschiedlich wären, gäbe es $11!$ mögliche Wörter, die wir bilden könnten, aber es gibt $4!\cdot 4!\cdot 2!$ mal zu viele Wörter, weil es $4$ S, $4$ I und 2 P gibt. Es ist hier nicht die Absicht, diese Formel zu beweisen. Wir werden nur den einfachsten Fall, in dem die Liste zwei verschiedene Arten von Objekten enthält, ausführlicher diskutieren.

Liste mit zwei Arten von Objekten

Betrachte das Wort

Die Anzahl der verschiedenen Wörter, die wir bilden können, ist

Wir wollen versuchen zu verstehen, warum dies so ist. Wir beginnen damit, dass wir den Buchstaben einen Index geben, damit wir sie unterscheiden können:

Die Anzahl der möglichen Wörter, die wir jetzt bilden können, ist $7!$. Wir bilden nun Gruppen: alle Wörter, die das gleiche Wort bilden würden, wenn die Indizes gelöscht würden, werden in eine Gruppe gelegt. Zum Beispiel die Wörter

sind in der gleichen Gruppe, weil sie das gleiche Wort

bilden, während die Wörter

in einer anderen Gruppe sind und bilden das Wort

bilden. Die nächste Frage ist nun: Wie viele Wörter gibt es in jeder Gruppe? Nun, es gibt $3!$ Möglichkeiten, die Indizes der $A$s neu anzuordnen, und für jede dieser Möglichkeiten gibt es $4!$ Möglichkeiten, die Indizes der $B$s anzuordnen. Insgesamt muss es also $3!\cdot 4!$ Wörter in jeder Gruppe geben. Wenn wir also die Indizes weglassen, hat jede Gruppe $3!\cdot 4!$ zu viele Wörter. Um die gleichen Wörter zu eliminieren, müssen wir also die $7!$ durch die $3!\cdot 4!$ dividieren. Und daraus folgt die obige Formel.