Permutation (Kombinatorik): Unterschied zwischen den Versionen

Aus MM*Stat

Wechseln zu: Navigation, Suche
(Die Seite wurde neu angelegt: „=={{Vorlage:Überschrift}}== ===Permutation=== Jede Zusammenstellung, in der alle <math>n</math> gegebenen Elemente in irgendeiner Anordnung stehen, hei…“)
 
({{Vorlage:Beispiele}})
Zeile 46: Zeile 46:
 
===Permutationen ohne Wiederholung===
 
===Permutationen ohne Wiederholung===
  
* Für 2 verschiedene [[Element]]e ([[Bild:STAT-Rot.gif]] und [[Bild:STAT-Grün.gif]]) ist die Anzahl der möglichen Permutationen <math> P(2)=1 \cdot 2 = 2\,! = 2</math>.
+
* Für 2 verschiedene [[Element]]e (<math>a</math> und <math>b</math>) ist die Anzahl der möglichen Permutationen <math> P(2)=1 \cdot 2 = 2\,! = 2</math>.
  
 
:Die beiden Permutationen sind logischerweise:
 
:Die beiden Permutationen sind logischerweise:
  
:[[Bild:STAT-Rot.gif]][[Bild:STAT-Grün.gif]] und [[Bild:STAT-Grün.gif]][[Bild:STAT-Rot.gif]]
+
:<math>ab</math> und <math>ba</math>
  
* Für 3 verschiedene [[Element]]e ([[Bild:STAT-Rot.gif]], [[Bild:STAT-Grün.gif]] und [[Bild:STAT-Gelb.gif]]) ist die Anzahl der möglichen Permutationen <math> P(3) = 1 \cdot 2 \cdot 3 = 3\,! = 6</math>.
+
* Für 3 verschiedene [[Element]]e (<math>a</math>, <math>b</math> und <math>c</math>) ist die Anzahl der möglichen Permutationen <math> P(3) = 1 \cdot 2 \cdot 3 = 3\,! = 6</math>.
  
 
:Die sechs möglichen Permutationen sind:
 
:Die sechs möglichen Permutationen sind:
  
:[[Bild:STAT-Rot.gif]][[Bild:STAT-Grün.gif]][[Bild:STAT-Gelb.gif]] [[Bild:STAT-Grün.gif]][[Bild:STAT-Rot.gif]][[Bild:STAT-Gelb.gif]] [[Bild:STAT-Gelb.gif]][[Bild:STAT-Rot.gif]][[Bild:STAT-Grün.gif]]
+
:<math>abc</math> <math>acb</math> <math>bac</math> <math>bca</math> <math>cab</math> <math>cba</math>
 
 
:[[Bild:STAT-Rot.gif]][[Bild:STAT-Gelb.gif]][[Bild:STAT-Grün.gif]] [[Bild:STAT-Grün.gif]][[Bild:STAT-Gelb.gif]][[Bild:STAT-Rot.gif]] [[Bild:STAT-Gelb.gif]][[Bild:STAT-Grün.gif]][[Bild:STAT-Rot.gif]]
 
  
 
===Permutationen mit Wiederholung===
 
===Permutationen mit Wiederholung===
Zeile 64: Zeile 62:
 
* Zuerst wird wieder der Fall zweier [[Element]]e betrachtet.  
 
* Zuerst wird wieder der Fall zweier [[Element]]e betrachtet.  
  
:Für zwei verschiedene [[Element]]e ([[Bild:STAT-Rot.gif]] und [[Bild:STAT-Grün.gif]]) ist die Anzahl der möglichen Permutationen <math>P(2) = 2\,! / 1\, ! = 2</math> (wie bei der [[Permutation ohne Wiederholung]]):
+
:Für zwei verschiedene [[Element]]e (<math>a</math> und <math>b</math>) ist die Anzahl der möglichen Permutationen <math>P(2) = 2\,! / 1\, ! = 2</math> (wie bei der [[Permutation ohne Wiederholung]]):
  
:[[Bild:STAT-Grün.gif]][[Bild:STAT-Rot.gif]] und [[Bild:STAT-Rot.gif]][[Bild:STAT-Grün.gif]]
+
:<math>aa</math> <math>ba</math>
  
:Für zwei identische [[Element]]e [[Bild:STAT-Rot.gif]] und [[Bild:STAT-Rot.gif]] ist die Anzahl der möglichen Permutationen <math>P(2;2) = 2!/2! = 1</math>.  
+
:Für zwei identische [[Element]]e (:<math>a</math> und <math>a</math>) ist die Anzahl der möglichen Permutationen <math>P(2;2) = 2!/2! = 1</math>.  
  
 
:Die einzig mögliche Permutation ist:
 
:Die einzig mögliche Permutation ist:
  
:[[Bild:STAT-Rot.gif]][[Bild:STAT-Rot.gif]]
+
:<math>aa</math>
  
 
* Für genau 3 [[Element]]e kann <math>g=1</math> (wie bei der [[Permutation ohne Wiederholung]]) oder <math>g=2</math> (zwei identische [[Element]]e und ein drittes verschiedenes) oder <math>g=3</math> (alle [[Element]]e sind identisch) sein:
 
