Herzlich willkommen zu diesem Video über Permutation und Kombination.
Es setzt voraus, dass man ein begriffliches Verständnis von
Binomialkoeffizienten besitzt.
Man sollte also wissen, dass der Binomialkoeffizient n über k gleich
der Anzahl der Möglichkeiten ist, aus n Dingen k auszuwählen, wobei
nicht auf die Reihenfolge beim Auswählen geachtet wird.
n über k ist also die Anzahl der Möglichkeiten, aus einer n
-elementigen Menge eine k-elementige Teilmenge zu bilden.
Was sind Permutation und Kombination?
Vorab die wichtigsten Botschaften hierzu.
Beides sind Tupel.
Doch was sind Tupel?
Tupel sind nichts anderes als geordnete Listen, die man so schreibt.
Man sieht hier eine Liste der Länge k, die man ein k-Tupel nennt.
Solch ein k-Tupel hat k Plätze oder Stellen, auf denen irgendwelche
Objekte a1 bis ak stehen.
Das heißt a1 steht auf Platz 1 im Tupel, a2 auf Platz 2 und so weiter.
Die Plätze sind durch Kommata getrennt und es gibt zu Beginn eine
öffnende und am Ende eine schließende Klammer.
Man nennt a1 bis ak auch die Komponenten des Tupels.
Wichtig ist hier, zwei solche k-Tupel sind genau dann gleich, wenn sie
komponentenweise übereinstimmen, das heißt es kommt auf die
Reihenfolge an, in der die Objekte aufgelistet sind.
Die nächste Botschaft ist die, dass der manchmal noch verwendete
Begriff Variation überflüssig ist.
Es reichen also die Begriffe Permutation und Kombination völlig aus.
Wir werden im folgenden auch Anzahlen von Permutation und Kombination
betrachten.
Hierfür ist die sogenannte Multiplikationsregel der Kombinatorik
entscheidend, zu der ich ein eigenes Video gemacht habe.
Was besagt diese Regel?
Gibt es bei einem k-Tupel wie oben j1 Möglichkeiten für die Wahl von
a1, dann, das heißt unabhängig von der erfolgten Wahl von a1, j2
Möglichkeiten für die Wahl von a2, dann, ganz egal wie a1 und a2
gewählt wurden, j3 Möglichkeiten für a3 und so weiter, so lassen sich
insgesamt j1 mal j2 mal und so weiter mal jk-Tupel a1 bis ak bilden.
Beispiele hierfür gibt es zuhauf.
Man denke etwa an Zahlenschlösser.
Da ist meist k gleich 4 und jedes aj ist eine der 10 Ziffern von 0 bis
9.
Insgesamt existieren also 10 mal 10 mal 10 mal 10, also 10 hoch 4 und
damit 10.000 Einstellungen des Schlosses.
Ein weiteres Beispiel sind Einlaufreihenfolgen bei Rennen.
Hier ist a1 die Person, die als Erste ins Ziel kommt, a2 die, die als
Zweite das Ziel erreicht und so weiter.
Interessieren etwa nur die ersten 3 Plätze und starten insgesamt 8
Personen, so gibt es 8 Möglichkeiten für den Sieger, dann, unabhängig
davon, wer der Sieger ist, 7 Möglichkeiten für den Zweitplatzierten
und dann, ganz egal wer die beiden Ersten sind, noch 6 Möglichkeiten
für den Drittplatzierten.
Begrifflich gleichwertig hierzu ist die Ziehung der Lottozahlen in
zeitlicher Reihenfolge.
Hier konkurrieren insgesamt 49 Zahlen gleichsam als Läufer.
Eine Zahl wird zuerst gezogen, dafür gibt es 49 Möglichkeiten.
Für die zweite Zahl dann noch 48 Möglichkeiten und so weiter.
Ein weiteres Beispiel sind Passwörter.
Ein 10-stelliges Passwort ist mathematisch ein Zehntupel und die
Komponenten können Klein- oder Großbuchstaben, Ziffern und gewisse
Sonderzeichen sein.
Sind zum Beispiel für jede Stelle im Passwort 65 Zeichen erlaubt, so
gibt es ohne jedwede Einschränkung 65 hoch 10 verschiedene Passwörter.
Gewisse Passwörter sind jedoch ausgeschlossen, so muss zum Beispiel
mindestens ein Groß- und ein Kleinbuchstabe sowie ein Sonderzeichen
dabei sein.
Die Anzahl der erlaubten Passwörter ist deutlich schwieriger zu
bestimmen.
Natürlich gibt es weitere Beispiele, aber das Video sollte nicht zu
lang sein und so kommen wir direkt zum wichtigen Begriff einer K
-Permutation.
Hierzu sei m eine Menge mit n Elementen.
Für Anzahlprobleme können wir immer ohne Beschränkung der
Allgemeinheit annehmen, dass m die Menge der Zahlen von 1 bis n ist,
denn wir können die Elemente der Menge von 1 bis n durchnummerieren.
Die erste Definition ist die, man nennt ein K-Tubel, dessen
Komponenten sämtlich aus m sind, eine K-Permutation aus m mit
Wiederholung und ich kürze mit Wiederholung so ab.
Die Menge all dieser K-Permutationen mit Wiederholung wird mit diesem
Pair unten k oben m, mw abgekürzt.
Der Zusatz mit Wiederholung betont, dass jedes aj völlig frei aus der
Menge m gewählt werden kann.
Es können also gewisse Komponenten im Tubel gleich sein.
Will man das ausschließen, fordert man also, dass je zwei der
Komponenten im Tubel verschieden sein sollen, so nennt man das K-Tubel
eine K-Permutation aus m ohne Wiederholung, kurz ow.
Das geht natürlich nur, wenn k höchstens gleich n ist.
Die Menge aller dieser K-Permutationen ohne Wiederholung kürzt man so
ab.
Der Unterschied zu oben besteht nur darin, dass jetzt ow anstelle von
mw steht.
Ein wichtiger Spezialfall von b entsteht, wenn k gleich n ist.
Dann spricht man auch kurz von Permutationen der Menge m.
Eine solche Permutation von m ist eine eindeutige, eine bijektive
Abbildung der Menge m auf sich selbst.
Sind die Elemente von m von 1 bis n durchnummeriert, so ist im n-Tubel
mit Komponenten a1 bis an die j-Komponente aj das Element von m, auf
das j abgebildet wird.
Wir können die Anzahlen der K-Permutationen mit bzw.
ohne Wiederholung leicht bestimmen.
Nach der Multiplikationsregel ist die Anzahl der K-Permutationen mit
Wiederholung gleich n hoch k, denn für jede Stelle im Tubel gibt es n
Möglichkeiten.
Bei den K-Permutationen ohne Wiederholung gibt es für a1 n
Möglichkeiten, dann für a2 nur noch n-1 Möglichkeiten, für a3 nur noch
n -2 Möglichkeiten usw.
und dann für ak nur noch n-k-1 in Klammern Möglichkeiten, sodass
dieses Produkt mit k Faktoren entsteht.
Man kann es in dieser Weise mit Hilfe von Fakultäten ausdrücken und es
findet sich dafür auch diese Kurzschreibweise, die man als n-tief-k
oder auch als die Karte absteigende Faktorielle von n liest.
Um diese Folie abzuschließen, ist m die Menge der Zahlen von 1 bis n,
so schreibt man die K-Permutation der Menge m auch so, dass man oben
anstelle von M das n setzt.
Wir kommen jetzt zu den K-Kombinationen und setzen voraus, dass die
Menge m die Menge der Zahlen von 1 bis n ist, was wir nämlich jetzt
benötigen ist, dass man mit diesen Zahlen Größenvergleiche anstellen
kann.
Ist m eine allgemeine n-elementige Menge, so müssen wir fordern, dass
es auf dieser Menge eine kleine Gleichrelation gibt, die eine
sogenannte Totalordnung ist.
Ich möchte aber darauf nicht weiter eingehen.
Die erste Definition ist die einer K-Kombination mit Wiederholung.
Eine K-Permutation mit Wiederholung, bei der die Zahlen aufsteigend
sortiert sind, das heißt es gilt a1 kleinergleich a2 und so weiter
kleinergleich ak, heißt K-Kombination mit Wiederholung.
Man sieht also, auch K-Kombinationen sind wie die K-Permutationen K
-Tupel.
Die Komponenten des Tupels genügen aber einer rot hervorgehobenen
kleiner Gleichbeziehung.
Insbesondere sind Gleichheitszeichen möglich, sodass, wie der Zusatz
mit Wiederholung betont, Komponenten im Tupel mehrfach auftreten
können.
Die Menge aller K-Kombinationen mit Wiederholung wird so abgekürzt.
Teil b der Definition betrifft K-Kombinationen ohne Wiederholung.
Man nennt eine K-Permutation ohne Wiederholung mit der Eigenschaft,
dass die Komponenten diesen kleineren Beziehungen genügen und damit
insbesondere alle verschieden sind, eine K-Kombination aus M ohne
Wiederholung.
Die Menge aller K-Kombinationen ohne Wiederholung wird in dieser Weise
abgekürzt.
Wo treten Kombinationen mit Wiederholung auf?
Dieses Bild zeigt das Ergebnis eines Wurfes mit acht nicht
unterscheidbaren Würfeln.
Drei der Würfel zeigen eine 1, einer eine 2, zwei eine 3, einer eine 5
und einer eine 6.
Gedanklich können wir anstelle der Augenzahlen natürliche Zahlen
hinschreiben und Kommata sowie Klammern einfügen und erhalten eine 8
-Kombination der Zahlen von 1 bis 6 mit Wiederholung.
Hätte ein Geschäft nur sechs verschiedene Artikel, die von 1 bis 6
durchnummeriert und jeweils in großer Zahl verfügbar sind, so sieht
man hier das Ergebnis eines Einkaufs mit insgesamt acht Artikeln.
Artikel Nummer 1 wurde dreimal gekauft, Artikel Nummer 2 einmal und so
weiter.
Was die K-Kombination ohne Wiederholung betrifft, sollte man folgendes
beachten.
Jede K-Kombination ohne Wiederholung liefert eine Teilmenge der Zahlen
von 1 bis n, nämlich die Teilmenge, die gerade aus den Elementen a1
bis ak besteht.
Hat man umgekehrt irgendeine k-elementige Teilmenge der Zahlen von 1
bis n, so kann man die Elemente dieser Teilmenge, die ja alle
verschieden voneinander sind, der Größe nach sortieren.
Nennen wir das kleinste Element a1, das zweitkleinste a2 und so
weiter, so entsteht aus der k-elementigen Teilmenge genau eine K
-Kombination ohne Wiederholung.
Aus diesem Grund ist die Anzahl der K-Kombination ohne Wiederholung
der Zahlen von 1 bis n gleich der Anzahl aller k-elementigen
Teilmengen dieser Menge und damit definitionsgemäß gleich dem
Binomialkoeffizienten n über k.
Was die Bestimmung der Anzahl der K-Kombination mit Wiederholung
betrifft, habe ich ein eigenes Video gemacht.
Der Vollständigkeit halber möchte ich aber eine schöne Idee auch hier
vorstellen.
Zur Erinnerung, die Anzahl der s-Kombinationen der Zahlen von 1 bis r
ist gleich r über s.
Man sieht, dass ich hier neue Symbole eingeführt habe.
Das ist aus didaktischen Gründen nötig.
Denn ich behaupte, dass die Anzahl der K-Kombinationen der Zahlen von
1 bis n mit Wiederholung gleich diesem Binomialkoeffizienten ist.
Man sieht also, dass im oberen Teil gegenüber den Kombinationen ohne
Wiederholung ein plus k minus 1 steht.
Warum ist das so?
Der Beweis ist nicht schwierig.
Wir starten mit einer beliebigen K-Kombination mit Wiederholung, die
ich mit a abkürze.
Es liegen also diese kleinen Gleichbeziehungen vor.
Die Beweisidee besteht darin, die Komponenten des Dupels
auseinanderzuziehen.
Genauer setzen wir b1 gleich a1 und b2 gleich a2 plus 1.
Dadurch ist b1 kleiner als b2.
Weiter setzen wir b3 gleich a3 plus 2 und damit ist b2 kleiner als b3.
So geht es weiter und zum Schluss setzen wir bk gleich ak plus k minus
1.
Das Schöne ist, dass wir ein neues K-Dupel erhalten haben, das ich
kurz b nenne und das die Komponenten b1 bis bk hat.
Ich habe also dem Dupel a in einer klar definierten Weise ein Dupel b
zugeordnet und diese Zuordnungsvorschrift, diese Abbildung auf der
Menge aller K-Kombinationen mit Wiederholung nenne ich f.
Das heißt b ist gleich f von a.
Da die bj strikt aufsteigende Zahlen sind, haben wir eine Kombination
ohne Wiederholung erhalten und da ak kleiner gleich n ist, ist bk als
ak plus k minus 1 kleiner gleich n plus k minus 1.
Wir haben also eine K-Kombination der Zahlen von 1 bis n plus k minus
1 ohne Wiederholung erhalten.
Die Abbildung f, die jeder K-Kombination der Zahlen von 1 bis n mit
Wiederholung eine K-Kombination der Zahlen von 1 bis n plus k minus 1
ohne Wiederholung zuordnet, ist injektiv, denn wenn wir mit einem
anderen K-Dupel gestartet wären, hätte sich unter der Abbildung f auch
ein anderes Dupel ergeben.
Die Abbildung f ist aber auch surjektiv, das heißt wir erhalten jede K
-Kombination der Zahlen von 1 bis n plus k minus 1 ohne Wiederholung,
denn wir können die Zuordnungsvorschrift, die allgemein die j
-Komponente des Dupels a in die j-Komponente des Dupels b überführt,
durch Auflösen dieser Gleichung nach aj auch umkehren.
Es gibt also genauso viele K-Kombinationen der Zahlen von 1 bis n mit
Wiederholung, wie es K-Kombinationen der Zahlen von 1 bis n plus k
minus 1 ohne Wiederholung gibt.
Die letzte Anzahl steht aber im Memo, wenn ich r gleich n plus k minus
1 und s gleich k setze und wir erhalten dieses Gleichheitszeichen, was
zu zeigen war.
Auf einer letzten Folie habe ich noch einmal zusammengefasst, was wir
erhalten haben und dieses Resultat nennt man oft die Grundformeln der
Kombinatorik.
Für die Anzahl der K-Permutationen mit bzw.
ohne Wiederholung und der K-Kombinationen mit bzw.
ohne Wiederholung gilt, in den Zeilen haben wir die Permutationen und
die Kombinationen und in den beiden Spalten die Möglichkeiten mit bzw.
ohne Wiederholung, wobei im zweiten Fall k kleiner gleich n sein muss.
Mit Hilfe der Multiplikationsregel haben wir diese beiden Anzahlen
erhalten, wobei n tief k das Produkt n mal n minus 1 und so weiter bis
n minus k minus 1 in Klammern ist.
Die K-Kombinationen ohne Wiederholung sind durch diesen
Binomialkoeffizienten gegeben und gerade haben wir diesen Ausdruck für
die Anzahl der K-Kombinationen mit Wiederholung erhalten.
Abschließend für jeden Fall noch ein kleines Beispiel.
Wie groß ist die Anzahl der Dreierausschüsse, die man aus sieben
Personen bilden kann?
Wir können die Personen gedanklich von 1 bis 7 nummerieren.
Ein Dreierausschuss ist dann eine dreielementige Teilmenge dieser
Zahlen, die wir auch als 3-Kombination der Zahlen von 1 bis 7
schreiben können.
Die gesuchte Anzahl ist also gleich 7 über 3 und damit gleich 35.
Im zweiten Beispiel ist nach der Anzahl verschiedener
Medaillenvergaben bei einem Feld mit 10 Läufern gefragt.
Wir nummerieren die Läufer gedanklich von 1 bis 10.
Die Nummer des Läufers, der als erster durchs Ziel geht, kommt auf die
erste Stelle eines Triples, eines Dreitupels.
Die Nummer des Zweitplatzierten auf die zweite Stelle und die des
Drittplatzierten auf die dritte Stelle.
Wir erhalten drei Permutationen ohne Wiederholung und die gesuchte
Anzahl ist 10 tief 3, also 10 mal 9 mal 8 und damit gleich 720.
Das dritte Beispiel betrifft den fünfmal hintereinander ausgeführten
Wurf mit einem Würfel.
Notiert man die Augenzahlen in zeitlicher Reihenfolge, so entstehen
fünf Permutationen der Zahlen von 1 bis 6 mit Wiederholung.
Die Anzahl der Tupel ist also gleich 6 hoch 5 und damit gleich 7776.
Zu guter Letzt, wie viele Einkaufskörbe kann man bilden, wenn man
insgesamt vier Artikel aus 10 möglichen Artikeln kauft.
Hier können wir die Einkaufskörbe als vier Kombinationen der Zahlen
von 1 bis 10 modellieren, wenn wir die Artikel gedanklich von 1 bis 10
durchnummerieren.
Die Anzahl der möglichen Einkaufskörbe ist dann dieser
Binomialkoeffizient und der ist gleich 715.
Damit sind wir am Ende dieses Videos angekommen.
Ich bedanke mich ganz herzlich fürs Zuschauen.
Für Hinweise und konstruktive Kritik bin ich wie immer dankbar.