Permutation - Kombinatorik einfach erklärt
Statistikquelle
https://www.youtube.com/watch?v=ASC1shbNr0A

Transkript (automatisch erstellt)

0:00 Im zweiten Video zu Kombinatorik besprechen wir noch die Permutation. Ich erkläre euch noch einmal kurz, was Permutation ist und seine Anwendung. Wir besprechen dabei Permutation mit
0:09 und ohne Wiederholung. Damit ihr die Formeln und das Konzept der Permutation besser versteht, zeige ich euch wieder, wie ihr euch die Permutationsformeln selbst einfach
0:18 herleiten könnt. Natürlich gibt’s zu allem wieder viele verschiedene Beispielen. Ihr solltet auf jeden Fall bereits das Video zu Variation und Kombination
0:25 gesehen haben. Viele Begriffe werde ich hier nicht mehr näher erläutern. Im Video zu Kombination und Variation haben wir bereits den Unterschied zur Permutation besprochen
0:42 und wir haben uns auch angesehen, wann man welche Formel verwendet. Hier noch einmal eine Übersicht. Noch einmal zur Wiederholung: Es handelt sich dann um Permutation,
0:51 wenn wir alle Elemente einer Menge betrachten, also keine Auswahl treffen und wir alle möglichen Anordnungen bestimmen wollen. Zum Beispiel, auf wie viele verschieden Arten drei unterschiedliche
1:02 Buchstaben angeordnet werden können. Wir unterscheiden zwischen Permutation mit und ohne Wiederholung. Mit Wiederholung oder mit zurücklegen haben wir, wenn wir gezogene Elemente
1:12 wieder zurückgeben und somit immer dieselbe Anzahl an Elementen haben. Wenn ich zum Beispiel eine Kugel aus einer Urne ziehe und diese wieder zurücklege nach der Ziehung. Wenn ich die
1:21 Kugel nicht mehr zurückgebe, verändert sich die Menge ständig und das wäre dann ohne Wiederholung. Wir sehen uns zuerst ein Beispiel für Permutation ohne Wiederholung an. Stellen wir uns vor,
1:34 wir haben 4 freie Parkplätze und wir wollen wissen, wie viele Möglichkeiten es gibt, 4 Autos auf diese freien Stellflächen aufzuteilen. Es werden alle Elemente verwendet,
1:44 somit haben wir also keine Auswahl. Wenn wir ein Auto ausgewählt haben, dann ist dieser Parkplatz voll. Somit also ohne zurücklegen und deswegen haben wir also Permutation ohne Wiederholung.
1:55 Für den ersten Parkplatz haben wir also 4 Autos zur Auswahl. Stellen wir nun ein Auto auf einen freien Platz, dann bleiben natürlich nur mehr 3 Autos übrig. Stellen wir das nächste Auto drauf,
2:05 dann haben wir noch 2 Autos zur Auswahl und zum Schluss haben wir nur noch eine Möglichkeit. Somit haben wir 4 * 3 * 2 * 1 also insgesamt 24 verschiedene
2:14 Möglichkeiten unsere Autos anzuordnen. Durch diese Überlegung können wir uns die Formel für Permutation ohne Wiederholung mühelos eigenständig herleiten. Wir hatten ja
2:24 n=4 Autos. Somit stehen uns für den ersten Platz n Autos zur Verfügung. Bei der zweiten Fläche, konnten wir 1 Auto weniger auswählen – oder anders ausgedrückt n-1. In weiterer Folge
2:36 reduzieren sich die Auswahlmöglichkeiten um n-2 für den dritten Platz und n-3 für den vierten. Diese Abfolge von Auswahlmöglichkeiten lässt sich als Produkt n * (n-1) * (n-2) * (n-3) darstellen,
2:49 was wiederum gleichbedeutend mit n Fakultät ist. So habt ihr euch die Formel schnell und einfach selbst abgeleitet und natürlich könnt ihr solche Aufgaben direkt mit der Formel lösen. Wir
2:56 hatten 4 Autos, somit 4 Fakultät was wiederum 24 Möglichkeiten ergibt. Zur Verdeutlichung kurz ein zweites Beispiel. Wir haben das Wort „Marke“. Wie viele Möglichkeiten
3:07 gibt es die Buchstaben anders anzuordnen. Wir verwenden alle Buchstaben, somit treffen wir keine Auswahl. Jeder Buchstabe kommt nur einmal vor, deswegen haben wir also erneut Permutation
3:17 ohne zurücklegen und die korrekte Formel ist n Fakultät. Wir haben n=5 Buchstaben, das heißt also n Fakultät entspricht 5 Fakultät was 120 mögliche Anordnungen ergibt.
3:33 Nun kommen wir zu Permutation mit Wiederholung. Sehen wir uns dazu direkt ein ähnliches Beispiel aber mit einem anderen Wort an. Wie viele Möglichkeiten gibt es die Buchstaben
3:41 des Wortes „Statistik“ anzuordnen. Der wesentliche Unterschied besteht darin, dass im vorherigen Fall, beim Wort "Marke", jeder Buchstabe nur einmal vorkam. Jetzt haben wir es
3:51 mit einer Permutation mit Wiederholung zu tun. Was ändert sich nun an unserer Formel? Wir beginnen, indem wir die Möglichkeiten so wie zuvor mit n Fakultät bestimmen. Wir haben 9 Buchstaben,
4:01 also 9! – was 362880 mögliche Anordnungen der Buchstaben ergibt. Bei Permutation ohne Wiederholung wären wir nun schon wieder fertig. Wir müssen jetzt aber noch etwas beachten.
4:14 Zuvor hatten wir wie erwähnt nur unterschiedliche Buchstaben. Das heißt, wenn ich die Buchstaben des Wortes „Marke“ anders anordnen möchte, kann ich jeden Buchstaben nur
4:22 einmal wählen. Beim Wort „Statistik“ kommen einzelne Buchstaben aber auch mehrmals vor. Das Wort hat 3 T´s, 2 mal S, 2 I´s, 1 A und 1 K. Würden wir zum Beispiel die 3 T´s (TTT) als
4:33 unterschiedliche Buchstaben betrachten, könnten wir sie wie soeben gelernt auf 3! – also auf 6 verschiedene Weisen anordnen. Wie ihr seht, macht es jetzt aber keinen Unterschied, welches dieser
4:44 drei T´s an der 1., 2. oder 3. Stelle steht. Da es jetzt also 3 mal derselbe Buchstabe ist, habe ich nicht 6 Möglichkeiten, wie ich TTT aufschreiben kann, sondern nur 1.
4:56 Da wir also nur 1 Anordnung anstelle von 6 haben, müssen wir diese Möglichkeiten noch aus unserem Ergebnis herausrechnen. Die 3 T´s können natürlich jetzt an jeder Stelle des Wortes vorkommen,
5:06 das heißt wir müssen das Ergebnis von vorher noch durch 3! dividieren. Wir haben auch 2 S bzw. 2 I´s. Auch die müssen wir rausdivideren. A und K kommen jeweils nur 1 mal vor,
5:17 das heißt die könnten wir eigentlich außen vor lassen, weil sie am Ergebnis nichts ändern. Der Vollständigkeit halber schreiben wir sie auch noch
5:24 mit auf. Das führt dann zu 15120 Anordnungen für die Buchstaben des Wortes „Statistik“. Das heißt, wir haben also die Anordnungen berechnet,
5:34 indem wir 9! durch 3!*2!*2!*1!*1! Gerechnet haben. Dies können wir auch allgemeiner formulieren mit: n! durch k1!*k2!* … * kj! und somit haben wir uns die Formel für Permutation mit Wiederholung
5:52 wieder einmal eigenständig abgeleitet. Sehen wir uns noch kurz zwei weitere Beispiele dazu an. Stellt euch vor, wir haben 12 Personen und wir haben in einem Hotel ein Vierbettzimmer,
6:03 2 Dreibettzimmer und ein Doppelzimmer zur Verfügung. Wir wollen wieder die Möglichkeiten berechnen, die 12 Personen auf die Zimmer aufzuteilen. Unsere Teilmengen sind die
6:13 jeweiligen Zimmer. Das heißt k1 ist gleich 4, k2 gleich 3, k3 ebenfalls 3 und k4 ist 2. Wir haben n=12 Personen, somit können wir die möglichen Anordnungen berechnen,
6:24 indem wir 12! durch 4!*3!*3!*2! rechnen. Wir haben zwei Dreibettzimmer, deswegen müssen wir hier auch 2mal durch 3! dividieren. Insgesamt ergibt das 277200 mögliche Anordnungen.
6:41 Als zweites Beispiel haben wir ein Kartenspiel mit 4 Personen. Unser Kartendeck 52 Karten, es setzt sich aus 4 Farben mit jeweils 13 Karten je Farbe zusammen. Wie viele unterschiedliche
6:53 Möglichkeiten gibt es, das gesamte Kartendeck auf die Personen aufzuteilen, wenn jede Person gleich viele Karten erhält? Wir teilen alle Karten auf, somit erhält jede Person jeweils 13 Karten.
7:04 Das bedeutet, wir haben jeweils 4 Partitionen zu jeweils 13 Karten. Die Teilmengen k1 bis k4 entsprechen also jeweils 13. Insgesamt haben wir n=52 Karten und die möglichen Anordnungen
7:17 lassen sich also wieder einfach bestimmen in dem wir 52! durch jeweils 4 mal 13! rechnen. Das ergibt 5,36 mal 10 hoch 28 –also sehr, sehr viele Möglichkeiten die Karten aufzuteilen.
7:33 Bei beiden Beispielen haben wir keine Auswahl getroffen und konnten gezogene Elemente wiederverwenden. Darum war es jetzt Permutation mit Wiederholung.