Herzlich willkommen zu einem weiteren Video
im Rahmen von OER Stochastik zum Thema Kombinatorik.
In diesem Video lernen Sie die vierte kombinatorische Grundfigur
kennen, nämlich das Ziehen von Kugeln aus einer Urne
mit Zurücklegen ohne Beachtung der Reihenfolge.
In gewissem Sinne ist dies der schwierigste Fall.
Um für diesen vierten Fall eine allgemeingültige Formel herzuleiten,
ist es sinnvoll, das sogenannte äquivalente Kästchenmodell zu betrachten.
Am Ende des Videos verschaffen wir uns einen Überblick
über alle vier Fälle, das heißt über alle vier
kombinatorischen Grundfiguren.
Kommen wir also zum vierten Fall, dem Ziehen mit Zurücklegen
ohne die Reihenfolge zu beachten.
In einer Urne befinden sich n Kugeln, die durchnummeriert sind.
Es wird daraus k mal eine Kugel gezogen.
In einer Strichliste wird jeweils notiert, welche Kugel gezogen wurde.
Diese wird anschließend in die Urne zurück geworfen
und es wird gut durchgemischt.
Die Strichliste sorgt dafür, dass man später zwar weiß,
welche Kugeln gezogen wurden, aber nicht, wann diese gezogen wurden.
Die Frage ist nun, wie viele Möglichkeiten es gibt,
auf diese Weise Kugeln mit Zurücklegen und ohne Beachtung
der Reihenfolge zu ziehen.
Um die Anzahl der Möglichkeiten zu bestimmen,
lohnt es sich, zum äquivalenten Kästchenmodell
überzugehen. Diese Art von Modellen schauen wir uns im Folgenden an.
Die Ausgangslage klingt jeweils ähnlich wie im Urnenmodell.
Es werden k Objekte auf n Kästchen verteilt.
Wir stellen uns vor, dass diese Kästchen aufgereiht
nebeneinander stehen.
Die Objekte können durchnummeriert sein oder nicht.
Außerdem sind Mehrfachbelegungen der Kästchen erlaubt oder eben nicht.
Jeder dieser vier Fälle entspricht einem Fall im Urnenmodell.
Sind Mehrfachbelegungen der Kästchen erlaubt,
so entspricht dies gerade dem Ziehen mit Zurücklegen.
Wenn die Objekte nummeriert sind, so entspricht das dem Beachten
der Reihenfolge im Urnenmodell.
Wir wollen uns die Äquivalenz zwischen dem Urnenmodell
und dem zugehörigen Kästchenmodell klarmachen. Stellen wir uns dazu
eine Urne vor, aus der wir ohne Zurücklegen Kugeln ziehen.
Zuerst ziehen wir die zwei.
Da die erste Kugel eine zwei ist, tragen wir in unsere Tabelle
eine eins in die zweite Spalte ein.
Danach ziehen wir beispielsweise eine eins und tragen deshalb eine zwei
für die zweite Kugel in die erste Spalte ein.
Und so weiter.
Die Darstellung in der Tabelle entspricht dem Kästchen Modell.
Jede Spalte entspricht einem Kästchen.
Im zweiten Fall kann jede Kugel nur einmal gezogen werden.
Deshalb ist die Spalte, das heißt das Kästchen,
nach einer Eintragung bereits voll.
Es sind keine Mehrfachbelegungen erlaubt.
Wir interessieren uns für den vierten Fall,
für den wir bisher noch keine allgemeine Formel kennen.
Wir verteilen nun also k nicht nummerierte Objekte auf n Kästchen,
und zwar mit Mehrfachbelegung.
Alle Kombinationen, die sich dabei ergeben,
systematisch aufzuschreiben, ist praktisch unmöglich.
Schon bei relativ kleinen Werten von n und k.
Wir betrachten dafür nicht mehr Kästchen, sondern die Trennwände
zwischen den Kästchen.
Ganz links und ganz rechts benötigen wir keine Trennwand.
Durch das Umschreiben verlieren wir insbesondere
keine Information.
In einem zweiten Schritt schieben wir die Symbole zusammen,
schreiben Sie also ohne Zwischenräume direkt hintereinander.
Die neuen Symbole tragen immer noch dieselbe Information
wie die Kästchen am Anfang.
Zwei Objekte befinden sich im ersten Kästchen.
Das zweite Kästchen ist leer.
Damit haben wir das Problem umformuliert.
Wir haben immer noch k Objekte.
In unserer Darstellung sind es vier, und wir haben n-1 Trennstriche.
Bei uns sind es fünf.
Wie viele Möglichkeiten gibt es nun, die k Objekte
auf k+n-1 Stellplätze zu verteilen?
Auf jeden Stellplatz kann entweder ein Objekt
oder ein Trennstrich verteilt werden.
Sobald die Objekte ihre Plätze gefunden haben,
werden die übrigen Plätze mit Trennstrichen aufgefüllt.
Anders formuliert geht es um die Frage, wie viele verschiedene
k-elementige Teilmengen sich aus einer k+n-1
elementigen Menge auswählen lassen.
Dies entspricht jedoch gerade dem Ziehen mit Zurücklegen
ohne Beachtung der Reihenfolge aus n Kugeln.
Die Formel hierfür kennen wir schon.
In unserem konkreten Beispiel liefert sie neun über vier
und im Allgemeinen k+n-1 über k Möglichkeiten.
Natürlich könnte man auch zunächst die Trennstriche verteilen
und die Objekte würden die übrigen Plätze bekommen.
Damit ergibt sich die äquivalente Formel k+n-1 über n-1.
Betrachten wir noch ein Beispiel: Ein Getränkekasten
für zwölf Flaschen soll bestückt werden.
Natürlich ist uns egal, wo die Flaschen nachher im Kasten positioniert sind.
Es stehen 5 mögliche Getränke zur Auswahl und wir wollen genau 12 Flaschen kaufen.
Da wir aus den 5 möglichen Getränken 12 je eins wählen
und die Reihenfolge egal ist, ergibt sich nach obiger Formel 12+5-1
über 12, also insgesamt 1820 Möglichkeiten,
die Getränke zusammenzustellen.
Wir haben nun alle vier Fälle besprochen, ziehen mit und ohne Zurücklegen,
ziehen mit und ohne Beachten der Reihenfolge.
Hieraus ergeben sich vier verschiedene Kombinationen.
In diesem Video haben wir folgendes gelernt.
Den vierten Fall, also das Ziehen mit Zurücklegen,
ohne die Reihenfolge zu beachten.
Sie kennen nun die allgemeine Formel für diesen Fall.
Bei der Herleitung der Formel war das äquivalente Kästchenmodell
entscheidend. Aus den drei Videos zur Kombinatorik
kennen Sie nun alle vier kombinatorischen Grundfiguren.