Permutationen

Das Problem, n Objekte (Personen, Gegenstände, Zahlen o. Ä.) in einer Reihe anzuordnen, d. h., sie auf n Plätze zu verteilen, führt zum Begriff der Permutation.

Jede mögliche Anordnung von n Elementen, in der alle Elemente verwendet werden, heißt Permutation $P_n$ dieser Elemente.

Man unterscheidet Permutationen ohne Wiederholung (der Elemente) und Permutationen mit Wiederholung (der Elemente).

Von n verschiedenen Elementen gibt es
$P_n=n\cdot \left(n-1\right)\cdot \mathrm{...}\cdot 3\cdot 2\cdot 1=n!\left(n\in \mathbb{N}\right)$
Möglichkeiten einer derartigen Anordnung (Permutationen ohne Wiederholung).

Anmerkung: Für das Produkt aufeinanderfolgender natürlicher Zahlen von 1 bis n verwendet man abkürzend die Schreibweise n! (gesprochen: n-Fakultät).

Beispiel 1:
Aus den drei Elementen der Menge $\left\{a;b;c\right\}$ lassen sich die folgenden sechs Permutationen bilden:
$abcacbbacbcacabcba$

Anmerkung: Beim Aufschreiben aller möglicher Permutationen von n Elementen ist es günstig, eine bestimmte Reihenfolge einzuhalten. Meist wählt man dabei die sogenannte lexikografische Anordnung, bei der die Reihenfolge der Elemente durch das Alphabet (bzw. bei Zahlen durch Ordnung nach ihrer Größe) festgelegt ist.

Beispiel 2:
Wie viele verschiedene Möglichkeiten gibt es, sechs Personen in einem ICE-Abteil mit sechs Platzen anzuordnen?
Lösung: $6!=720$

Treten bei Anordnungen Elemente mehrfach auf, so spricht man von Anordnungen mit Wiederholung. Im Vergleich zu dem Fall, dass alle Elemente voneinander verschieden sind, verringert sich die Zahl der mögliche Anordnungen.

Für die Anzahl der Permutationen von n Elementen mit Wiederholung (d. h., von n Elementen von denen je ${\alpha }_1,{\alpha }_2\mathrm{...}{\alpha }_r$untereinander gleich sind (wobei ${\alpha }_1+{\alpha }_2+\mathrm{...}+{\alpha }_r=n$ ist) gilt:
${}^{w}P{}_n=\frac{n!}{{\alpha }_1!\cdot {\alpha }_2!\cdot \mathrm{...}\cdot {\alpha }_r!}$

Beispiel 3:
Aus den vier Elementen der Menge $\left\{a;a;b;b\right\}$ lassen sich $\frac{4!}{2!\cdot 2!}=\frac{24}{2\cdot 2}=6$ verschiedene Permutationen bilden, und zwar:
$aabbabababbabaabbababbaa$

Bei Permutationen werden alle zur Verfügung stehenden Elemente angeordnet. Werden dagegen nur k der n Elemente angeordnet, d. h. wird eine Auswahl vorgenommen, so führt das zu Variationen bzw. Kombinationen.