Permutation (Kombinatorik)

Aus MM*Stat

(Weitergeleitet von Permutation mit Wiederholung)
Wechseln zu: Navigation, Suche

Kombinatorik

Kombinatorik • Binomialkoeffizient • Permutation (Kombinatorik) • Variation (Kombinatorik) • Kombination (Kombinatorik) • Multiple Choice • Video • Aufgaben • Lösungen
Eulersches Symbol • Kombination mit Wiederholung • Kombination ohne Wiederholung • Permutation mit Wiederholung • Permutation ohne Wiederholung • Variation mit Wiederholung • Variation ohne Wiederholung

Grundbegriffe

Permutation

Jede Zusammenstellung, in der alle n gegebenen Elemente in irgendeiner Anordnung stehen, heißt eine Permutation (lat. Vertauschung, Austausch, Umstellung).

Dies impliziert, dass sich Permutationen durch die unterschiedliche Anordnung der n Elemente ergeben.

Es können 2 Varianten von Permutationen unterschieden werden:

  1. Permutation mit Wiederholung
  2. Permutation ohne Wiederholung

Permutation ohne Wiederholung

Bei der Permutation ohne Wiederholung wird davon ausgegangen, dass alle n Elemente verschieden sind, also jedes Element nur einmal vorkommt.

Die Anzahl der möglichen Permutationen von n Elementen ohne Wiederholung, symbolisiert mit P(n), ist:

 P(n) = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n = n \, !

Permutation mit Wiederholung

Bei der Permutation mit Wiederholung wird davon ausgegangen, dass unter den n gegebenen Elementen mehrere Elemente identisch sind.

Es existiert also eine Gruppe von gleichen Elementen.

Die Anzahl der möglichen Permutationen aus n Elementen mit Wiederholung, symbolisiert mit P( n; g ), ist:

P(n; g) = \frac{n\,!}{g\,!} \qquad g \leq n,

wobei g die Anzahl der Elemente ist, die gleich sind (Größe der Gruppe).

Weiterhin gibt es Permutationen, bei welchen unter den n gegebenen Elementen mehrere Gruppen gleicher Elemente existieren.

Die Anzahl der möglichen Permutationen ist für r Gruppen:

P(n;g_{1}, \dots, g_{r}) = \frac{n\,!}{g_{1}\,! \cdot g_{2}\,!
\cdot \dots \cdot g_{r}\,!}

wobei g_i die Größe der i-ten Gruppe ist und g_{1} + g_{2} + g_{3} + \dots + g_{r} \leq n gelten muss.

Beispiele

Permutationen ohne Wiederholung

  • Für 2 verschiedene Elemente (a und b) ist die Anzahl der möglichen Permutationen  P(2)=1 \cdot 2 = 2\,! = 2.
Die beiden Permutationen sind logischerweise:
ab und ba
  • Für 3 verschiedene Elemente (a, b und c) ist die Anzahl der möglichen Permutationen  P(3) = 1 \cdot 2 \cdot 3 = 3\,! = 6.
Die sechs möglichen Permutationen sind:
abc acb bac bca cab cba

Permutationen mit Wiederholung

  • Zuerst wird wieder der Fall zweier Elemente betrachtet.
Für zwei verschiedene Elemente (a und b) ist die Anzahl der möglichen Permutationen P(2) = 2\,! / 1\, ! = 2 (wie bei der Permutation ohne Wiederholung):
aa ba
Für zwei identische Elemente (:a und a) ist die Anzahl der möglichen Permutationen P(2;2) = 2!/2! = 1.
Die einzig mögliche Permutation ist:
aa
  • Wenn g=1 (a, b und c) ist, so ist die Anzahl der möglichen Permutationen P(3) = 3!/1! = 6. Die sechs möglichen Permutationen sind:
abc acb bac bca cab cba
  • Wenn g=2 (a, a und b), ist, so ist die Anzahl der möglichen Permutationen P(3;2) = 3!/2! = 3. Die drei möglichen Permutationen sind:
aac aca caa
  • Wenn g=3 (a, a und a), ist, so ist die Anzahl der möglichen Permutationen P(3;3)=3!/3!=1. Die einzig mögliche Permutation ist:
aaa
Wie man sehen kann, ist die Permutation ohne Wiederholung ein Spezialfall der Permutation mit Wiederholung. Die Permutation mit Wiederholung einer Gruppe gleicher Elemente ist wiederum ein Spezialfall der Permutation mit Wiederholung mehrerer Gruppen gleicher Elemente.

Schönheitswettbewerb

An einem Schönheitswettbewerb nehmen 14 Bewerber teil. Jeder der anwesenden Juroren soll seine persönliche Rangliste der 14 Bewerber zusammenzustellen.

Wenn jeder der Juroren einen anderen Geschmack bezüglich der Platzierung hat, wieviele Juroren werden dann gebraucht, um alle möglichen (voneinander verschiedenen) Ranglisten der 14 Bewerber zu erhalten?

Da es sich in diesem Fall um eine Zusammenstellung aller n Elemente (hier die Bewerber) handelt, liegt eine Permutation vor.

Zu entscheiden ist jetzt noch, welche der zwei möglichen Permutationen - Permutation mit Wiederholung oder Permutation ohne Wiederholung - die richtige ist.

Da jeder Bewerber in einer Rangliste nur einmal platziert sein kann, liegt eine Permutation ohne Wiederholung vor.

P(n) = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n = n!

P(14) = 1 \cdot 2 \cdot 3 \cdot \dots \cdot 14 = 14! = 87\;178\;291\;200

Es werden mehr als 87 Milliarden Juroren gebraucht. Die aufzutreiben dürfte bei einer Erdbevölkerung von ca. 7,2 Milliarden (Jan. 2014) ein Problem werden.