3.2 Permutationen

3.2.1 Permutationen ohne Wiederholung

Für die Auswahl des ersten Bildes gibt es 4 Möglichkeiten. Bei der Auswahl des zweiten Bildes stehen nur noch 3 Bilder zur Verfügung. Das dritte Bild kann unter den noch verbliebenen zwei Bildern ausgewählt werden, und für das vierte Bild gibt es nur noch eine Möglichkeit. Nach dem Zählprinzip gibt es insgesamtAnordnungen der 4 Bilder nebeneinander.

2. Beim 100-m-Lauf werden 8 Bahnen unter den Läufern ausgelost. Wie viele verschiedene Startaufstellungen sind möglich?

Auslosen der ersten Bahn: 8 Möglichkeiten;
Auslosen der zweiten Bahn: noch 7 Möglichkeiten;
Auslosen der dritten Bahn: noch 6 Möglichkeiten;
...
Auslosen der siebten Bahn: noch 2 Möglichkeiten;
Auslosen der achten Bahn: noch 1 Möglichkeit.

Nach dem Zählprinzip gibt es insgesamt alsomögliche Startaufstellungen.

3. Die allgemeine Fragestellung, die in den Beispielen auftritt, lautet:

Wie viele Möglichkeiten gibt es, n verschiedene Dinge der Reihe nach anzuordnen?

Jede solche Anordnung wird eine Permutation genannt. Zu einer Menge mit n verschiedenen Elementen gibt es nach dem ZählprinzipPermutationen. Dieses Produkt aller natürlichen Zahlen von 1 bis n wird abgekürzt n! geschrieben und n Fakultät ausgesprochen.

Die Anzahl PoW der Permutationen ohne Wiederholung aus einer Menge mit n Elementen beträgt .

Die Fakultäten der natürlichen Zahlen wachsen rasch an:
 

n
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40 320
9	362 880

5. Nach der Definition gilt fürdie Beziehung. Damit sie auch für n =1 anwendbar ist (), muss die Definition von n! noch erweitert werden:

3.2.2 Permutationen mit Wiederholung

1. Im vorigen Abschnitt wurde eine Permutation als eine Anordnung von n verschiedenen Elementen zu einem n-Tupel beschrieben (). Im Folgenden soll zugelassen sein, dass Elemente gleich sein können. Es ergeben sich dann Permutationen mit Wiederholung.

Ein Beispiel für eine Permutation mit Wiederholung ist das Anagramm. Ein Anagramm ist eine beliebige Umstellung der Buchstaben eines Wortes, wobei die Wortlänge gleich bleibt. So ist z.B. TAPSA ein Anagramm des Wortes PASTA, ebenso TASAP oder PATSA.

Die Anagramme sind 5-Tupel. Die Anzahl aller Permutationen mit Wiederholung, also aller Anagramme des Wortes PASTA, beträgt nun aber nicht 5!. Der Buchstabe A tritt ja doppelt auf, und die Vertauschung der beiden A untereinander ergibt kein neues Anagramm. Daher reduziert sich die Anzahl der Anagramme auf.

2. Bei dem Wort PFIFF sind 5-Tupel zu bilden. Die Permutationen der 3 F untereinander ergeben kein neues Anagramm, also gibt es nurAnagramme.

3. PFIFFIG: Hier werden 7-Tupel gebildet. Die Permutationen der 2 I bzw. der 3 F untereinander liefern keine neuen Anagramme. Die Anzahl der Anagramme ist damit

4. Allgemein:
 

Die Anzahl PmW der Permutationen mit Wiederholung aus einer Menge mit n Elementen beträgt mit n > k und n1 + n2 + ... + nk = n .

Eine andere Formulierung:

Besteht ein n-Tupel aus k verschiedenen Elementen, die jeweils n₁, n₂, ..., n_k-mal vorkommen mit
n₁ + n₂ + ... + n_k = n, so gibt es

verschiedene n-Tupel.
 

Übung

Wieviel Anagramme gibt es aus den folgenden Wörtern?

a) ATLAS
b) MISSISSIPPI
c) ABRAKADABRA
d) PFEFFERFRESSER
e) KOALITIONSVEREINBARUNG