Willkommen zur heutigen Vorlesung.
Ich habe nochmal die letzte Folie aufgelegt.
Das zweite Fundamentalprinzip des Zählens, wie es gern genannt wird,
oder Multiplikationsregel.
Wir werden sehr häufig Tupel bilden.
Und entscheidend ist, wie viele Möglichkeiten Sie für jeden einzelnen
Platz des Tupels haben.
Das sind Objekte aus einer Menge M.
Das Entscheidende ist eben hier, dass die Anzahl der Möglichkeiten
allgemein für das j-Element, die muss immer, die darf nur von j
abhängen, ganz egal, was Sie schon vorher getan haben.
Das ist das Entscheidende.
Ich hatte als Beispiel gemacht die Ziehung der Lottozahlen.
Für die erste Zahl haben Sie 49 Möglichkeiten.
Dann ganz egal, welche gekommen ist, das ist das Entscheidende.
Für die zweite noch 48 und so weiter und so multipliziert sich das.
Also das ist die Multiplikationsregel der Kombinatorik.
Ich möchte Ihnen hier ganz nebenbei ein paar Fragen stellen.
Nämlich erstens, wie viele Abbildungen gibt es von einer 4-elementigen
in eine 6-elementige Menge?
Ich kann das gleich verallgemeinern.
Wie viele Abbildungen gibt es von einer k-elementigen in eine n
-elementige Menge?
Und die gleiche Frage können wir uns stellen, wie viele injektive
Abbildungen gibt es von einer 4-elementigen in eine 6-elementige und
dann allgemein von einer k-elementigen in eine n-elementige Menge?
Ich behaupte, das ist eine simple Anwendung dieser
Multiplikationsregel.
Die erste Überlegung ist natürlich die, es kommt nicht darauf an, wie
konkret die Mengen aussehen.
Es kommt nur darauf an, dass sie vier beziehungsweise sechs Elemente
haben.
Ich kann also sagen, die Menge, auf der die Abbildung definiert ist,
hat vier Elemente.
Das ist die Menge der Zahlen von 1 bis 4.
Das andere ist die Menge der Zahlen von 1 bis 6.
Wodurch ist eine Abbildung bestimmt?
Eine Abbildung ist bestimmt dadurch, dass ich angebe, was ist f von 1,
der Funktionswert von 1, der Funktionswert von 2, der Funktionswert
von 3 und der Funktionswert von 4.
Das kann ich als Viertupel schreiben.
Für f von 1 habe ich, es soll in eine sechselementige Menge gehen,
sechs Möglichkeiten.
Für f von 2 habe ich auch sechs Möglichkeiten, keinerlei
Einschränkung.
Für f von 3 genauso und für f von 4 genauso.
Das heißt, die Anzahl der Möglichkeiten, Abbildungen zu bilden von
einer vierelementigen, einer sechselementigen Menge, ist nichts
anderes als 6 mal 6 mal 6 mal 6, also 6 hoch 4.
Das heißt, die Frage ist hier beantwortet, das sind dann 1296 Stück.
Das Entscheidende ist, die Abbildung ist eindeutig beschrieben durch
ein Viertupel.
Wenn Sie jetzt die gleiche Frage allgemein haben, eine k-elementige
Menge, sind es die Menge der Zahlen von 1 bis k, O, B, D, A.
Die n-elementige Menge sind die Zahlen von 1 bis n.
Die Abbildung ist bestimmt, indem Sie angeben, f von 1, f von 2, f von
3 usw.
bis f von k, das ist ein k-Tupel.
Für die erste Stelle haben Sie n Möglichkeiten, für die zweite haben
Sie n Möglichkeiten, keine Einschränkung.
Das heißt, insgesamt haben Sie n mal n mal n.
Wie viele Stellen Sie im Tupel haben, das sind k, also n hoch k.
Das heißt, diese zweite Frage, das ist das Allgemeine dann, das ist n
hoch k.
Wenn die Abbildung jetzt injektiv sein soll, das geht natürlich nur
dann, wenn k kleiner gleich n ist, oder in dem Fall haben wir
natürlich schon 4 kleiner gleich 6, das ist erfüllt.
Jetzt können Sie f von 1 zwar angeben, eine der Zahlen von 1 bis 6,
aber f von 2 darf nicht f von 1 sein.
Unabhängig davon, was Sie für f von 1 festgelegt haben, 6
Möglichkeiten, haben Sie nur noch 5 Möglichkeiten für f von 2, für die
zweite Stelle im Tupel.
Nur noch 4 Möglichkeiten für die dritte Stelle im Tupel und nur noch 3
Möglichkeiten für die vierte Stelle im Tupel.
Injektivität.
Das bedeutet, die Anzahl der injektiven Abbildungen hier ist nichts
anderes als 6 mal 5 mal 4 mal 3 und das sind 360.
Sie sehen also, die Zahl ist deutlich kleiner.
Allgemein, wenn Sie jetzt eine k-elementige Menge haben, injektive
Abbildung in eine n-elementige, haben Sie natürlich für f von 1 die
erste Stelle im Tupel, n Möglichkeiten.
Ganz egal, was Sie da draufschreiben, nur noch n-1 für die zweite, nur
noch n-2 für die dritte.
Das heißt, Sie haben ein Produkt aus k-Faktoren, die absteigen.
Das bedeutet, diese Anzahl ist gegeben durch n mal n-1 und so weiter
mal und der letzte Faktor ist n-k-1 in Klammern.
Jetzt haben Sie k-Faktoren.
Der erste ist n-0, der zweite n-1.
Und das werden wir später auch gern abkürzen als ein n hoch k und dann
unterstreichen wir das k, um das abzukürzen.
Das kommt häufiger vor.
Sie sehen also, wie diese Multiplikationsregel sehr einfache
Anwendungen findet.
In dem Fall Abbildungen.
Wir werden uns später auch mit syrjektiven Abbildungen beschäftigen.
Das ist ein bisschen komplizierter, wie viele syrjektive Abbildungen
gibt es.
Aber hier die Abbildung ganz allgemein und auch die injektiven können
wir direkt mit der Multiplikationsregel bestimmen.
Okay, ich denke, das sollte kein größeres Problem gewesen sein.
Ich möchte dann eingehen auf zwei Grundbegriffe der Kombinatorik.
Das sind einmal Permutationen und einmal Kombinationen.
Wir starten mit Permutationen.
Wichtig ist, dass sowohl Permutationen als auch Kombinationen immer
Tupe sind.
Das ist die grundsätzliche Merkregel erstmal.
Ich habe eine n-elementige Menge, die wird später dann die Menge der
Zahlen von 1 bis n sein.
Man kann sie aber auch allgemein erstmal sehen.
Und jetzt bilde ich k-Tupe.
Sie sehen, es ist die gleiche Bildung, die wir hatten bei der
Multiplikationsregel.
Und ich setze nur voraus, dass alle die aj aus der Menge m sind, für
jedes j von 1 bis k.
Und das bekommt nur einen Namen.
Das heißt eine k-Permutation aus n mit Wiederholung.
Mit Wiederholung deshalb, dass sich ein Element, was ich an die erste
Stelle des Tupes setze, sich beliebig oft wiederholen kann.
Und an jeder anderen Stelle genauso.
Keinerlei Einschränkung.
Mit Wiederholung wird im Folgenden kurz abgekürzt mit m.w.
Und das ist die Abkürzung, also die Menge aller k-Permutationen aus
der Menge m.
Mit Wiederholung ist natürlich nichts anderes als das k-fache
kathesische Produkt.
In dem Fall ist es besonders einfach, die Menge aller k-Tupe mit
Elementen aus m.
Heißt, ist eben die Bezeichnung für die Menge aller k-Permutationen
mit Wiederholung.
Kennen Sie da ein Beispiel aus dem Alltagsleben, wo sowas vorkommt?
Solche Permutationen.
Wenn Sie zum Beispiel Fahrrad fahren, da gab es auch Zahlenschlösser.
Das sind also vier Stellen.
Jeweils die Ziffern von 0 bis 9, das ist die Menge m.
Und es kommt auf die Reihenfolge an.
Erste Stelle, zweite, dritte, vierte.
Dann haben Sie ein ganz einfaches Beispiel einer 4-Permutation aus der
Menge der Ziffern von 0 bis 9.
Das wäre eine Möglichkeit.
Wenn ich fordere, dass die Komponenten alle verschieden sind, das geht
natürlich nur dann, wenn das k kleiner gleich n ist, dann spricht man
von einer k-Permutation ohne Wiederholung.
Das ist also hier die Sprechweise.
k-Permutation aus m ohne Wiederholung, ohne Wiederholung kurz ow.
Und hierfür muss eben k kleiner gleich n gelten.
Sonst geht das nicht.
Ja, das ist also hier die Abkürzung.
Das ist die Menge aller dieser Tupel mit der Eigenschaft, alle sind
verschieden.
Das ist das typische Beispiel, wenn man die Ziehung der Lottozahlen
noch live übertragen sehen könnte, würde das genau passieren.
Also 6 Tupel ohne Wiederholung.
Die ursprüngliche Reihenfolge, in der die Zahlen gezogen werden, ist
ein typischer Fall.
Ja, das ist die Menge aller k-Permutationen.
Und die n-Permutationen aus m heißen kurz Permutationen.
Also die kennen Sie auf jeden Fall.
Das ist dann die sogenannte symmetrische Gruppe.
Da können Sie hintereinander schalten, können alle möglichen Dinge
betrachten.
Das können Sie aus der Linie ein All geben.
Also das sind nur Sprechweisen für Tupel, für bestimmte Tupel.
Die Grundmenge ist m mit und ohne Wiederholung.
Das sind die Permutationen.
So, die Kombinationen, das ist das Entscheidende.
Diese Kombinationen sind auch Tupel.
Und zwar, hier ist es so, dass die Menge m geordnet sein muss durch
eine Relation.
Denken Sie sich immer eine Menge von Zahlen.
Es werden dann meistens die Zahlen sein von 1 bis n.
Bei einer Menge von Zahlen ist es immer die ganz natürliche Anordnung
der Zahlen.
Das kleiner gleich, das stellen Sie sich einfach darunter vor.
So, jetzt betrachten wir wieder K-Tupel.
Aber das Entscheidende ist, Sie haben jetzt diese Ordnungseigenschaft.
a1 kleiner gleich a2 usw.
kleiner gleich ak.
Das nennt man dann eine K-Kombination mit Wiederholung.
Wo sind uns diese Kombinationen schon mal begegnet?
Kann ja noch nicht lange her sein.
Denken Sie mal an die beiden Bilder mit den Würfeln.
Die sechs nicht unterscheidbaren Würfel.
Wie konnten wir das sichtbar machen?
Wir haben die Ergebnisse der Größe nach sortiert.
Da war kleiner gleich.
a1, das Ergebnis, kleinster Wert.
a2, zweikleinster Wert.
D.h.
diese Kombinationen kamen direkt schon in der allerersten Stunde vor.
Mit Wiederholung.
Also auch Tupel.
Kombinationen sind auch Tupel.
Aber hier habe ich das Entscheidende.
Es ist eine Ordnung drin.
Das ist die Kurzschreibweise hierzu.
Die Kombination mit Wiederholung.
Die Menge aller dieser Tupel mit der Eigenschaft, dass die a's
aufsteigend geordnet sind.
Wenn ich einen Tupel habe und jetzt habe ich eben striktes geordnet
sein.
Das bedeutet natürlich kleiner gleich aber nicht gleich.
Bei Zahlen ist es also die kleineren Nation.
Jetzt sind sie alle verschieden.
Und der Größe nach sortiert.
Dann spricht man von einer K-Kombination ohne Wiederholung.
Also insbesondere können die natürlich nicht gleich sein.
Also in dem Fall kürzt man das so ab.
Kommen.
N.
Oben M.
Ohne Wiederholung.
Also das kennen Sie natürlich auch.
Denn wenn Sie sich ansehen, was hier gemacht wird.
Das sind jetzt k verschiedene Objekte.
Aus einer n-elementigen Menge.
Das entspricht eindeutig einer Teilmenge.
Genau die Teilmenge, die die Elemente hat.
A1, A2 und so weiter bis AK.
Das ist eben hier eine eindeutige Zuordnung.
Solche Kombinationen ohne Wiederholung entsprechen Teilmengen.
Das wird zum Beispiel bei der Anzahlbestimmung, werden wir sehen, auf
Binomialkoeffizienten.
Also das ist die Menge der K-Kombination ohne Wiederholung.
Und wenn die Menge m, das ist also hier unser Hauptfall.
Die Menge der Zahlen von 1 bis n, so schreiben wir kurz.
Schreiben wir die Mächtigkeit klein n oben hin und nicht die Menge.
Und das dann genauso.
Das sind eben dann die Kombinationen mit und ohne Wiederholung.
Und die Permutation.
Da kommt natürlich dann der Zusatz ohne und mit Wiederholung noch
dazu.
Aber das ist die Kurzschreibweise, dass die Menge m ersetzt wird durch
die Mächtigkeit.
Okay, also das waren nur Sprechweisen.
Sie haben jetzt im Handout ein bisschen Platz, um Ergebnisse
einzutragen.
Nämlich jetzt kommen vier Grundformeln.
Von diesen Grundformeln müsste schon einiges dran gewesen sein im
ersten Studienjahr.
Das heißt, wir haben hier...
Sie sehen dort eine Vierfelder-Tafel.
Links sehen Sie k-Permutation und k-Kombination.
Und oben sehen Sie mit Wiederholung und Sie sehen ohne Wiederholung.
Ohne Wiederholung geht nur bei k kleiner gleich n.
Oben sehen Sie schon Memo, wie normal die Permutationen definiert
waren.
Einmal ohne Wiederholung und einmal mit Wiederholung.
Nun bei den k-Permutationen mit Wiederholung, das ist besonders
einfach.
Wir wenden direkt die Multiplikationsregel an.
Wir bilden ja k-Tupel.
Für die erste Stelle haben Sie n Möglichkeiten, für die zweite n
Möglichkeiten usw.
Es multipliziert sich.
Wir haben dann n hoch k Möglichkeiten.
Das heißt, das ist besonders einfach mit Wiederholung.
Und ohne Wiederholung haben wir auch gehabt.
Für die erste Stelle haben wir n Möglichkeiten, für die zweite n-1,
dann n-2 usw.
Und das war genau dieses absteigende Produkt mit k-Faktoren.
Und das hatte ich so bezeichnet und das ist so definiert.
Das Feld unten rechts ist auch besonders einfach.
Jetzt poppen oben die Kombinationen auf.
Jetzt sind die Permutationen durch die Kombinationen ersetzt.
Machen wir erstmal ohne Wiederholung.
Ohne Wiederholung ist ganz oben, kleiner.
Und ich sagte schon, das steht in eindeutiger Korrespondenz mit
Teilmengen.
Da sollten Sie gelernt haben im ersten Studienjahr.
Wenn Sie eine k-elementige Teilmenge bilden, einer n-elementigen
Menge, dann ist die Anzahl der Möglichkeiten dafür der
Binomialkoeffizient n über k.
Ganz allgemein, m über l.
Das können Sie mit Faktoren ausrechnen.
Mit Fakultäten meine ich natürlich.
0 Fakultät ist 1, ist also eine wichtige Definition.
Also interessant ist eigentlich nur das Letzte, was noch fehlt.
Und das war vielleicht auch nicht dran.
Ich will auch dort zwei Zugänge geben.
Den zweiten findet man auch sogar in Schulbüchern.
Das ist auch ein Binomialkoeffizient.
Jetzt steht da aber n plus k minus 1 über k.
Man sieht noch nicht, wieso das plus k minus 1 da oben reinkommt.
Man sieht natürlich, dass es mehr Kombinationen mit Wiederholung gibt
als ohne.
Also muss da schon was Größeres stehen.
Das ist auch größer.
Aber warum ist es gerade n plus k minus 1 über k?
Da gibt es einen sehr schönen Beweis.
Das ist nochmal das Memo für die Kombination ohne Wiederholung.
Sie sehen, ich habe dort neutrale Buchstaben eingeführt.
Nicht n und k, sondern r und s.
Weil ich das gleich allgemeiner brauche.
Das heißt, die Zahl ist bekannt.
Die Behauptung ist die, dass die Zahl der Kombinationen mit
Wiederholung, besonders deutlich gemacht, das soll sein, dass n, und
jetzt sehen Sie oben auch rot, plus k minus 1 über k.
Und die Idee ist hier ganz einfach die.
Also erster Zugang, der Beweis.
Ich betrachte eine Kombination mit Wiederholung.
Nennen wir sie mal a.
a steht für das Tupel mit den Komponenten a1 bis ak.
Und das Entscheidende ist, Kombinationen mit Wiederholung kann ich
abzählen.
Solche Tupel kenne ich, die Anzahl ist n über k.
Jetzt mache ich folgendes.
Aus diesem... Entschuldigung.
Das ist mit Wiederholung.
Die wollen wir gerade abzählen.
Ich will es darauf zurückführen, auf etwas, was wir kennen.
Da steht mit Wiederholung.
Das bedeutet, mit Wiederholung heißt, kleiner gleich ist zugelassen.
Das ist das Entscheidende, kleiner gleich.
Wir kennen aber jetzt die Anzahl für Kombinationen ohne Wiederholung.
Und die Frage ist, wenn wir dort nicht kleiner gleich hätten, sondern
kleiner hätten jeweils, sowas könnten wir abzählen.
Die Idee ist jetzt, ziehe, falls nötig, die Komponenten hier
auseinander.
Das, falls nötig, soll ich auch streichen.
Wir machen das ganz einfach mal.
Und wir setzen.
Die werden auseinandergezogen.
Ich setze mal ein b1 gleich a1.
Ich bilde ein neues Tupel.
b1 setze ich a1.
Das b2 setze ich aber a2 plus 1.
Durch diesen kleinen Trick habe ich erreicht, dass b1 kleiner als b2
wird.
Denn a1 war ja kleiner gleich a2.
Bei dem nächsten, das b3, setze ich mal an.
Jetzt als das a3 plus 2.
Und Sie sehen, dadurch, dass a2 kleiner gleich a3 war, ist jetzt b2
strikt kleiner als b3.
Auch hier bekomme ich ein echt Größer.
Das mache ich weiter.
Das letzte, das bk, ist dann ak plus k minus 1.
Das Entscheidende ist, ich habe jetzt ein neues Tupel bekommen.
Und zwar ein Tupel, ich nenne das mal b.
Das hat die Komponenten b1 bis bk.
Das habe ich mit einer ganz konkreten Zuordnungsvorschrift, einer
Abbildung bekommen aus dem ursprünglichen Tupel.
Nämlich mit der Abbildung, die drüber steht.
Erste Komponente bleibt, zweite plus eins, dritte plus zwei, vierte
plus drei und so weiter.
Ja, ich nenne das mal f von a.
Das ist meine Zuordnungsvorschrift.
Und was bekomme ich natürlich?
Nun, jetzt weiß ich, b1 ist größer gleich eins, kleiner als b2,
kleiner als b3 und so weiter, kleiner als bk.
Ich bekomme eine Kombination ohne Wiederholung.
Ja, aus welchen Zahlen?
Nun, ich weiß, das ak, was da steht, das war kleiner gleich n.
Das bedeutet, das bk ist ja ak plus k minus 1, ist kleiner gleich n
plus k minus 1.
Ich bekomme also eine Kombination ohne Wiederholung aus den Zahlen von
1 bis n plus k minus 1.
Eine k-Kombination.
So, und die Anzahl kann ich abzählen.
So, und das Schöne ist natürlich bei dieser Zuordnungsvorschrift, wenn
ich mit einem anderen a-Tupel starten würde, käme auch ein anderes b
-Tupel raus.
Die Abbildung ist offensichtlich injektiv.
Die Abbildung ist aber auch syjektiv und damit bijektiv, denn ich kann
sie umkehren.
Ich muss nur, wenn ich die b's habe, das ist ja die Gleichung für die
b's aus den a's, ich kann das nach aj auflösen.
Das heißt, wenn ich mit einem b-Tupel starte, dann bekomme ich auch
das a-Tupel über diese Gleichungsauflösung.
Ich habe eine bijektive Abbildung.
Wenn ich aber eine bijektive Abbildung habe, das war das erste
Fundamentalprinzip des Seelens, dann habe ich gleiche Mächtigkeit.
Endliche Mengen.
Also das bedeutet, die Anzahl der Kombinationen mit Wiederholung, n-K,
ist die Anzahl der Kombinationen ohne Wiederholung, aus den Zahlen von
n plus K minus 1.
Und die letzte Anzahl, die kenne ich, ohne Wiederholung, das ist
gerade das obere, n plus K minus 1 über K.
Das haben wir eben gehabt.
Und das ist eben eine Möglichkeit, das einzusehen.
Also über eine, ich nenne sie mal eine Auseinanderziehabbildung.
Einfacher Trick.
Wir werden den gleich auch nochmal verwenden.
Und die Zahl kennen wir, das ist gerade n plus K minus 1 über K.
Zweiter Zugang.
Alternative Herleitung.
Sie wissen, dass Binomialkoeffizienten eine Symmetrie aufweisen,
paskalsches Dreieck.
Das heißt, dieser Binomialkoeffizient ist nichts anderes als n plus K
minus 1 über n minus 1.
Wir werden jetzt sehen, dass wirklich dieser rechte
Binomialkoeffizient rauskommt, und zwar wie folgt.
Ich habe hier mal einige Kreise aufgemalt.
Ich mache folgendes, es seien insgesamt n plus K minus 1 Kreise.
Von diesen Kreisen markiere ich n minus 1 mit einem Strich.
Wir werden gleich sehen, was der Strich bedeutet.
Ich wähle ganz einfach hier n minus 1 aus von den n plus K minus 1.
Sie sehen sofort, da ich n minus 1 auswähle, aus denen ist eine
Teilmenge bilden.
Die Anzahl der Möglichkeiten ist genau das, was rechts oben steht, n
plus K minus 1 über n minus 1.
In diesem Bild, ich fange mal hier an, ich wähle das aus, ich wähle
das aus, wähle das aus und wähle das aus.
Das heißt, ich habe 4 ausgewählt, in diesem Bild ist also n gleich 5,
denn n minus 1 Striche habe ich gebildet, das sind 4, und K ist 7.
Wenn Sie nachzählen, ist K 7.
Ich behaupte, dass ich hier auch eine 7 Kombination habe, in
eindeutiger Weise, von insgesamt n Objekten, von 5 Objekten.
Warum?
Nun, ich interpretiere diese Striche als Trennstriche.
Ich schaue von links.
Wenn ich von links einen Kreis sehe, dann sage ich, das Objekt 1 ist
dabei.
Jetzt kommt der Trennstrich, die 1 ist nur einmal dabei.
Nach dem Trennstrich kommen jetzt die Zweien.
Sie sehen, es sind zwei Zweien dabei, denn danach kommt erst ein
Trennstrich.
Nach dem Trennstrich müssen die Dreien kommen.
Da kommt keine Drei, da kommt gleich wieder ein Trennstrich.
Nach dem Trennstrich müssen die Vieren kommen, das ist eine.
Danach kommt ein Trennstrich und danach kommen noch Fünfen, nämlich
zwei Fünfen.
Das heißt, dieses Bild, was Sie dort sehen, entspricht der Kombination
1, 2, 2, 4, 5, 5, 5.
Das ist eine Kombination mit Wiederholung aus den Zahlen von 1 bis 5,
eine 7 Kombination.
Sie können auch sagen, Sie haben einen Einkaufskorb gebildet, in dem
Sie ganz bestimmte Artikel gekauft haben.
Den Artikel 1 haben Sie einmal gekauft, den Artikel 2 haben Sie
zweimal gekauft, den Artikel 4 einmal und den Artikel 5 dreimal.
Das heißt, Sie können dort auch Einkaufskörbe beschreiben, wenn in
einem Laden insgesamt so und so viele Artikel drin sind und der
Einkaufskorb soll so und so viel enthalten.
Dann tauchen auch diese Kombinationen auf.
Das ist vielleicht noch nicht ganz klar geworden.
Ich mache mal noch ein anderes Beispiel.
Ich mache mal hier einen Strich, da einen Strich, da einen Strich und
da einen.
Das heißt, welcher Kombination entspricht das?
Sehen Sie, vom ersten Strich ist nichts, keine 1.
Dann kommt der Trennstrich, nach dem Trennstrich schauen sich die Zahl
der 2 an, dann kommt aber wieder gleich ein Trennstrich, keine 2.
Hier nach, müssten die 3en kommen, dann kommt sofort ein Trennstrich,
keine 3.
Jetzt kommen die 4en.
Eine 4, zwei 4, drei 4, dann kommt der Trennstrich und es bleiben noch
vier 5en über, das entspricht dieser Kombination.
Das findet man in Schulbüchern.
Das ist ein alternativer Zugang zu den Kombinationen mit Wiederholung.
Ja, einige Bemerkungen.
Die erste Bemerkung ist die, das hatte ich eben schon gesagt, n über k
ist die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge.
Erstes Studienjahr.
Es gibt hier eine wichtige Rekursionsformel für die
Binomialkoeffizienten, die sieht so aus.
Es mag sein, dass Sie die mal mit Induktion bewiesen haben.
Man kann es ja ausrechnen, mit Fakultäten ausrechnen.
Aber Sie bekommen keinen begrifflichen Zugang, vor allen Dingen können
sich die Formeln nicht merken oder schwer merken.
Wie kann man sich die Formeln leicht merken?
Gibt es einen begrifflichen Zugang, einen begrifflichen Beweis?
Und wenn wir auf die Zeile drüber schauen, dann heißt das ja, n plus 1
über k ist die Anzahl der Möglichkeiten, k-elementige Teilmengen zu
bilden einer n plus 1 elementigen Menge.
Nun sagen wir OBDA, die Menge der Zahlen von 1 bis n plus 1.
Es gibt für solche Teilmengen nur zwei Möglichkeiten.
Entweder Sie enthalten das Element n plus 1 nicht oder Sie enthalten
das Element n plus 1.
Das heißt, alle Teilmengen können Sie zerlegen.
Das Jungt der Zerlegung.
Wenn Sie das Element nicht enthalten, dann müssen Sie aus den anderen
n noch k-elementige Teilmengen bilden, das sind genau n über k.
Wenn Sie aber das Element n plus 1 enthalten, dann haben Sie schon ein
Element drin, dann müssen Sie aus den anderen n noch k minus 1
auswählen, das ist der zweite Summand.
Das ist der ganze Beweis.
Das heißt, hier brauchen Sie nichts ausrechnen mit Fakultäten.
Die Idee ist ganz einfach, die Zerlege, die Möglichkeiten, k
-elementige Teilmengen zu bilden aus einer n plus 1 elementigen Menge,
danach, ob Sie das Element n plus 1 enthalten oder nicht.
Ein sehr simpler Zugang.
Diese Rekursionsformel führt auf das Paskalsche Dreieck.
Haben Sie mal gehabt.
Man sieht hier diese Binomialkoeffizienten.
Und insbesondere, wenn Sie sowas haben, x plus y hoch n, Summe k von 0
bis n, n über k, mal x hoch k, mal y hoch n minus k, der sogenannte
binomische Leersatz, den haben Sie vielleicht auch mal bewiesen mit
Induktion.
Vermutlich mal.
Das ergibt ja auch einen begrifflichen Zugang.
Begrifflicher Beweis.
Ganz simpel.
Wie würden Sie das einem erklären in der achten Klasse?
Ich weiß nicht, wo eine Klammerrechnung vorkommt.
Sie würden sagen, x plus y hoch n heißt x plus y in Klammern, mal x
plus y in Klammern, mal x plus y in Klammern und so weiter, bis ich n
Faktoren habe.
Klammerrechnung bedeutet natürlich, ich muss sozusagen jedes mit jedem
multiplizieren.
Ich kann jetzt aus der ersten Klammer kann ich ein x auswählen, aus
der zweiten Klammer kann ich ein x auswählen, aus der dritten ein y,
aus der vierten wieder ein x, aus der fünften ein y.
Und dann kommt es nur darauf an, wie oft ich das x ausgewählt habe und
wie oft ich das y ausgewählt habe.
Insgesamt sind es n Faktoren.
Wenn ich das x aus k der Klammern ausgewählt habe und dann aus den
anderen n minus k Klammern das y, steht dann nichts anderes als x hoch
k mal y hoch n minus k.
Das taucht auf jeden Fall auf.
Ja, wie oft taucht das auf, dieses Produkt?
Das taucht genauso oft aus, wie ich eben aus den insgesamt n Klammern
k auswählen kann für die x.
Das sind n über k.
Aus den anderen wählen sie automatisch y aus.
Und natürlich haben sie hier die Möglichkeit, das x überhaupt nicht
auszuwählen, 0 einmal auszuwählen, zweimal auszuwählen und über die
Möglichkeiten wird summiert.
Das bedeutet, die binomische Formel, um sie einzusehen, muss man sie
nicht per Induktion beweisen.
Vor allen Dingen merkt man sich das viel leichter über n begrifflichen
Zugang.
Okay?
Schon fast n bisschen Fachdidaktik, was wir hier machen.
Ich mach jetzt mal n paar Beispiele.
Wir haben einfach in dieser Vorlesung auch Zeit für Beispiele, gerade
in der Kombinatorik.
Ich persönlich fand das auch immer schwer, als Student.
Und Zwillinge beim Lotto.
Es ist so n Phänomen, Zwillinge beim Lotto heißt, es können bei der
6er Kombination, die gezogen wird, dann auch benachtbarte Zahlen
auftreten.
Also sowas wie 17 oder 18.
Wie wahrscheinlich ist das?
Das heißt, hier ist die Grundmenge, die Menge der Kombination, der 6er
Kombination, der Zahlen von 1 bis 49, das ist das, was am Ende
mitgeteilt wird.
Da werden die noch der Größe nach sortiert.
Hier ist also die Information nicht mehr drin, in welcher Reihenfolge
die 6 Zahlen gezogen wurden, sondern wirklich nur noch, welche
Gewinnzahlen gezogen wurden.
So A sei das Ereignis, die Menge aller dieser A-Tupel mit der
Eigenschaft, es gibt mindestens ein I, mit der Eigenschaft Ai minus Ai
minus 1 gleich 1.
Und das heißt genau mindestens zwei direkt benachbarte Zahlen, also
ein Zwilling.
Das ist das Ereignis.
Wir wollen P von A bestimmen.
Wir nehmen an, jede Kombination wird mit gleicher Wahrscheinlichkeit
gezogen.
Alle Daten, die in Deutschland verfügbar sind, widersprechen nicht
dieser Annahme, dieser Hypothese.
Darüber kann man auch lange diskutieren.
Was ist die Wahrscheinlichkeit von A?
Nun, wenn die Gleichverteilung vorliegt, wissen wir Laplace-Modell,
Anzahl der günstigen Fälle durch Anzahl der möglichen Fälle.
Das heißt also hier muss ich die Anzahl der günstigen Fälle bestimmen
und hier ist es so, Sie sehen schon A oben C, Komplement.
Hier ist es viel leichter, die Wahrscheinlichkeit des komplementären
Ereignisses zu bestimmen und dann wissen wir, P von A ist 1 minus P
von A Komplement.
Warum ist das leichter?
Nun, was ist das Gegenteil von mindestens ein Zwilling?
Es könnten ja auch zwei Zwillinge sein oder drei.
Also wenn Sie das direkt angehen würden, müssten Sie vielleicht noch
Fälle unterscheiden.
Es würde wahnsinnig kompliziert.
Aber wenn Sie hier zum komplementären Ereignis übergehen und immer
wenn Sie hören mindestens, dann ist so ein Stichwort komplementäres
Ereignis ist vielleicht besser zu behandeln.
Nun, das ist kein Zwilling.
Das bedeutet, in dem Fall muss sein für jedes i von 2 bis 6 Ai minus
Ai minus 1 größer gleich 2.
Genau dann liegt kein Zwilling vor.
Und das Schöne ist, wir können hier wieder mit einer, in dem Fall
einer Komprimierungsabbildung, das Gegenteil von dieser
Auseinanderziehabbildung, können wir so eine Gewinnreihe, in der kein
Zwilling auftritt, behandeln.
Und wir setzen hier b1 gleich a1, die erste Zahl verändern wir nicht.
Das ist die kleinste.
Bei der zweitkleinsten, die ist ja um mindestens 2 größer als die
kleinste, ist ja kein Zwilling.
Da kann ich also durchaus noch einen subtrahieren.
Das bedeutet, ich bilde mal b2 als a2 minus 1.
Und b2 ist immer noch größer als b1.
Aufgrund der Bedingung drüber.
Ist ja kein Zwilling da.
Ich kann jetzt weitermachen.
Bei b3 kann ich sogar 2 subtrahieren.
Und b3 ist immer noch größer als b2.
Weil nämlich, dass a2 kleiner gleich a3 minus 2 war.
Und das ist die Bedingung.
Kein Zwilling.
Das heißt, hier komprimieren Sie die Reihe.
Und am Ende haben Sie noch b4, b5 ist a5 minus 4 und b6 ist a6 minus
5.
Sie haben jetzt immer noch eine Kombination, b1 kleiner als b2,
kleiner als b3 und so weiter, kleiner als b6.
Aber das b6, das kann höchstens noch 44 sein.
Nämlich a6 ist höchstens 49, minus 5 heißt höchstens 44.
Sie bekommen eine Kombination ohne Wiederholung aus den Zahlen von 1
bis 44.
Und offenbar haben Sie wieder eine injektive und eine surjektive
Abbildung.
Sie können es umkehren.
Gleiches Prinzip wie bei der Abbildung, die uns zwischen den
Kombinationen mit und ohne Wiederholung vermittelte.
Das heißt, wir haben hier eine Kombination ohne Wiederholung und die
Zuordnung ist bijektiv.
Das heißt, wir können sofort die Wahrscheinlichkeit von a Komplement
angeben.
Das ist hier der Vorteil.
Die Wahrscheinlichkeit von a ist dann 1 minus p von a Komplement,
unsere Regel für die komplementäre Wahrscheinlichkeit.
Und das ist 1 und Sie sehen, unten stehen alle Kombinationen, 49 über
6, Auswahl.
Und oben stehen jetzt die günstigen für a Komplement, 44 über 6.
Und wenn Sie das jetzt ausschreiben mit Faktoren, mit Fakultäten, dort
schön wegkürzen, dann kommt raus auf drei Stellen 0,495.
Das heißt, ziemlich genau im Schnitt bei jeder zweiten Ausspielung
tritt mindestens ein Zwilling auf.
Also kein Zwilling ist noch etwas wahrscheinlicher als mindestens ein
Zwilling.
Sie haben heute die Möglichkeit, im Internet sich alle Ausspielungen
runterzuladen.
Sie können also das in Excel einbinden, Sie können relative
Häufigkeiten bilden.
Die Möglichkeiten sind heute da und können mal sehen, ob das
vielleicht, das ist ja jetzt eine Prognose.
Wir arbeiten jetzt mit einem Modell.
Wir würden Wahrscheinlichkeiten interpretieren als Prognosen für
relative Häufigkeiten in lange Versuchsserien.
Wenn die bisher weit über 5000 Ausspielungen da war beim Lotto, haben
wir natürlich ein großes Arsenal von Versuchswiederholungen, ein
großes N.
Also das ist hier ein einfaches, aber instruktives Beispiel, dass eben
manchmal der Übergang zum Komplement dann wirklich sehr schnell zum
Ergebnis führt.
Zweites Beispiel, Kartenverteilung beim Skatspiel.
Nun Skatspiel, das wird ab und zu noch gespielt.
Damit das jetzt auch schön gendergerecht ist, habe ich sogar ein
kleines Video gedreht.
Das heißt, wer das nicht kennt, kann sich ansehen, wie dann auch rein
offiziell die Karten gegeben werden.
Aber das Entscheidende ist, es ist ein normales Kartenspiel mit 32
Blatt.
Bei diesem Blatt erhalten drei Spieler je zehn Karten und zwei Karten
kommen verdeckt auf den Tisch, ist der sogenannte Skat.
Die erste Frage, wir können das modellieren, die Modellierung der
verschiedenen möglichen Kartenverteilungen, der mögliche Grundraum.
K könnte ich natürlich ansetzen als Menge der Zahlen von 1 bis 32,
denn ich könnte jede Karte identifizieren.
Karo 7 ist vielleicht die richtige Nummer 1, Karo 8 die Nummer 2 und
so weiter.
Ich könnte natürlich sagen, okay, das sind eben alle Karos, alle
Herzen, alle Pik und alle Kreuz.
Das sind die Karten, die ich habe.
Entscheidend ist, dass es eine 32-elementige Menge ist.
Und jetzt kommt es darauf an, auf die Kartenverteilung.
Wie kann ich eine Kartenverteilung modellieren?
Denn wir wollen dann gleich Wahrscheinlichkeiten ausrechnen für
bestimmte Ereignisse.
Das ist eine Kartenverteilung.
Das Entscheidende ist hier Omega.
Ich muss nur wissen, ich muss die Spieler identifizieren.
Was bekommt Spieler 1?
Entscheidend ist nur die Menge der Karten.
Was bekommt Spieler 2?
Nur die Menge der Karten.
Was bekommt Spieler 3?
Nur die Menge seiner Karten.
Damit ist automatisch schon der Skat festgelegt.
Das ist der Rest.
Das bedeutet, diese Überlegung führt zu einem Ansatz, dass ich sage,
die Menge der Kartenverteilungen sind Triple.
K1 steht für die Menge der Karten von Spieler 1.
K2 für die Menge der Karten von Spieler 2.
Und K3 für die Menge der Karten von Spieler 3.
Das Entscheidende ist, jeder bekommt 10 Karten.
Die Mächtigkeiten sind alle 10.
Und die Vereinigung, die sollen paarweise disjunkt sein, sonst
schreibe ich kein Plus.
Die Vereinigung dieser 3 ist eine Teilmenge von K.
Dann habe ich eine 30-elementige Teilmenge.
Der Rest ist der Skat.
Aber dadurch ist alles festgelegt.
Der Skat ist redundant.
Ich könnte den zwar aufnehmen als eine vierte Komponente eines Tuples,
aber es würde keinerlei weitere Information bedeuten.
Sie sehen, das ist jetzt ein Akt der Modellierung.
Man kann da auch anders rangehen.
Das ist sozusagen für Sie ein Vorschlag.
Dem können Sie sich anschließen.
Sie können aber auch sagen, ich habe etwas Besseres.
Das Kj steht für die Menge der Karten von Spieler J.
Der Skat ist redundant, das habe ich gesagt.
Und jetzt kommt die Anzahl der Elemente.
Und was wir jetzt machen, ist nichts anderes als eine Anwendung der
Multiplikationsformel und von Grundregeln der Kombinatorik.
Ich besetze jetzt nach und nach die Stellen im Tuple.
Wie viele Möglichkeiten gibt es für K1?
K1 ist eine zehnelementige Teilmenge einer 32 elementigen Menge.
Wir wissen, das führt auf den Binomialkoeffizienten 32 über 10.
Jetzt, ganz egal, jetzt kommt der nächste Punkt, welche 10 Karten der
jetzt bekommen hat, ich habe noch 22.
Und davon erhält Spieler 2 10.
Das bedeutet, jetzt kommt die Multiplikationsregel mal 22 über 10.
Ganz egal, welche Kartenmengen die beiden Spieler bekommen haben, es
bleiben noch 12 Karten über.
Und davon bekommt Spieler 3 10 mal 12 über 10.
Jetzt sehen Sie, es bleibt noch der Skat über, aber der steht jetzt
fest.
Das heißt, die Anzahl der Kartenverteilungen, wenn ich sie so
modelliere, ist genau dieses Produkt.
So etwas bräuchten Sie auch in einer Klausur nicht weiter
auszurechnen.
Das Entscheidende ist, die Struktur muss verstanden worden sein, wir
haben also die Multiplikationsregel angewendet und wir mussten den
Binomialkoeffizienten haben als Teilmenge einer allgemein jetzt n
-elementigen Menge, in dem Fall einmal 32, 22, 12.
Jetzt machen wir die Laplace-Annahme.
Wir sagen, alle Kartenverteilungen sind gleichwahrscheinlich.
Es gibt hier interessante mathematische Arbeiten, wirklich nicht
trivial, wie oft man mischen muss, damit ungefähr die Gleichverteilung
vorliegt und wie man mischen muss.
Das kann man mit Markov-Ketten machen.
Sie haben zum Beispiel die Möglichkeit, auch eine Markov-Ketten
-Vorlesung zu hören.
Man muss ja auch ein bisschen Werbung machen für die Straßen.
Also, ein Ereignis.
Das Ereignis A, Spieler 1, erhält genau zwei Buben.
Wie kann ich das erstmal modellieren?
Ich muss es jetzt modellieren, das ist die Menge der Buben.
Das Ereignis A ist jetzt eine gewisse Menge von Kartenverteilungen.
Jetzt kommt die Eigenschaft.
Genau zwei Buben heißt, die Menge der Karten, die er bekommt,
geschnitten mit der Menge der Buben, soll genau zwei Elemente haben.
Das wäre jetzt mathematisch formalisiert.
Dieser Spieler erhält genau zwei Buben.
Sie sehen, das ist jetzt auch ein Akt des formalen Hinschreibens.
Wir wissen alle, was gemeint ist.
Nun, wir müssen jetzt die günstigen Fälle ausrechnen.
Jetzt wird es interessant.
Es kommt natürlich auch darauf an, welche Buben er bekommt.
Ich unterscheide ja.
Das bedeutet, ich muss erst aus den vier Buben zwei auswählen.
Die Anzahl der Möglichkeiten, die ich dafür habe, ist 4 über 2.
Wenn ich das gemacht habe, dann gebe ich ihm diese zwei Buben.
Jetzt hat er zwei.
Er soll aber genau zwei bekommen.
Jetzt muss ich also noch acht Karten auswählen für ihn.
Insgesamt bekommt er ja zehn.
Ja, aus den 28.
Wichtig ist, die beiden Buben, die er hat, die hat er schon, aber die
beiden anderen Buben dürfen ja nicht dabei sein.
Deshalb nur noch 28.
Das heißt, die restlichen Karten, die er bekommt, die Anzahl der
Möglichkeiten, sind 28 über 8.
So, jetzt ist es wieder völlig egal.
Spieler 2, es bleiben noch 22 über.
Er bekommt zehn.
Spieler 3, 12 über 10.
Das sind die günstigen Fälle.
Jetzt können wir den Quotienten bilden.
Das heißt, wir haben Anzahl der Elemente von A durch Anzahl der
Elemente von Omega.
Und jetzt können wir natürlich mit Fakultäten rechnen und ordentlich
was wegkürzen.
Wenn wir das machen, dann bleibt das über.
Hier können wir immer noch ordentlich was wegkürzen.
Und dann bleibt das über.
Und irgendwann muss man mal rechnen und dann bekommt man das.
Ich glaube, das lässt sich nicht weiter kürzen.
Entscheidend ist, es kommt raus 0,289 auf drei Stellen.
Also fast 30 Prozent ist die Wahrscheinlichkeit.
Man hätte ja vielleicht auch vorher mal schätzen können für sich.
Fast 30 Prozent, dass Spieler A genau zwei Buben bekommt.
Und das ist natürlich die gleiche Wahrscheinlichkeit aus
Symmetriegründen, dass Spieler B zwei Buben bekommt.
Und auch dass Spieler C zwei Buben bekommt.
Genau zwei Buben.
Jetzt ist die Frage, mit welcher Wahrscheinlichkeit bekommt denn
mindestens ein Spieler genau zwei Buben.
Und die Wahrscheinlichkeit ist natürlich jetzt wesentlich größer.
Mindestens ein Spieler genau zwei Buben.
Das ist natürlich hier, wenn das Ereignis AJ ist, Spieler J erhält
genau zwei Buben, müssen wir die Wahrscheinlichkeiten, das ist hier
wieder die Menge aller Kartenverteilungen, derart, dass die Menge der
Karten von Spieler J geschnitten, die Menge der Buben genau zwei
Elemente hat.
Gesucht ist jetzt die Wahrscheinlichkeit der Vereinigung.
Mindestens einer der Spieler hat genau zwei Buben.
So, wir haben eine Formel gehabt für die Vereinigung von allgemein
sogar N Ereignissen, aber für drei haben wir das beim letzten Mal ganz
explizit gemacht.
Und die Formel sagt, okay, die Wahrscheinlichkeit der Vereinigung ist
die Summe der einzelnen Wahrscheinlichkeiten, vermindert um die
Wahrscheinlichkeiten der Schnitte von jeweils zwei Ereignissen plus
die Wahrscheinlichkeit von allen dreien.
Nun, die letzte Wahrscheinlichkeit würde ja bedeuten, Spieler 1 hat
genau zwei Buben, Spieler 2 hat genau zwei Buben und Spieler 3 hat
genau zwei Buben.
Das geht nicht.
Das ist die leere Menge.
Das heißt, die letzte Wahrscheinlichkeit ist null.
Es sind ja nur vier Buben drin.
So, und aus Symmetriegründen, die Wahrscheinlichkeiten, die ersten
drei sind alle gleich.
Das ist also 3 mal p von h1.
Und die anderen Pärchen von 2 sind auch aus Symmetriegründen alle
gleich.
Das heißt, hier habe ich natürlich die Möglichkeiten aus 3, 2
auszuwählen.
Das ist das gleiche wie 3 über 2, 3 über 1.
Das ist das gleiche wie 3 über 1, das ist 3.
Minus 3 mal p von h1 geschnittenen h2.
Das bedeutet, ich muss nur noch bestimmen, was ist die
Wahrscheinlichkeit von h1 geschnittenen h2.
Spieler 1 genau zwei Buben und Spieler 2 genau zwei Buben.
Das andere habe ich schon ausgerechnet.
Das haben wir eben gemacht.
Also, ich gehe mal ran.
Günstige Fälle.
Ich brauche die günstigen Fälle.
Was sind die günstigen Fälle?
Ich baue das schon auf.
Spieler 1 soll zwei Buben bekommen.
Ich muss also aus den vier Buben erst mal zwei auswählen.
Die bekommt er jetzt.
Dann bekommt er aus den 28 Karten, das hatten wir eben auch, das sind
die Karten, die jetzt wirklich genau keine Buben sind, 8 Stück.
Jetzt kommt der Spieler 2 dran.
Spieler 2 bekommt natürlich jetzt die beiden Buben, die überbleiben,
die der 1 nicht bekommen hat.
Die soll ja er bekommen.
Und dann haben wir natürlich noch Karten, die er weiter bekommt.
Das Entscheidende ist, wie viele Karten sind draußen.
Es sind also 10 Karten draußen für den ersten Spieler.
Es sind aber jetzt auch die beiden Buben draußen.
Es sind 12 Karten draußen.
Das heißt, es sind nur noch 20 drin und von diesen 20 bekommt er 8.
Das heißt, es geht jetzt weiter mit 20 über 8.
Und beim letzten Spieler, da ist es wie gehabt, da bleiben jetzt noch
12 Karten über 10.
Dividiert durch alle Möglichkeiten, die habe ich nochmal drunter
geschrieben.
Hier kürzt man jetzt wieder weg und rechnet aus.
Und das Entscheidende ist, da kommt das raus und das ist ungefähr 0
,0563.
Jetzt bauen wir alles zusammen.
Das heißt, die Wahrscheinlichkeit der Vereinigung ist eben 3 mal das
minus 3 mal das.
Und da kommt raus das und das ist fast 70%.
0,608.
Das heißt eben wirklich ganz grob in 7 von 10 Spielen beim Skat.
Es ist so, dass mindestens ein Spieler genau zwei Buben hat.
Sie sehen also hier, was wir verknüpft haben.
Wir haben die Multiplikationsregel heftigst angewendet.
Wir hatten ja die Kombination ohne Wiederholung.
Wir mussten genau überlegen, wie wir das modellieren.
Und wir haben hier die Formel des Ein- und Ausschließens verwendet für
drei Ereignisse.
Ganz elementar.
Ja, ich möchte Ihnen hier ein weiteres Beispiel zeigen, bei dem ein
neuer, ganz interessanter Trick auftritt.
Es ist das sogenannte Stimmzettelproblem, ein berühmtes Problem im
Englischen, das Ballotproblem.
Und der Ausgangspunkt des Folgendes hat eine Wahl gegeben.
Zwei Kandidaten haben Stimmen bekommen.
Kandidat A, Kandidat B.
Der Kandidat A hat klein a Stimmen bekommen, der Kandidat B klein b
Stimmen.
Am Ende hat A gewonnen, A größer als B.
Das Entscheidende ist, jemand zählt die Stimmzettel sukzessive aus.
Erster Stimmzettel kann für A und für B sein.
Es soll keine Enthaltung geben, also auf jedem Stimmzettel stellen wir
A oder B.
Dann ist die Frage, wie groß ist die Wahrscheinlichkeit, dass A
während der gesamten Stimmauszählung in Führung ist.
Das ist zum Beispiel dann nicht der Fall, wenn schon der erste
Stimmzettel für B ausgegeben wird.
Ist auch dann nicht der Fall, wenn der erste für A ausgegeben wird und
der zweite für B.
Dann habe ich schon Gleichstand.
Also A führt, es hat wirklich echt führen.
Ab dem ersten Mal strickt mehr Zettel für A als für B.
Also notwendig ist, dass der erste Stimmzettel für A ausgegeben wird.
Wenn ich hier schon P schreibe, heißt das, ich muss mir Gedanken
machen über den Grundraum und ich muss natürlich eine
Verteilungsannahme machen.
Also ich muss erst mal beschreiben, was ist überhaupt so eine
Stimmauszählung.
Das muss ich modellieren.
Die kann ich folgendermaßen modellieren.
Sie sehen, hier läuft die Zeit.
Zeitpunkt 1 heißt, erster Stimmzettel wird ausgezählt und so weiter,
zweiter, dritter.
Auf dieser Achse läuft die Zeit.
Insgesamt werden also A plus B Stimmzettel ausgezählt.
Am Ende wird also dort A plus B erscheinen.
Und ich werde jetzt einen Weg malen.
Also hier geht zum Beispiel der erste Stimmzettel, blau heißt immer A.
Wenn A ausgezählt wird, geht es nach oben.
Wenn B ausgezählt wird, geht es runter.
Es entsteht ein Polygonzug.
So der muss natürlich am Ende enden in der Höhe A minus B.
Denn A mal ist er hochgegangen, A Stimmen für A.
B mal runter, B Stimmen für B.
Das bedeutet, ich könnte hier so einen Polygonzug zeichnen.
Und Sie sehen, das ist das Ende hier.
Es sind insgesamt fünf Stimmen für A ausgezählt worden und drei für B.
Das heißt, ich kann so einen Auszahlungsverlauf mir veranschaulichen
als so einen Weg in einem Koordinatensystem.
Machen wir noch einen zweiten.
Es könnte theoretisch auch zuerst runtergehen.
Zweimal sogar für B.
Dann müssen aber irgendwann auch die Stimmen für A kommen.
Das heißt, das könnte ein anderer Auszahlungsverlauf sein.
Dieser zweite ist offenbar ungünstig für das Ereignis.
Der erste ist ein günstiger Weg.
Ich muss offenbar hier Wege abzählen.
Günstige Wege.
Wie viele Wege sind günstig für das Ereignis?
Ich muss auch wissen, wie viele Wege es insgesamt gibt.
N sei kurz A plus B.
Das ist die Gesamtzahl der Zettel, die ausgezählt werden.
Und die Stimmauszählung könnte ich beschreiben als ein N-Tupel.
Ich nenne die Komponenten mal C1 bis Cn.
Ich habe schon betont, dass diese Tupel wichtig sind im Modellieren
von stochastischen Vorgängen, die über die Zeit ablaufen.
Das sind natürlich hier diskrete Zeitpunkte.
Zeitpunkt 1, erster Stimmzettel, Zeitpunkt 2, zweiter und so weiter.
In diesem Tupel kann ich sagen, A-Komponenten sind gleich 1.
Das heißt, immer hoch gehen auch.
Das sind die Stimmzettel für A.
Und B ist minus 1.
Sie sehen, diesen ersten Weg kann ich eindeutig beschreiben durch
dieses Tupel.
1, 1 heißt hoch, hoch, dann runter, hoch, hoch, runter, runter, hoch.
Den zweiten Weg durch ein anderes Tupel.
Also, das bedeutet, wenn ich die Wege jetzt so beschrieben habe,
könnte ich jetzt Omega ansetzen, rein formal.
Die Menge aller dieser N-Tupel und die Komponenten sind alle entweder
minus 1 oder 1.
Sie sind also aus einem einfachen kathesischen Produkt.
Der zweielementigen Menge minus 1, 1.
Jetzt kommt die Nebenbedingung.
Die Anzahl der Einsen in dem Tupel ist klein a und die Anzahl der
Minuseinsen ist klein b.
Das bedeutet, die Anzahl, Sie sehen Summe, Indikator, Variable, ich
schreibe das auch so.
Der Indikator ist 1, wenn cj gleich 1 ist und ansonsten 0.
Die Anzahl der Einsen im Tupel soll klein a sein und die Anzahl der
Minuseinsen im Tupel soll klein b sein.
Damit habe ich das Omega festgelegt.
So modelliere ich, es sei denn, Sie haben eine bessere Idee, solche
Stimmauszählungsverläufe als Tupel.
Wie viele Elemente hat Omega?
Das können wir sehr einfach abzählen.
Denn ich muss jetzt Tupel besetzen.
Ich weiß, ich muss ein N-Tupel besetzen, also ein a plus b Tupel.
Und von diesen Stellen muss ich genau klein a auswählen, wo ich Einsen
drauf packe.
Und auf die anderen packe ich automatisch Minuseinsen.
Das heißt, ich habe ein reines Auswahlproblem.
Ich muss aus einer n-elementigen Menge, also hier a plus b-elementigen
Menge, a Objekte auswählen.
Das sind die Stellen in dem Tupel und da muss ich Einsen
draufschreiben.
Das heißt, die Anzahl der Elemente von Omega ist einfach a plus b über
a.
Das ist erstmal wichtig.
Sehen, hier kommt wieder diese Teilmengeneigenschaft mit dem
Binomialkompetenzieren.
p sei die Gleichverteilung.
Ich nehme an, jede Reihenfolge der Stimmauszählung ist
gleichwahrscheinlich.
Und jetzt muss ich natürlich sehen, was sind die günstigen Fälle.
Die günstigen Fälle, ich schreibe das mal als Ereignis d, das sind
diejenigen Stimmauszählungsvorläufe mit folgender Eigenschaft.
Jetzt muss ich formal beschreiben, a liegt immer in Führung.
Für jedes k von 1 bis n-1 muss immer gelten c1 plus plus ck größer
gleich 1.
Also schon für k gleich 1 muss es gelten, der erste Stimmzettel muss
für a sein.
Aber auch c1 plus c2 muss größer gleich 1 sein.
Damit schließe ich aus, dass der zweite Stimmzettel für b ist.
Das geht nur, wenn beide für a sind.
Das heißt, da kommt dann 2 raus.
Dann, der dritte darf natürlich für b sein, dann ist a immer noch in
Führung.
Das bedeutet, c1 plus c2 plus c3 ist auch größer gleich 1.
Größer gleich 1 heißt immer, der Weg verläuft wirklich strikt oberhalb
der x-Achse.
So kann ich die günstigen Verläufe möglichst kompakt beschreiben.
Das ist jetzt die Kunst des Modellierens.
Ich gebe Ihnen hier nur Vorschläge.
Also das ist das Ereignis in Worten, a liegt immer in Führung.
Rein formal.
Jetzt will ich an das Problem ran.
Ich muss p von d haben.
Ich zerlege mal alle Auszählungsverläufe.
Das Omega wird zerlegt in drei paarweise sich ausschließende Mengen.
Wir werden sehen, dass wir damit sehr schnell zum Ziel kommen.
Nämlich, das Ereignis e sei, das Ereignis, der erste Stimmzettel ist
für b.
Das ist offenbar ungünstig.
Das heißt, der Weg geht nach unten.
Mehr schreibe ich nicht vor.
Nur der erste Schritt geht nach unten.
Gibt es jetzt noch Fälle, wo a nicht immer in Führung liegt?
Naja, das ist das Ereignis f.
Das sind alle Auszählungsverläufe mit der Eigenschaft, der erste
Zettel ist zwar für a, aber irgendwann trifft er wenigstens mal die x
-Achse.
Also c1++ck kleiner gleich 0.
Natürlich auf jeden Fall dann auch 0.
Das heißt, er liegt nicht immer in Führung.
So, und der dritte Fall, das war das a, das d da oben.
Und diese drei Ereignisse schließen sich paarweise aus und ergeben
alle Wege.
Jeder Weg hat eine von diesen drei Möglichkeiten.
Entweder a ist immer in Führung, das heißt hoch und strikt oberhalb
der x-Achse.
Oder erster Schritt schon nach unten, dann wird nichts weiter
festgelegt.
Oder erster Schritt nach oben, aber nicht strikt oberhalb der x-Achse,
sondern mindestens eine Nullstelle, mindestens ein Gleichstand.
Das heißt, das ist das Ereignis erster Zettel für a und a führt nicht
immer.
Stellen Sie sich vor, wenn der erste Stimmzettel schon für b ist,
schauen Sie sich das Ereignis e an.
Das wäre sozusagen so ein Weg.
Ich brauche gar nicht jetzt wissen, wie es weitergeht.
Das heißt, ich muss jetzt nur noch wissen, naja, ich sollte schon
wissen, wie viele Möglichkeiten gibt es weiterzugehen.
Und wie viele Wege gibt es, die zuerst runtergehen, und das ist jetzt
schon festgelegt, aber die jetzt vom Punkt 1-1 hochgehen, dort hinten
in diesen Punkt.
Da muss ich ja enden, denn ich weiß ja, so viele Zettel sind für a
abgegeben, klein a.
Das heißt, ich muss die Zahl der Wege finden von da unten da oben hin.
Und Sie sehen, ich habe jetzt noch a plus b minus 1 Zeitpunkte,
Zettel, a plus b minus 1, ein Zeitpunkt ist weg.
Wie viele Zettel habe ich noch?
Ich habe a einzeln, der Rest sind natürlich dann die minus 1, eine
habe ich da auch schon verbraten, aber das Entscheidende ist, um von
da nach da zu kommen, habe ich einen Weg, der genau a mal hochgeht,
und insgesamt habe ich a plus b minus 1 Zeitpunkte.
Das bedeutet, ich muss aus denen auswählen, a, und diese Zeitpunkte,
die ich dann im Tupel beschreiben kann, mit 1en belegen.
Das heißt, die Anzahl ist nichts anderes als a plus b minus 1 über a.
So viele Wege gibt es von da unten, vom Punkt 1-1 hoch, zum Punkt mit
den Koordinaten a plus b, a minus b.
Das heißt, das Ereignis, dessen Wahrscheinlichkeit kann ich sofort
angeben.
Interessant ist jetzt das, was noch fehlt, nämlich wenn ich jetzt auch
das Ereignis f noch im Griff hätte, dann würde ich natürlich die
Wahrscheinlichkeit von d genau ausrechnen können, denn p von Omega ist
1, ist p von d plus p von e plus p von f.
Das heißt, wenn ich die beiden Wahrscheinlichkeiten habe, habe ich
auch die Wahrscheinlichkeit von d.
Die will ich haben.
Der Trick ist jetzt der, ich betrachte mal einen Weg aus f.
Das heißt, der erste Zettel ist für a, und a führt nicht immer.
Das heißt, dieser Weg trifft irgendwann mal die x-Achse.
Da muss er wieder enden.
Das ist jetzt ein günstiger Weg für das Ereignis f.
Das Entscheidende ist bei diesem Weg, er geht erst hoch, aber dann
trifft er irgendwann mal die x-Achse, mindestens einmal.
Also trifft er die x-Achse auch, Prinzip des kleinsten Täters, zu
einem Zeitpunkt erstmalig.
In diesem Beispiel ist das dieser Zeitpunkt, da trifft er erstmalig
die x-Achse.
Ich ordne jetzt diesem Weg einen anderen zu, nämlich vom Startpunkt
spiegel ich diesen ersten Teil des Weges bis zum erstmaligen Erreichen
der x-Achse, erste Nullstelle, an der x-Achse.
Das heißt, dieser erste Teil wird verändert und ergibt den Teil.
So, Sie sehen, dass das eine injektive Zuordnung ist, denn
verschiedene Wege werden hierdurch auch verschieden abgebildet.
Und was ich hier halte, ist ein Weg, der, weil der eine hoch geht, der
geht im ersten Schritt runter.
Ich bekomme einen Weg aus E.
Das ist der Weg, der erst runter geht, dann hoch geht und natürlich am
Ende ist es der ganz normale Weg.
Diese Wege habe ich abgezählt.
Das Entscheidende ist hier, machen Sie sich das bitte klar, diese
Zuordnung ist bijektiv.
Das bedeutet, das ist ein sogenanntes Spiegelungsprinzip, was hier zum
Tragen kommt, die Anzahl der Elemente von diesem F ist gleich der
Anzahl der Elemente von E.
Das heißt, ich kann diese Gleichung fortsetzen.
Das heißt, E und F haben die gleiche Anzahl von Elementen und jetzt
kann ich die Wahrscheinlichkeit ausrechnen von D.
Das ist das Schöne.
Das bedeutet, wenn Sie sich die Gleichung ansehen, Omega ist D plus E
plus F, heißt das einfach, P von D ist P von Omega, ist 1, minus
zweimal die Wahrscheinlichkeit von E.
Denn wenn E und F gleiche Elementanzahl haben, sind die
Wahrscheinlichkeiten gleich.
Das bedeutet, das ist das Memo, das haben wir nachgewiesen, das wissen
wir auch.
Und wir wissen auch noch die Anzahl der Elemente von E.
Das haben wir auch.
Jetzt können wir rangehen und können sofort sagen, P von D ist 1 minus
P von D Komplement.
Und P von D Komplement setzt sich zusammen aus E und F.
Das 1 ist P von Omega.
Sie sehen, das ist die Anzahl der Elemente.
Aber F hat die gleiche Anzahl von Elementen wie E.
Also zweimal Anzahl der Elemente von E durch Anzahl der Elemente von
Omega.
Die Anzahl haben wir, ich setze ein, kürze weg und das bleibt über und
das kommt raus.
Ist also ein sehr einfaches Resultat in Abhängigkeit der Zahl der
Stimmzettel, die für A abgegeben wurden und die für B abgegeben
wurden.
Ich kann es auch geometrisch deuten.
Das, was Sie hier sehen, da hinten ist ja der Punkt mit den
Koordinaten A plus B und A minus B.
Und wenn Sie hier die beiden Punkte verbinden, bekommen Sie eine
Gerade.
Und die Steigung dieser Geraden ist genau die Wahrscheinlichkeit.
A minus B dividiert durch A plus B.
Das ist jetzt ein leicht zu merkendes Resultat.
Also das berühmte Stimmzettelproblem.
Es gibt da schon Tricks in der Kombinatorik.
Also gerade so bei Wegen, auch mal Spiegeln.
Das sind wichtige Abzählprinzipien.
Und auf der anderen Seite haben wir gesehen, dass wir diese Wege auch
durch Tupel modellieren können.
Und dafür möchte ich jetzt die Kombinatorik beenden.
Also mit diesen drei Beispielen.
Sie werden natürlich weitere Beispiele dann kennenlernen in den
Übungen und in den Tutorien.
Und möchte jetzt auf etwas kommen, was Sie auch schon vermutlich aus
der Schule kennen.
Nämlich das sind die Urnen und die Fächermodelle.
Ziehen mit und ohne zurücklegen und vielleicht noch allgemeiner.
So eine Urne ist natürlich hier in der Stochastik einfach nur ein
undurchsichtiges Gefäß.
Das kann sonst was sein, das Entscheidende ist, da sind dann meistens
Kugeln drin und die kann man ziehen.
Also möchte ich gleich ein Beispiel geben aus der Qualitätskontrolle,
ein typisches Beispiel.
Stellen Sie sich vor, eine Werkstatt kauft eine Sendung mit Schrauben,
10.000 Stück.
Und die Lieferfirma garantiert höchstens 5% dieser Schrauben.
Die halten eben gewisse Toleranz nicht ein, sind also im gewissen
Sinne unbrauchbar.
Vielleicht kann die Firma noch mehr garantieren, höchstens 1%, aber
das ist sozusagen eine Vorgabe.
Man kann natürlich hier eine Stichprobe ziehen.
Das Wort Stichprobe kommt vom Anstich des Hochofens.
Ist die Schmelze gut?
Stichprobe.
Das heißt man greift rein zufällig 30 raus, natürlich legt man die
nicht zurück.
Ich kann auch sagen mit einem Griff 30 oder nacheinander, ziehe 30,
ohne zurücklegen.
Ich könnte die Schachtel als Urne deuten, ziehe raus und unter diesen
30 finde ich 6 unbrauchbare.
Es soll die Sendung reklamiert werden.
So natürlich unter den 30 habe ich 20% unbrauchbare.
Die Lieferfirma sagt höchstens 5% und höchstens 5% von 10.000 sind
500, höchstens 500.
Ich kann natürlich sozusagen Pech haben.
Insofern, es könnte sein, in Wahrheit hat die gesamte Lieferung nur 6
unbrauchbare Schrauben.
Die sind in meiner Stichprobe durch Zufall.
Alles andere ist in Ordnung.
Kann passieren.
Man kann die Wahrscheinlichkeiten dafür ausrechnen.
Das heißt, Sie sehen, Sie müssen Entscheidungen unter Unsicherheit
treffen.
Also bevor Sie jetzt zurückschicken und reklamieren, nehmen Sie noch
eine weitere Stichprobe.
Das sind Fragen, mit denen sich dann vielleicht Leute im Betrieb
ausgesetzt sehen, in der Qualitätskontrolle.
Die Projektion soll ja auch vielleicht weitergehen.
Die Annahme, wir können sagen, 5% der gelieferten Schrauben, 500
Stück, halten die Toleranzen nicht ein.
Das wäre sozusagen das Maximale, was die Firma sagt.
Okay, 5% maximal, das sind die 500.
Jetzt könnte man die Wahrscheinlichkeit mal berechnen für das
Ereignis, dass unter diesen 30 rein zufällig gewählten Schrauben
mindestens 6 unbrauchbare sind.
Der mögliche Grundraum dafür, den können wir wieder ansetzen als
Permutation, indem wir jetzt folgendes machen, wir nummerieren die
Schrauben gedanklich durch.
Das heißt, selbst wenn irgendetwas erstmal nicht unterscheidbar ist,
können wir natürlich gedanklich auch unterscheidbar das Ganze machen.
Das heißt, wir können jetzt zum Beispiel sagen, wenn wir rein zufällig
ziehen, was ist die erste Schraube, die Nummer der ersten Schraube,
die Nummer der zweiten Schraube, rein gedanklich.
Das heißt, wir bilden hier Permutationen und zwar ohne Wiederholung.
N gleich 10.000, K gleich 30 und die Schrauben nummerieren wir durch.
Dann kann ich sagen, die erste Stelle im Tupel ist die Nummer der
zuerst gezogenen Schraube.
Also hier sehen Sie, kommen Sie wieder auf Tupel, wieder auf
Permutationen, obwohl das eigentliche Modell schon etwas ist, was wir
gleich mit einer Urne verbinden würden, und mit ziehen, in dem Fall
ist es eben ziehen ohne zurücklegen, denn wenn ich eine Schraube jetzt
geprüft habe, ich lege sie nicht wieder zurück.
Man sollte aber auch gleich erkennen, aus 10.000, 30 Schrauben ziehen
mit oder ohne zurücklegen, sollte vielleicht für Wahrscheinlichkeiten
nicht viel ausmachen, weil ich ganz viele Schrauben habe insgesamt und
sozusagen die Stichprobe einen sehr kleinen Anteil macht.
Das heißt, man kann dann manchmal sehen, wir werden später dann auf
Verteilung kommen, auf eine Binomialverteilung, auf eine
hypergeometrische Verteilung, wir werden dort dann sehen, dass eine
Verteilung vielleicht durch eine andere angenähert werden kann.
Urnmodelle.
Was gibt es für Modelle?
In einer Urne liegen gleichartige Kugeln, seien wir, wir seien
durchnummeriert von 1 bis N, also N-Kugeln.
Und wir können jetzt verschiedene Arten betrachten, Kugeln zu ziehen.
K-Kugeln sollen gezogen werden.
Wir können unter Beachtung der Reihenfolge ziehen.
Das heißt, unter Beachtung der Reihenfolge heißt jetzt, wir müssen
notieren, was ist die Nummer der ersten gezogenen Kugel, die Nummer
der zweiten und so weiter, bis wir unser K-Tupel haben, das ist
Beachtung der Reihenfolge.
Mit zurücklegen.
Das ist die erste Möglichkeit.
So, nach jedem Zug notieren wir die Kugelnummer und legen die Kugel
zurück.
Wenn A-J die Nummer der beim J-Mal gezogenen Kugel bezeichnet, dann
habe ich natürlich hier als Ergebnisraum die Permutation mit
Wiederholung.
K -Permutation der Zahlen von 1 bis N.
Das, ich ziehe K-Mal, das ist das Tupel aus den Nummern der Kugeln,
die gezogen werden.
Und wir haben hier das als einen kanonischen Ergebnisraum.
Wenn wir gedanklich, zumindest gedanklich, die Kugeln
durchnummerieren.
Also das wären die K-Permutationen mit Wiederholung.
Das gleiche können wir machen unter Beachtung der Reihenfolge.
Das heißt, wir betrachten wieder Permutation, aber jetzt ohne
zurücklegen.
Das geht natürlich nur bei K kleiner gleich N.
Wenn ich jetzt nicht zurücklege, muss ich dann höchstens so viele
Kugeln ziehen, wie ich dann Kugeln in der Urne habe.
Der geeignete Ergebnisraum sind natürlich die Permutationen dann
dementsprechend ohne Wiederholung.
Und die Interpretation von A-J ist die gleiche.
Das ist also weiterhin die Nummer der Kugel, die ich beim J-Mal ziehe.
Das heißt, solche Permutationen mit und ohne Wiederholung kommen
direkt beim Urnenmodell vor, wenn die Kugeln unterscheidbar sind.
Einmal mit Zurücklegen heißt Permutation mit Wiederholung.
Ohne Zurücklegen heißt ohne Wiederholung.
Das sind dann die K-Permutationen ohne Wiederholung.
Also das sind sozusagen zwei Urnenmodelle.
Sie sehen, dass natürlich, wenn ich die Reihenfolge beachten kann,
gibt es vielleicht auch die Möglichkeit, ich beachte die Reihenfolge
nicht.
Machen wir das mal, ohne Beachtung der Reihenfolge, mit Zurücklegen.
Wenn ich die Reihenfolge nicht beachte, dann weiß ich ja nicht, welche
Kugel ich beim ersten Mal gezogen habe.
Welche ich beim zweiten Mal gezogen habe.
Ich habe die Reihenfolge nicht beachtet.
Was kann ich überhaupt nur feststellen?
Wenn ich mit Zurücklegen ziehe, am Ende habe ich nur eine Information,
wie oft jede der N-Kugeln gezogen wurde.
Die Kugeln sind natürlich weiterhin nummeriert.
Wenn ich die Info nicht mehr habe, das heißt, irgendeiner im
Nachbarraum macht das.
Der notiert sich vielleicht wirklich die Nummer der Kugel beim ersten
Mal, die Nummer der Kugel beim zweiten Mal und so weiter beim dritten
Mal.
Und dann gibt er mir aber nur die Information, die Reihenfolge, die
teilt er mir nicht mit.
Dann kann er mir nur noch mitteilen, die Kugel Nummer 1 ist viermal
gekommen, Kugel Nummer 2 gar nicht, Kugel Nummer 3 ist dreimal
gekommen.
Das heißt, ich weiß jetzt, wie oft jede Kugel gezogen wurde.
Nur das, nur die Info habe ich.
Das ist wichtig, ohne Beachtung der Reihenfolge.
Der Ergebnisraum sind dann genau die Kombinationen mit Wiederholung.
Denken Sie an das Bild mit den sechs Würfeln, die jetzt nicht
unterscheidbar waren.
Das ist genau wieder das rechte Bild.
Ich sehe hier sozusagen das Ergebnis der kleinsten Augenzahl, zwei
kleinste und so weiter.
Das kann ich hinterher noch unterscheiden.
Das heißt hier ist jetzt, das sind die K-Kombinationen und die
Interpretation ist eben die, dass AJ ist die J-kleinste Nummer der
gezogenen Kugel.
Wenn das also losgehen würde, die Strupe mit 1, 1, 1 und dann 3, 3,
dann wüsste ich, dreimal ist die 1 gezogen worden, keinmal die 2,
zweimal die 3.
Das ist die Info, mehr habe ich nicht.
Okay?
Das muss man sich hier wirklich klar machen.
Wenn ich ohne Beachtung der Reihenfolge ziehe, jetzt ohne zurücklegen,
also das heißt die Kugel bleibt jetzt draußen, kann nicht
wiedergezogen werden, dann ist natürlich klar, es kommt jetzt auf die
Kombinationen an, zum Beispiel wie beim Lotto, K muss kleiner gleich N
sein.
Ich habe hier die Kombination ohne Wiederholung, also striktes Größer.
Jetzt habe ich wirklich eine Teilmenge vom Umfang K der N-elementigen
Menge der Kugelnummern.
Ich habe ja K verschiedene.
Wenn ich die Reihenfolge nicht mehr weiß, ist es wie beim Lotto.
Beim Lotto weiß ich vielleicht, wenn ich live das Ganze ansehen kann,
sehe ich in welcher Reihenfolge, aber am Ende, wenn mir nur mitgeteilt
wird, sozusagen wie oft, und es geht ja nur einmal, dadurch, dass ich
nicht zurücklege, kann jede Kugel nur einmal kommen, also habe ich
hier solche Kombinationen und das wäre mein geeigneter Ergebnisraum.
Wir sehen also diese vier Möglichkeiten, Permutation mit ohne
Wiederholung, Kombination mit ohne Wiederholung, kommen bei vier
verschiedenen Urnenziehmodellen vor.
Das Kapitel heißt jetzt nicht nur Urnenmodelle, sondern heißt auch
Fächermodelle.
Wir werden sehen, dass es begrifflich völlig gleichartig ist, aus
Urnenziehen oder Fächerbesetzen.
Manchmal ist man bei einem konkreten Problem auch näher bei einem
Fächermodell und manchmal ist man näher bei einem Urnenmodell.
Sie können zum Beispiel interpretieren, das Ergebnis eines
Würfelwurfs, eine der Zahlen von 1 bis 6, können Sie uminterpretieren
als sagen, ich besetze eines der Fächer mit den Nummern von 1 bis 6.
Jetzt ist begrifflich genau das gleiche.
Man muss es nur uminterpretieren.
Also, es werden k Teilchen verteilt auf n Fächer.
Die Fächer sind nummeriert von 1 bis n.
Wir betrachten erst die Möglichkeit, dass die Teilchen unterscheidbar
sind.
Wirklich unterscheidbare Teilchen.
Und ich darf Mehrfachbesetzung machen.
Das heißt, also theoretisch können beliebig viele Teilchen auch in ein
Fach fallen.
Keine neue Beschränkung.
Der geeignete Grundraum sind wieder die Permutationen.
Nämlich, ich sage einfach, aj ist die Nummer des Fachs, in dem das j
-Teilchen liegt.
Also, ich habe da das erste Teilchen, kommt vielleicht in Fach Nummer
5.
Das zweite Teilchen in Fach Nummer 8.
Das dritte Teilchen in Fach Nummer 5.
So baue ich meinen Tupel auf und schon habe ich eine Permutation mit
Wiederholung.
Das heißt, das ist also hier mit Wiederholung.
Unterscheidbare Teilchen, das bleibt dabei.
Keine Mehrfachbesetzung.
Das bedeutet, in jedem Fach darf höchstens ein Teilchen liegen.
Das bedeutet, ich kann zwar jetzt noch sagen, Nummer des Fachs wäre
das erste Teilchen, aber das zweite Teilchen muss in ein anderes Fach
fallen.
Ich bekomme Permutationen, aber jetzt ohne Wiederholung.
Nicht mit Wiederholung.
Das heißt, der geeignete Merkmalraum sind hier Permutationen ohne
Wiederholung.
Der dritte Fall, die Teilchen seien nicht unterscheidbar.
Das ist wichtig.
Ich lasse Mehrfachbesetzung zu.
Jetzt ist die Frage, was kann ich da überhaupt noch beobachten?
Da kann ich natürlich nur noch beobachten, Merkmalraum sind jetzt
Kombinationen.
Ich bekomme nur noch die Info, wie viele Teilchen sind in den
einzelnen Fächern.
Ich bekomme nur noch Besetzungszahlen.
Aber ich kann nicht mehr reden von Teilchen 1, Teilchen 2 oder das
Teilchen, was habe ich denn beim ersten Mal?
Wohin getan?
Die Info habe ich nicht mehr.
Das heißt, das ist so ein typisches Bild.
Sie sehen vier Fächer.
Insgesamt sind sechs Kugeln verteilt worden.
Ich kann nur noch solche Besetzungszahlen sehen.
Und das entspricht einer Kombination mit Wiederholung.
Sie sehen eine Kombination 1, 3, 3, 3, 4, 4.
Dieses Bild korrespondiert eindeutig mit dieser Kombination.
Der vierte Fall, der jetzt noch übrig bleibt, ist der, die Teilchen
sind nicht unterscheidbar, keine Mehrfachbesetzung.
So keine Mehrfachbesetzung heißt natürlich jetzt, es werden jetzt von
den N-Fächern...
K sollen besetzt werden, aber nur mit einem Teilchen.
Ich muss aus den N-Fächern K auswählen.
Ich komme auf die Kombination ohne Wiederholung oder gedanklich
gleichwertig Teilmengen.
Der geeignete Merkmalraum sind jetzt die Kombination ohne
Wiederholung.
Sie sollten zumindest wissen, diejenigen, die Physik machen, wird es
vielleicht besonders interessieren, diese Fächermodelle tauchen
insbesondere in der Physik auf.
Das heißt, die ersten, die Modelle 1, 3 und 4, gerade die in der
statistischen Physik, ich will das relativ schnell abhandeln, die
Teilchen sind dann sowas wie Gasmoleküle, Photonen, Elektronen,
Protonen, ähnliches.
Und der Phasenraum gibt es da, der wird in Zellen unterteilt und die
Zellen sind die Fächer.
Das heißt, einige kennen das wohl schon.
Und je nach Gleichverteilungsannahme ergeben sich verschiedene
Verteilungen.
In der Physik nennt man das dann Statistiken.
Es gibt zum Beispiel die Maxwell-Boltzmann-Statistik, alles
renommierte Physiker.
Modell 1 zum Beispiel, unter anderem bei Gasen, bei mittleren und
hohen Temperaturen.
Es gibt auch nach zwei anderen Physikern, Bose-Einstein-Statistik, das
Modell 3, unter anderem für Photonen und Helium-4-Kerne, habe ich mir
sagen lassen, und die Fermi-Dirac-Statistik, also auch zwei Physiker
Modell 4.
Und für Elektronen, Neutronen und Protonen, da taucht das auf.
Also Sie sehen, diese Fächermodelle tauchen unter anderem da auf.
Da hat man eben beim Modell 4 höchstens ein Teilchen in einer Zelle,
und das ist nach einem weiteren Physiker benannt, das ist das
sogenannte Pauli-Prinzip.
Das heißt also, wer sowas mal gesehen hat, da tauchen drei dieser vier
Modelle sofort auf, in der Statistischen Physik.
Ja, ich möchte, das hatte ich eben schon gesagt, aber hier nochmal auf
die begriffliche Äquivalenz eingehen zwischen Urnmodellen und
Fächermodellen.
Es ist wirklich total gleichwertig.
Und zwar, die begriffliche Gleichwertigkeit dieser beiden Modelle
kommt von daher, dass ich sagen kann, naja, wenn ich ein Teilchen lege
in das Fach Nummer J, ist das natürlich auch gleichbedeutend, ich kann
jetzt aus einer Urne ziehen eine Kugel mit der Nummer J.
Das bedeutet, ein Fach belegen ist das gleiche wie eine Kugel mit der
Nummer J ziehen.
Sie können auch sagen, statt eines Würfelwurfs könnten Sie eine Urne
nehmen, sechs Kugeln reintun, beschriften Sie mit 1 bis 6, ziehen rein
zufällig eine Kugel, stochastischer Form der gleiche wie in echten
Würfelwerfen.
Kugel Nummer J ziehen heißt, naja, ich besetze Fach Nummer J von sechs
Fächern.
Das gleiche.
Begrifflich gleichwertig.
So, wenn die Teilchen unterscheidbar sind, das heißt also in dem Fall,
wissen Sie, was ist das Teilchen 1, was ist das Teilchen 2, was ist
das Teilchen 3, was entspricht das bei den Fächermodellen?
Das ist genau die Reihenfolge.
Sie wissen also, welches Fach Sie als erstes besetzen, in welches Fach
Sie das erste Teilchen tun, das zweite Teilchen.
Das entspricht genau der Unterscheidbarkeit der Teilchen.
Und das mit Zurücklegen entspricht natürlich bei den Fächern, dass Sie
Fächer mehrfach besetzen dürfen.
Das ist eben mit Zurücklegen.
Sie können sozusagen auch eine Kugel mehrfach ziehen.
Wenn Sie das als Fachbelegung interpretieren, haben Sie mehrfach
Besetzung.
Das ist auch gleichwertig.
Das heißt, wenn Sie sich das einmal klar gemacht haben, dann ist es
bei konkreten Aufgabenstellungen, die Sie vielleicht später haben, es
gibt so klassische Aufgaben in der Schule mit Brötchen und Rosinen und
Teig und alles mögliche, ist die Frage, wollen Sie das jetzt
interpretieren mit Urnen oder mit Fächern?
Das eine ist vielleicht etwas näher an einem Fächermodell, aber für
Schülerinnen und Schüler sind das schon beides Abstraktionsstufen.
Also sowohl aus einer Urne ziehen als auch eben Fächer besetzen.
Wir wollen behandeln spezielle Urnen oder Teilchen oder Fächermodelle,
nämlich einmal Kollisionsprobleme, das machen wir gleich.
Insbesondere gibt es da das berühmte Geburtstagsproblem.
In anderer Einkleidung ist es das Phänomen der ersten Lotto
-Gewinnreihen -Wiederholung.
Wir werden uns auch beschäftigen mit dem sogenannten Zwei-Drittel
-Gesetz beim Roulette.
Das wird also in Roulette-Foren im Internet heftigst diskutiert und
daraus versucht man dann auch Gewinnstrategien abzuleiten.
Das ist besagt ganz grob.
Beim Roulette gibt es einen Kessel, das sind also die Zahlen von 0 bis
36, also 37 Zahlen.
Nehmen wir mal an, das ist alles rein zufällig.
Und dann passiert folgendes, wenn die Kugel 37 mal gefallen ist, dann
haben die Roulette-Spieler festgestellt, dass ungefähr zwei Drittel
aller 37 Zahlen aufgetreten sind, im Mittel.
Wir werden das alles präzisieren.
Also ungefähr 24, 25 verschiedene.
Warum ist das so?
Es sind ungefähr zwei Drittel von 37.
Ganz grob.
Das berühmte Zwei-Drittel-Gesetz.
Oder vollständige Serien, sogenannte Sammelbilder-Probleme.
Sammelalben.
Da gibt es eine berühmte italienische Firma, die macht das schon seit
Jahrzehnten.
Immer wieder.
Bundesliga, Fußball-Weltmeisterschaft, doppelte, dreifache Bilder.
Wann habe ich das Album voll?
Das leere Album sind Fächer.
570 Fächer bei der WM in Brasilien.
570 Fächer.
Kaufen Sie Tüten.
Sind fünf verschiedene.
Wenn Sie einkleben, haben Sie fünf Fächer besetzt.
Kommt das nächste Tütchen.
Sie können stochastische Annahmen machen.
Sie sehen, das sind sehr schulnahe und sehr schülernahe Probleme.
Also, machen wir mal das Paradoxon der ersten Kollision.
Der Ausgangspunkt war der, dass in den badischen Neuesten Nachrichten,
das ist hier die Lokalzeitung, stand auf der ersten Seite, das ist
jetzt länger her, eine Meldung, und das war die Meldung, erstmals im
Lotto dieselbe Zahlenreihe.
Die staatliche Lotto, Toto GmbH in Stuttgart, hat eine Lottosensation
gemeldet.
Es kam also auf Seite 1.
Und die Sensation bestand in Folgendem.
Zum ersten Mal in der 40-jährigen Geschichte des deutschen
Zahlenlottos, das war so grob 1995, wurden zwei identische
Gewinnreihen festgestellt.
Am 21.
Juni dieses Jahres kam im Lotto am Mittwoch, man sieht, damals gab es
auch schon das Mittwochslotto, in der Ziehung A, damals gab es zwei
Ziehungen, Ziehung A, Ziehung B, die Gewinnreihe 15, 25, 27, 30, 32,
48, es kommt gar nicht auf die konkrete Gewinnreihe an, aber genau
dieselben Zahlen wurden bei der 1628.
Ausspielung im Samstagslotto schon einmal gezogen, nämlich am 20.
Dezember 1986.
Und jetzt kommt das, welch ein Lottozufall, unter den 49 Zahlen sind
fast 14 Millionen verschiedene Sechserreihen möglich.
Meine Frau zeigte mir das und sagte, Mensch Norbert, du bist doch
Stochastiker, was sagst du denn dazu?
Da habe ich gedacht, ist das jetzt wirklich sensationell?
Natürlich ist es eben so, aber was war passiert?
Also erstmal könnte man sagen, okay, die Lottogesellschaft hat also
gesucht in der Vergangenheit, sie hat offenbar Mittwochslotto,
Samstagslotto zusammengepackt.
Und wenn ich das dann, ich habe das dann kurz durchgesagt, dann habe
ich gesagt, naja, was ist passiert?
In der 3016.
Ausspielung ist offenbar zum ersten Mal eine Gewinnreihenwiederholung
aufgetreten.
Das ist letztlich die Botschaft.
Erste Gewinnreihenwiederholung.
Ich habe natürlich sofort abstrahiert.
Ich habe gesagt, okay, ich kann jetzt Folgendes machen.
Ich deute das einfach als ein Fächermodell.
Was sind denn hier die Fächer?
Mir fiel gleich das Geburtstagsproblem ein.
Da werden wir gleich zu kommen.
Nun, was sind die Fächer?
Es gibt N fast 14 Millionen mögliche Gewinnreihen.
49 über 6.
13.983.816.
So viele.
Okay.
Gedanklich könnte ich die alle durchnummerieren.
Ich könnte sagen, okay, die erste Reihe ist die Reihe 1, 2, 3, 4, 5,
6.
Die hat genau die gleiche Wahrscheinlichkeit wie alle anderen.
Nur bitte nicht tippen.
Die tippen Zehntausende pro Woche.
Also wenn Sie da ein 6er haben, dann gibt es nichts.
Dann muss ich ja das teilen.
Also bitte die nicht tippen.
Dann mache ich das lexikografisch.
Hinten geht es jetzt hoch.
Die 7, die 8 usw.
Reihe Nummer 3.
Das kann ich machen, bis dann hinten die 49 steht.
Jetzt muss ich die 5 erhöhen.
Die nächste Reihe ist 1, 2, 3, 4, 6, 7.
Die nächste ist 1, 2, 3, 4, 6, 8.
Es geht also lexikografisch weiter.
Ganz am Ende habe ich dann die Reihe Nummer N.
N ist oben, fast 14 Millionen.
Das ist die Reihe 44, 45, 46, 47, 48, 49.
Das heißt, ich habe das gedeutet erstmal, als Lottoziehung fällt Ihnen
ein Fach.
Ich habe einen ganzen Haufen von Fächern, fast 14 Millionen.
Aber jede einzelne Ziehung, jede 6er Kombination kann ich
identifizieren und sie fällt Ihnen ein Fach.
Und das passiert sukzessive.
Rein zufällig werden Fächer besetzt.
Und zwar so lange, bis zum ersten Mal ein Teilchen, jetzt in Form
einer Lottoziehung, Lottokombination, in ein Fach fällt, was schon
belegt war.
Nichts anderes ist passiert.
Und wenn Sie das berühmte Geburtstagsproblem sehen, dann können Sie
sagen, wenn Sie von Schaltjahren absehen, Sie nummerieren die Tage des
Jahres durch von 1 bis 365.
Ich kann Sie sukzessive nach Ihren Geburtstagen fragen.
Und wenn Sie am 7.
Januar Geburtstag haben, fallen Sie in Fach Nummer 7.
Ich kann das auch so lange machen, sukzessive, bis ich das erste Fach
besetze, was schon mal besetzt ist.
Dann habe ich eben den Doppelgeburtstag.
Sie sehen, das sind nur zwei Spezialfälle von einer allgemeinen
Situation.
N Fächer, rein zufällig fallen Teilchen, sukzessive, unabhängig
voneinander.
Und dann habe ich die erste Kollision.
Kollision heißt, ein Fach, da will ein Teilchen rein, ist schon ein
Teilchen drin.
Das sollte man sich erstmal klar machen.
Hier haben wir einen ganzen Haufen von Fächern.
Rein zufällig, ich denke, das Wichtigste schaffen wir noch.
Was ist die Modellierung?
Xn, ich arbeite jetzt schon mit einer Zufallsverjahung.
Ich will hier gar keinen Grundraum angeben, aber Sie werden sofort
sehen, den Xn nenne ich den Zeitpunkt der ersten Kollision beim
sukzessiven, rein zufälligen Besetzen von N Fächern.
Und ich behaupte, wir können sofort die Wahrscheinlichkeit angeben,
erstmal, welche Werte Xn annimmt.
Theoretisch, das Schnellste, was passieren kann, ist, erstes Teilchen
fällt, zweites Teilchen fällt ins gleiche Fach.
Der Zeitpunkt ist frühestens zwei, wenn ich diskret zähle.
Der schlimmste Fall, der passieren kann, ist, die ersten N Teilchen
fallen alle in verschiedene Fächer, aber dann muss die erste Kollision
kommen.
Das heißt, die Werte, die das Xn annehmen kann, liegen zwischen 2 und
N plus 1.
Eine ganz simple Überlegung.
Jetzt kann ich auch sofort die Wahrscheinlichkeit angeben.
Das Ereignis, nämlich Xn größer gleich K plus 1, heißt, die erste
Kollision findet frühestens zum Zeitpunkt K plus 1 statt.
Das ist genau dann der Fall, wenn die ersten K Teilchen in
verschiedene Fächer fallen.
Genau dann tritt das Ereignis ein.
Dass sie in verschiedene Fächer fallen, die günstigen und die
möglichen Fälle, können wir sofort abzählen.
Das heißt, das passiert genau dann, wenn die ersten Teilchen in
verschiedene Fächer fallen.
Das heißt, die Wahrscheinlichkeit, jetzt kommen die günstigen Fälle,
für das erste Teilchen N, für das zweite N minus 1, für das dritte N
minus 2, und das baut sich auf, bis ich die K-Faktoren habe.
Die günstigen Fälle, die möglichen, für das erste N, für das zweite N,
für das dritte N, und das sind N hoch K.
Jetzt kann man einmal wegkürzen, ein N, und das andere kann man so
schreiben.
Und Sie sehen, wenn ich die Wahrscheinlichkeit habe, kann ich jetzt
mal zum Komplementären im Ereignis übergehen.
Das Komplementäre zu größer gleich K plus 1 ist kleiner gleich K.
Das kann ich machen für jedes K.
Und wenn ich das mache, dann habe ich als Ergebnis 1 minus.
Das ist die Wahrscheinlichkeit, kleiner gleich K.
Das heißt, die erste Kollision spätestens zum Zeitpunkt K.
Und das kann ich jetzt mal machen für das Lotto.
Da kommt das raus.
Und Sie können auch hier, das ist ungefähr 10,36.
Das heißt, das Ereignis ist nicht so unwahrscheinlich, ist nicht so
sensationell, wie die Lottogesellschaft gemeldet hat.
Und Sie können das auch hier die Wahrscheinlichkeit mal auftragen, in
Abhängigkeit von K, für diese Fächer.
Und Sie sehen, 1.500, 3.000 Ziehungen und so weiter.
Das ist die 1.
Für 2016 war es eben knapp 0,28.
Und so geht die Kurve hoch.
Das heißt, wenn zum Beispiel 9.000 Ziehungen gemacht werden, ist die
Wahrscheinlichkeit fast 1, dass die Gewinnreihenwiederholung erfolgt
ist.
Obwohl wir fast 14 Millionen Fächer haben.
Das ist also hier eine Botschaft.
Wir werden später noch auf andere Probleme eingehen.
Aber hier fragt ihr natürlich auch, wie ich das ausgerechnet habe.
Ich gehe da auch noch darauf ein.
Aber so sensationell, wie es gemeldet wurde, war es nicht.
Dankeschön.