Schlagwort: Rekursionsformel

Grundbegriffe der Wahrscheinlichkeitsrechnung: Binomialkoeffizienten, das Pascalsche Dreieck und der n-dimensionale Hyperwürfel

Binomialkoeffizienten und einige einfache Anwendungen in Abzählproblemen (wie die Anzahl der möglichen Ergebnisse beim Zahlenlotto) wurden bereits in den Begriffsbildungen der Kombinatorik vorgestellt. Hier werden die grundlegenden Eigenschaften der Binomialkoeffizienten diskutiert: die Pascalsche Rekursionsformel, der Aufbau des Pascalschen Dreiecks, der binomische Satz. Binomialkoeffizienten treten in unüberschaubar vielen Bereichen der Mathematik auf und ihr Auftreten sollte immer als Hinweis auf - mehr oder weniger offensichtliche - Querverbindungen verstanden werden. Als Beispiel einer dieser Querverbindungen wird der Zusammenhang der Binomialkoeffizienten mit dem n-dimensionalen Hyperwürfel diskutiert.

Spezielle Abzählprobleme: Partitionen

Das Abzählproblem, nicht unterscheidbare Kugeln auf nicht unterscheidbare Urnen zu verteilen ist äquivalent zum Problem zu einer ganzen Zahl Z Zerlegung in L Summanden zu finden. Eine derartige Zerlegung wird als Partition bezeichnet. Wie viele Partitionen es gibt, wird für mehrere Fälle untersucht: Die Vertauschung der Reihenfolge zählt (oder zählt nicht) als neue Partition, die Null ist als Summand zugelassen, die Länge der Partition wird nicht festgelegt. Man kann für diese Abzählprobleme zwar Rekursionsformeln angeben, man kann mit einfachen Mitteln aber keine expliziten Formeln angeben, die die Rekursionsformeln lösen.

Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars

Kombinationen mit Wiederholungen treten in mehreren Abzählproblemen auf, die zunächst sehr unterschiedlich wirken. Es wird ihre Äquivalenz gezeigt und die Formel hergeleitet, wie man die Anzahl aller Kombinationen mit Wiederholungen berechnet. Dazu verwendet man die Methode Stars and Bars. In den R-Skripten wird ein einfacher Algorithmus gezeigt, wie man die Menge alle Kombinationen mit Wiederholungen rekursiv berechnet.

Berechnung der Gewinn-Wahrscheinlichkeiten für das Zahlenspiel 3-5-11 und Durchführung von Simulationen mit Zufallszügen

Ein wichtiger Bestandteil des Monte-Carlo-Tree-Search-Algorithmus ist es, aus einer gegebenen Spielsituation zahlreiche Spiele auszuführen, bei denen die Züge zufällig ausgewählt werden. Die Ergebnisse dieser Simulationen bestimmen dann, wie der Algorithmus den Spielbaum weiter untersucht. Um besser nachvollziehen zu können, wie der Monte-Carlo-Tree-Search-Algorithmus den Spielbaum untersucht und für die möglichen Züge Gewinn-Wahrscheinlichkeiten schätzt, werden für das Zahlenspiel 3-5-11 die Formeln hergeleitet, wie man zu gegebenem Anfangswert die Gewinn-Wahrscheinlichkeit berechnen kann, wenn sämtliche Züge eines Spiels zufällig ausgewählt werden (mit jeweils gleicher Wahrscheinlichkeit). Ferner werden Simulationen mit unterschiedlichen Anzahlen von Spielen durchgeführt, um zu beurteilen, wie gut die Ergebnisse der Simulation mit den berechneten Gewinn-Wahrscheinlichkeiten übereinstimmen.

Lösung von Abzählproblemen durch Rekursion

Als weitere Methode zur Lösung von Abzählproblemen wird die Rekursion vorgestellt. Dies geschieht am Beispiel eines Zahlenspiels, für das der vollständige Spielbaum entwickelt wird. Dieser wirkt zwar sehr unregelmäßig und kann mit den bekannten kombinatorischen Formeln nicht bewältigt werden, aber aufgrund seiner rekursiven Struktur lassen sich Abzählprobleme auf das Aufstellen der Rekursionsformel und der Behandlung des Basisfalls zurückführen.