* Für genau 3 [[Element]]e kann <math>g=1</math> (wie bei der [[Permutation ohne Wiederholung]]) oder <math>g=2</math> (zwei identische [[Element]]e und ein drittes verschiedenes) oder <math>g=3</math> (alle [[Element]]e sind identisch) sein:
  
:Wenn <math>g=1</math> ([[Bild:STAT-Rot.gif]], [[Bild:STAT-Grün.gif]], und [[Bild:STAT-Gelb.gif]]) ist, so ist die Anzahl der möglichen Permutationen <math>P(3) = 3!/1! = 6.</math>
+
:* Wenn <math>g=1</math> (<math>a</math>, <math>b</math> und <math>c</math>) ist, so ist die Anzahl der möglichen Permutationen <math>P(3) = 3!/1! = 6</math>. Die sechs möglichen Permutationen sind:
 
 
:Die sechs möglichen Permutationen sind:
 
 
 
:[[Bild:STAT-Rot.gif]][[Bild:STAT-Grün.gif]][[Bild:STAT-Gelb.gif]] [[Bild:STAT-Grün.gif]][[Bild:STAT-Rot.gif]][[Bild:STAT-Gelb.gif]] [[Bild:STAT-Gelb.gif]][[Bild:STAT-Rot.gif]][[Bild:STAT-Grün.gif]]
 
  
:[[Bild:STAT-Rot.gif]][[Bild:STAT-Gelb.gif]][[Bild:STAT-Grün.gif]] [[Bild:STAT-Grün.gif]][[Bild:STAT-Gelb.gif]][[Bild:STAT-Rot.gif]] [[Bild:STAT-Gelb.gif]][[Bild:STAT-Grün.gif]][[Bild:STAT-Rot.gif]]
+
::<math>abc</math> <math>acb</math> <math>bac</math> <math>bca</math> <math>cab</math> <math>cba</math>
  
:Wenn <math>g=2</math> ([[Bild:STAT-Rot.gif]] [[Bild:STAT-Rot.gif]], [[Bild:STAT-Gelb.gif]]), ist, so ist die Anzahl der möglichen Permutationen <math>P(3;2) = 3!/2! = 3</math>.
+
:* Wenn <math>g=2</math> (<math>a</math>, <math>a</math> und <math>b</math>), ist, so ist die Anzahl der möglichen Permutationen <math>P(3;2) = 3!/2! = 3</math>. Die drei möglichen Permutationen sind:
  
:Die drei möglichen Permutationen sind:
+
::<math>aac</math> <math>aca</math> <math>caa</math>
  
:[[Bild:STAT-Rot.gif]][[Bild:STAT-Rot.gif]][[Bild:STAT-Gelb.gif]] [[Bild:STAT-Rot.gif]][[Bild:STAT-Gelb.gif]][[Bild:STAT-Rot.gif]] [[Bild:STAT-Gelb.gif]][[Bild:STAT-Rot.gif]][[Bild:STAT-Rot.gif]]
+
:* Wenn <math>g=3</math> (<math>a</math>, <math>a</math> und <math>a</math>), ist, so ist die Anzahl der möglichen Permutationen <math>P(3;3)=3!/3!=1</math>. Die einzig mögliche Permutation ist:
 
 
:Wenn <math>g=3</math> ([[Bild:STAT-Rot.gif]], [[Bild:STAT-Rot.gif]], [[Bild:STAT-Rot.gif]]), ist, so ist die Anzahl der möglichen Permutationen <math>P(3;3)=3!/3!=1</math>.
 
 
 
:Die einzig mögliche Permutation ist:
 
  
:[[Bild:STAT-Rot.gif]][[Bild:STAT-Rot.gif]][[Bild:STAT-Rot.gif]]
+
::<math>aaa</math>
  
 
:Wie man sehen kann, ist die [[Permutation ohne Wiederholung]] ein Spezialfall der [[Permutation mit Wiederholung]]. Die [[Permutation mit Wiederholung]] einer [[Gruppe (Mengenlehre)|Gruppe]] gleicher [[Element]]e ist wiederum ein Spezialfall der [[Permutation mit Wiederholung]] mehrerer [[Gruppe (Mengenlehre)|Gruppen]] gleicher [[Element]]e.
 
:Wie man sehen kann, ist die [[Permutation ohne Wiederholung]] ein Spezialfall der [[Permutation mit Wiederholung]]. Die [[Permutation mit Wiederholung]] einer [[Gruppe (Mengenlehre)|Gruppe]] gleicher [[Element]]e ist wiederum ein Spezialfall der [[Permutation mit Wiederholung]] mehrerer [[Gruppe (Mengenlehre)|Gruppen]] gleicher [[Element]]e.

Version vom 11. September 2018, 11:59 Uhr

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.