Herzlich willkommen zu einem weiteren Video
im Rahmen von OER Stochastik zur Kombinatorik.
In diesem Video befassen wir uns mit dem zweiten und dritten Fall
der vier kombinatorischen Grundfiguren, dem Ziehen ohne Zurücklegen
mit und ohne Beachtung der Reihenfolge.
Widmen wir uns zuerst dem zweiten Fall, dem Ziehen ohne Zurücklegen
mit Beachtung der Reihenfolge.
Unser Modell ist hierbei wie folgt gegeben.
In einer Urne befinden sich einen Kugeln mit den Nummern eins bis n.
Es wird daraus k mal eine Kugel gezogen und die Kugeln
werden der Reihe nach angeordnet.
Die Kugeln werden dabei nicht zurückgelegt.
Wir stellen uns die Frage, wie viele Möglichkeiten
es für die Ausgänge dieses Zufallsexperiment gibt.
Angenommen, es sind n unterscheidbare Kugeln in der Urne
und wir ziehen k mal aus der Urne.
Dann haben wir im ersten Zug genau n Möglichkeiten, eine Kugel zu ziehen.
Im zweiten Zug verbleiben noch n minus eins Möglichkeiten
eine Kugel zu ziehen, denn die erste Kugel wurde ja bereits zur Seite gelegt.
Im dritten Zug hätten wir noch n minus zwei Möglichkeiten.
Und so weiter.
Jedes Ergebnis im ersten Zug kann mit jedem
im zweiten Zug kombiniert werden, so dass sich insgesamt
das Produkt n mal n-1, mal ein n-2 mal n-k+1 ergibt.
Dies können wir schreiben als n Fakultät durch n-k Fakultät.
Allgemein gilt damit der folgende Satz.
Es gibt n Fakultät durch n-k Fakultät Möglichkeiten k Elemente
aus n unterscheidbaren Elementen ohne Zurücklegen
mit Beachtung der Reihenfolge zu ziehen.
Betrachten wir einige Beispiele.
Fünf gemischte Spielkarten werden nach und nach aufgedeckt
und in dieser Reihenfolge liegen gelassen.
Damit haben wir n gleich fünf Karten und k gleich fünf Ziehungen
ohne Zurücklegen mit Beachtung der Reihenfolge.
Damit ergeben sich fünf Fakultät durch 5-5 Fakultät
gleich 120 Möglichkeiten.
Beachten Sie hierbei, dass 0 Fakultät definitorisch gleich 1 ist.
In diesem Fall ist außerdem k gleich n, und wir nennen eine solche Ziehung
auch Permutation, da wir im Prinzip nur die Elemente
auf verschiedene Weisen anordnen, also permutieren.
Ein zweites Beispiel ist, dass k gleich vier Kinder
aus n gleich zehn durchnummerierten Losen aus einer Trommel
bei einer Tombola ziehen.
Wir erhalten damit zehn Fakultät durch zehn minus vier Fakultät,
gleich 5040 Möglichkeiten.
Ein drittes Beispiel: Aus sieben Spielsteinen,
die alle eine unterschiedliche Farbe haben,
werden drei gezogen.
Es ergeben sich damit 210 Möglichkeiten auf Basis des obigen Satzes.
Kommen wir nun zum dritten Fall, dem Ziehen ohne Zurücklegen,
ohne Beachtung der Reihenfolge.
Unser Modell ist nun wieder eine Urne mit n Kugeln mit den Nummern 1 bis n.
Es werden daraus k mal eine Kugel gezogen und in einer Strichliste
die Ergebnisse notiert.
Die Reihenfolge, in der die Kugeln gezogen werden,
ist nun jedoch im Gegensatz zum zweiten Fall irrelevant.
Wir stellen uns also wieder die Frage, wie viele Möglichkeiten es gibt,
k Kugeln ohne Zurücklegen und ohne Beachtung
der Reihenfolge zu ziehen.
Dazu unterscheiden wir zwei Schritte.
Wir berechnen die Anzahl der Ziehungen von k aus n Elementen ohne Zurücklegen,
aber mit Beachtung der Reihenfolge.
Dies haben wir bereits im zweiten Fall oben abgehandelt
und können auf unsere Formel n Fakultät durch n minus k Fakultät zurückgreifen.
Damit ergeben sich also n Fakultät durch n minus k Fakultät Möglichkeiten.
Da wir die Reihenfolge nicht beachten, müssen wir noch durch die Anzahl
der Permutationen von k Elementen, also k Fakultät teilen.
Dies liefert die Anzahl der Ziehungen, die sich nicht mehr
in der Reihenfolge unterscheiden.
Damit erhalten wir insgesamt n Fakultät durch k Fakultät mal n-k Fakultät.
Dies führt zur Definition des Binomialkoeffizienten.
Der Binomialkoeffizient n über k gibt die Anzahl der Ziehungen
von k Elementen aus n Elementen ohne Beachtung der Reihenfolge
und ohne Zurücklegen an.
Er ist für n größer oder gleich k definiert
als n Fakultät durch k Fakultät mal n-k Fakultät.
Da per Konvention null Fakultät gleich eins ist,
gilt n über null ist gleich eins.
Der Binomialkoeffizient ist symmetrisch, das heißt, dass n über k
gleich n über n minus k ist.
Allgemein gilt damit der folgende Satz: Es gibt n über k Möglichkeiten
k Elemente aus n unterscheidbaren Elementen
ohne Zurücklegen, ohne Beachtung der Reihenfolge zu ziehen.
Der Ausdruck Ende über k ist gleich n Fakultät durch k Fakultät
mal n-k Fakultät und heißt Binomialkoeffizient.
Betrachten wir nun ein detailliertes Beispiel.
Gegeben sei die Lottoziehung von sechs aus 49 nummerierten Kugeln in einer Urne.
Wir ziehen ohne Beachtung der Reihenfolge und ohne Zurücklegen.
Gesucht ist die Anzahl der Möglichkeiten, sechs aus 49 Kugeln
ohne Beachtung der Reihenfolge und ohne Zurücklegen zu ziehen.
Wir könnten jetzt einfach den Binomialkoeffizienten berechnen,
aber wir vollziehen die Schritte des obigen Beweises
noch einmal nach.
Zunächst ziehen wir gedanklich sechs aus 49 Kugeln ohne Zurücklegen,
jedoch mit Beachtung der Reihenfolge.
Dafür gibt es 10.068.437.520 Möglichkeiten,
was gerade 49 Fakultät durch 49-6 Fakultät entspricht.
In dieser Berechnung wird jedoch noch die Reihenfolge der Ziehung beachtet.
Wir müssen also die Ziehungen, die sich nur in der Reihenfolge
der Kugeln unterscheiden, miteinander identifizieren,
um auf die Lösung zu kommen.
Betrachten wir dazu den folgenden Einschub:
Wie viele Möglichkeiten gibt es, n Elemente anzuordnen?
Ziehen wir k gleich sechs Kugeln, so können wir diese auf sechs mal fünf
mal vier mal drei mal zwei mal eins gleich 720 Möglichkeiten anordnen.
Allgemein kann man also k unterscheidbare Elemente
auf k Fakultät verschiedene Weisen anordnen.
Aus dem Grund haben wir oben im Beweis im zweiten Schritt
auch durch k Fakultät geteilt.
Kommen wir zurück zur Lösung im Lotto.
Beispiel. Nach obigem Einschub gilt also, dass sich 720 Ziehungen
nur in der Reihenfolge unterscheiden, aber dieselben Kugeln beinhalten.
Beispielsweise sind die Ziehungen 13
12 44 48 3 7 und 48 3
7 13 12 44 identisch, wenn wir die Reihenfolge
der Kugeln nicht beachten.
Die Gesamtlösung ergibt sich damit wie folgt.
Im ersten Schritt berechnen wir die Anzahl k gleich sechs
aus n gleich 49 Kugeln, ohne Zurücklegen mit Beachtung der Reihenfolge zu ziehen.
Im zweiten Schritt teilen wir das obige Ergebnis
durch sechs Fakultät, also durch 720.
Und dies liefert gerade den Binomialkoeffizienten
49 Fakultät durch sechs Fakultät mal 49 minus 6 Fakultät.
Insgesamt ergeben sich somit 13.983.816 Möglichkeiten,
6 Kugeln aus 49 Kugeln ohne Zurücklegen und ohne Beachtung
der Reihenfolge zu ziehen.
Kommen wir damit zur Zusammenfassung.
In diesem Video haben Sie gelernt, wie viele Möglichkeiten
es gibt k Elemente ohne Zurücklegen und mit Beachtung der Reihenfolge
aus n unterscheidbaren Elementen zu ziehen, nämlich n Fakultät
durch n-k Fakultät.
Wie viele Möglichkeiten es gibt k Elemente ohne Zurücklegen
und ohne Beachtung der Reihenfolge aus n unterscheidbaren Elementen
zu ziehen, nämlich n über k, und in welchen Kontexten
beide kombinatorische Grundfiguren auftreten, sowie wie die Anzahl
der Möglichkeiten jeweils mathematisch hergeleitet wird.