Herzlich willkommen zu einem Video im Rahmen von OER Stochastik
zum Thema Kombinatorik.
In diesem Video wird es zunächst grundsätzlich um das
systematische Zählen gehen.
Sie werden ein Modell kennenlernen, in das die meisten Anwendungsfälle
überführt werden können.
Außerdem kümmern wir uns um die einfachste kombinatorische Grundfigur,
das Abzählen von sogenannten k-k-Permutationen
mit Wiederholung.
Widmen wir uns zuerst der Frage, wie wir die Anzahl verschiedener Ausgänge
bei einem mehrstufigen Experiment systematisch abzählen können.
Dazu betrachten wir folgendes Beispiel.
Lara möchte ihren Kleiderschrank minimalisieren
und ein capsule wardrobe zusammenstellen.
Sie hat sich zunächst für zwei verschiedene Hosen,
drei Shirts und zwei Strickjacken entschieden.
Wie viele verschiedene Outfits kann Lara so kombinieren?
Es soll also die Anzahl verschiedener Kombinationen
bestimmt werden, wobei wir sicherstellen müssen,
dass wir auch wirklich alle möglichen verschiedenen Outfits mitgezählt haben.
Wir müssen also systematisch abzählen.
Um sicher zu gehen, dass wir auch alle Möglichkeiten betrachten,
können wir zunächst alle Outfits systematisch auflisten.
Hier bietet sich eine Baumstruktur an.
Wir wählen zunächst eine der beiden Hosen, dann können wir uns zu jeder Hose
für eines der drei Shirts entscheiden und schließlich
zu jeder dieser Hose Shirt Kombination.
Eine der beiden Strickjacken wählen.
Insgesamt sind demnach zwei mal drei mal zwei, also
zwölf verschiedene Outfits möglich.
Damit es im Capsule Waltrop nicht langweilig wird,
hat Lara noch zehn verschiedene Ketten und Schals zum Kombinieren ausgewählt.
Nun wird selbst die Darstellung im Baum schwierig.
Allgemein können wir dieses Vorgehen jedoch als
allgemeines Zählprinzip formulieren.
Wir betrachten allgemein ein Experiment, das aus einfachen,
voneinander unabhängigen Teilversuchen besteht. Im Beispiel
des minimalen Kleiderschranks wären es drei Teilversuche.
Die Auswahl einer Hose, die Auswahl eines Shirts
und die Auswahl einer Jackenvariante.
Nun zählen wir die Möglichkeiten in jedem Teilversuch.
m1 Mögliche Ergebnisse für Teilversuch eins, m2 mögliche Ergebnisse
für Teilversuch zwei, usw.
Das heißt, insgesamt erhalten wir m1 mal m2,
mal usw., mal im mk verschiedene Ausgänge des Gesamtexperiments.
Je nachdem, ob Wiederholungen zulässig sind oder nicht
und ob die Reihenfolge der Teilversuche eine Rolle spielt
erhält man verschiedene kombinatorische Grundfiguren.
Beim ersten Fall ist die Reihenfolge relevant und Wiederholungen sind erlaubt.
Beim zweiten Fall ist ebenfalls die Reihenfolge relevant,
aber Wiederholungen kommen nicht vor.
Beim dritten Fall ziehen wir ohne Beachtung der Reihenfolge
und ohne Wiederholung.
Und beim vierten Fall ziehen wir ebenfalls ohne Beachtung der Reihenfolge,
aber mit Wiederholung.
Je nach Kontext lassen sich auf der Grundlage
des allgemeinen Zählprinzips und dieser vier Unterscheidungen
verschiedene Formeln für die Anzahl der möglichen Ausgänge
eines Experiments herleiten.
Hier schauen wir uns zunächst den einfachsten Fall an,
das Ziehen mit Zurücklegen unter Beachtung der Reihenfolge.
Dies können wir uns allgemein in einem Experiment wie folgt vorstellen.
In einer Urne befinden sich n Kugeln, die von eins bis n durchnummeriert sind.
Es wird nun k mal eine Kugel gezogen.
Das Ergebnis wird jeweils notiert und die Kugel zurückgelegt
und gut durchgemischt.
Es stellt sich nun also die Frage, wie viele Möglichkeiten es gibt,
k Kugeln mit Zurücklegen unter Beachtung der Reihenfolge aus n Kugeln zu ziehen.
Um die Frage mithilfe des allgemeinen Zählprinzips zu beantworten,
betrachten wir beim Ziehen der Kugeln jeden Zug als einen Teilversuch,
insgesamt also k Teilversuche.
Da nach jedem Versuch die gezogene Kugel wieder zurückgelegt wird,
haben wir in jedem Zug gleich viele, also n Kugeln in der Urne.
Es gibt also n mögliche Ergebnisse in jedem der k Teilversuche.
Damit gibt es nach dem Fundamentalprinzip des Zählens insgesamt
n hoch k verschiedene Möglichkeiten, k Kugeln mit Zurücklegen
unter Beachtung der Reihenfolge zu ziehen.
Das können wir auch allgemein, ohne auf das obige Modell
zurückzugreifen wie folgt formulieren.
In einem Experiment mit k einfachen Teilversuchen
mit jeweils n möglichen Ergebnissen in jedem Teilversuch
gibt es n hoch k verschiedene Ausgänge des Gesamtexperiments.
Betrachten wir noch ein Beispiel.
Bei einem Zahlenschloss kann an vier Stellen
eine Zahl aus den Ziffern 0 bis 9 gewählt werden.
Wir fragen uns, wie viele verschiedene Codes
einstellbar sind.
An jedem Rädchen können wir also die Ziffern
0 bis 9 einstellen.
Das entspricht im Urnenmodell dem viermaligen Ziehen mit Zurücklegen
unter Beachtung der Reihenfolge.
Damit gibt es nach unserer Formel zehn hoch vier,
also 10.000 mögliche Codes, die eingestellt werden können.
Kommen wir damit zur Zusammenfassung.
Zunächst haben wir uns mit der allgemeinen Frage beschäftigt,
wie viele mögliche Ausgänge ein Experiment hat
und das sogenannte fundamentale Zählprinzip hergeleitet.
Dann haben wir die erste der kombinatorischen Grundfiguren, Ziehen
mit Zurücklegen unter Beachtung der Reihenfolge
aus dem Urnenmodell hergeleitet.
Und zum Schluss haben wir eine Formel für diesen ersten Fall hergeleitet.