Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme
    • Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik

Systematisch untersucht werden Abzählprobleme im nächsten Kapitel Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik.

Einführung

Abzählprobleme werden in der Kombinatorik systematisch untersucht; hier sollen lediglich einige Spezialfälle vorgestellt werden, um die Vorgehensweise zu demonstrieren.

Im Rahmen der Wahrscheinlichkeitsrechnung sind Abzählprobleme in folgendem Sinn relevant: Wenn man davon ausgehen kann – etwa aus Symmetriegründen –, dass gewisse Elementarereignisse gleich wahrscheinlich sind, kann man die Berechnung der Wahrscheinlichkeiten auf Abzählen zurückführen.

Nimmt man etwa an, dass ein Würfel perfekt symmetrisch geformt ist, sollte keine der sechs Seiten ausgezeichnet sein und bei langen Versuchsreihen sollte jede Seite mit gleicher relativer Häufigkeit erscheinen.

Man kann diese Vorgehensweise auf komplexe Ereignisse verallgemeinern. Ein Parade-Beispiel ist das Zahlenlotto 6 aus 49:

• Wie viele Möglichkeiten gibt es, einen Lottoschein auszufüllen?
• Wie viele Möglichkeiten gibt es etwa für die Ereignisse "genau 6 Richtige" oder "mindestens 3 Richtige"?

In den folgenden Beispielen sollen einfache Anwendungen besprochen werden, die aber zeigen werden, wie tückisch diese Abzählprobleme werden können.

Dabei soll aber auch klar werden, dass Abzählprobleme – sofern man sie geschickt formuliert – verallgemeinert und klassifiziert werden können, was gerade der Vorgehensweise der Kombinatorik entspricht.

Bei besonders schwierigen Problemen, bei denen keine aus der Kombinatorik bereitgestellte Formel zutrifft oder man nicht in der Lage ist, eine entsprechende Formel herzuleiten, kann man mit roher Gewalt vorgehen. Damit ist gemeint, dass man ein Abzählproblem in ein ein einfacheres Abzählproblem einbettet, indem man für die abzuzählende Menge eine Bedingung formuliert, die angibt, ob eine Realisierung des Zufallsexperimentes mitgezählt werden soll oder nicht. Wer programmieren kann, hat somit ein Abzählproblem darauf zurückgeführt:

• in einer Schleife alle Realisierungen einer umfassenderen Menge zu erzeugen,
• durch eine Bedingungs-Prüfung festzustellen, ob eine der gesuchten Realisierungen vorliegt.

Angewandt auf das Zahlenlotto 6 aus 49 würde dies bedeuten:

• man bildet alle Teilmengen der Zahlen von 1 bis 49 und
• zählt diejenigen Teilmengen, die genau 6 Elemente besitzen.

Dadurch erhält man die Zahl der Möglichkeiten, wie ein Lottoschein ausgefüllt werden kann.

Man sieht hier zweierlei:

1. Es sind nahezu keine Kenntnisse der Kombinatorik nötig.
2. Die Rechenzeit derartiger Programme kann leicht in unzumutbare Größenordnungen wachsen.

In den R-Skripten werden einige Beispiele gezeigt, wie man Abzählprobleme mit roher Gewalt löst.

Fakultät, fallende Faktorielle und Binomialkoeffizient

Bei den folgenden Abzählproblemen werden die Fakultät, die fallende Faktorielle und der Binomialkoeffizient benötigt.

Für eine natürliche Zahl n kann man die Fakultät (oder seltener: Faktorielle) entweder iterativ oder – gleichwertig – rekursiv definieren. In Abbildung 1 ist in Gleichung (1) die iterative Definition zu sehen: man multipliziert alle natürlichen Zahlen von n bis 1.

Gleichung (2) zeigt die rekursive Definition: jetzt wird die Definition der Fakultät auf die Berechnung einer anderen Fakultät zurückgeführt. Damit die Definition nicht unendlich oft in sich selbst eingesetzt werden muss, benötigt man eine Abbruch-Bedingung: dazu definiert man

1! = 1 und 0! = 1.

Letzteres ist zur Definition der Fakultät nicht nötig, aber bei vielen Formeln spart man sich die umständliche Beschreibung von Sonderfällen, wenn man 0! = 1 setzt.

Abbildung 1: Formeln zur Berechnung der Fakultät, der fallenden Faktoriellen und des Binomialkoeffizienten.

Werden von den n Faktoren in n! nur die ersten k Faktoren miteinander multipliziert, ensteht die fallende Faktorielle P(n, k), siehe Gleichung (3) in Abbildung 1. Da die zu n! fehlenden (n - k) Faktoren wiederum als Fakultät geschrieben werden können, kann P(n,k) auch wie in Gleichung (4) dargestellt werden.

Teilt man P(n, k) durch k!, entsteht der Binomialkoeffizient "k aus n" oder "n über k", siehe Gleichung (5). Schreibt man ihn nur mit Fakultäten, erhält man Gleichung (6).

Einfache Abzählprobleme beim Würfeln

Im Folgenden wird an einigen Beispielen gezeigt, wie man einfache Fragestellungen verallgemeinern kann.

Würfeln: einmal 6 bei 6 Würfen

1. Beispiel: einmal 6 bei 6 Würfen

Ein Würfel wird sechsmal nacheinander geworfen, wobei die Würfe unabhängig voneinander sind.

Wie viele mögliche Ausgänge hat das Zufallsexperiment?

Bei wie vielen Ausgängen erscheint genau eine 6?

Lösung:

Die Elementarereignisse für das zusammengesetzte Zufallsexperiment sind Zahlenfolgen der Länge 6, wobei jede Stelle mit einer Zahl von 1 bis 6 belegt werden kann:

(1; 1; 1; 1; 1; 1)
(1; 1; 1; 1; 1; 2)
 ... 
(1; 2; 3; 4; 5; 6)
(1; 2; 3; 4; 6; 6)
 ... 
(5; 6; 6; 6; 6; 6)
(6; 6; 6; 6; 6; 6)

Die Reihenfolge, in der die Möglichkeiten angegeben werden, ist unerheblich, wichtig ist ihre Anzahl. Aber es sollte klar sein – und dies gilt für alle Abzählprobleme –, dass eine geschickte Anordnung das Abzählen erleichtert.

Insgesamt gibt es

6 · 6 · 6 · 6 · 6 · 6 = 6⁶ = 46 656 Möglichkeiten,

da es für jede Stelle 6 Möglichkeiten gibt; und die Zahl, die an einer Stelle steht ist unabhängig davon, wie die anderen Stellen belegt sind.

Unabhängigkeit bedeutet, dass das Ergebnis eines Zufallsexperimentes nicht von der Ergebnissen vorangehender Experimente bestimmt wird – kurz: der Zufall hat kein Gedächtnis. Aufgrund der Unabhängigkeit werden die Möglichkeiten, die es für je eine Stelle gibt, miteinander multipliziert.

Fragt man jetzt nach den Möglichkeiten, bei denen genau einmal die 6 vorkommt, wird ähnlich abgezählt:

• Die 6 kann beim ersten Wurf eintreten, dann müssen alle anderen Ergebnisse ungleich 6 sein.
• Die 6 kann beim zweiten Wurf eintreten und alle anderen Ergebnisse sind ungleich 6,
• und so weiter

Man erhält insgesamt

1 · 5 · 5 · 5 · 5 · 5 + 5 · 1 · 5 · 5 · 5 · 5 + ... + 5 · 5 · 5 · 5 · 5 · 1 = 6 · 5⁵ = 18 750 Möglichkeiten.

Verallgemeinerungen

Es sollte klar sein, dass im letzten Beispiel die Zahl 6 in zwei verschiedenen Rollen auftritt:

• einerseits als die Anzahl der Elementarereignisse (die 6 Seiten des Würfels),
• andererseits als die Länge der Versuchsreihe (oder der Anzahl der Wiederholungen des Zufallsexperimentes).

Dass die Länge der Versuchsreihe gerade mit der Anzahl der Elementarereignisse übereinstimmt, sorgt dafür, dass man im Mittel eine 6 pro Versuchsreihe erwartet.

Man kann dieses Beispiel in mehrere Richtungen verallgemeinern:

1. Man kann danach fragen, wie viele Möglichkeiten es gibt, wenn die 6 k-mal vorkommen soll, k = 0, 1, 2, ..., 6.
2. Oder: Wie viele Möglichkeiten gibt es dafür dass die 6 mindestens k-mal beziehungsweise höchstens k-mal vorkommt, k = 0, 1, 2, ..., 6.
3. Man kann die Anzahl N der Würfe verändern und dann die entsprechenden Fragen stellen:
   1. Wie viele Möglichkeiten es gibt, wenn die 6 bei N Würfen genau k-mal vorkommen soll, k = 0, 1, 2, ..., N.
   2. Wie viele Möglichkeiten gibt es dafür dass die 6 bei N Würfen mindestens k-mal beziehungsweise höchstens k-mal vorkommt, k = 0, 1, 2, ..., N.
4. Man kann nach bestimmten Mustern, etwa 123456, in den Zufallsfolgen suchen und fragen, wie viele Möglichkeiten es dafür gibt, dass das Muster genau k-mal (oder mindestens k-mal oder höchstens k-mal mal) vorkommt.
5. Man kann anstelle des Würfelns ein anderes Zufallsexperiment wählen, bei dem es nicht 6 sondern b gleichwahrscheinliche Elementarereignisse gibt.

Würfeln: k-mal 6 bei 6 Würfen

2. Beispiel: k-mal 6 bei 6 Würfen

Ein Würfel wird sechsmal nacheinander geworfen, wobei die Würfe unabhängig voneinander sind.

Bei wie vielen Ausgängen erscheint genau k-mal die 6, k = 0, 1, 2, ..., 6?

Lösung:

Für k = 1 wurde das Problem oben gelöst. Wie muss man diese Lösung abändern, wenn k variiert?

Man kann jetzt wie im 1. Beispiel ein bestimmtes k vorgeben und dann entsprechend Abzählen. Lässt sich das Abzählproblem auch für ein beliebiges k formulieren und lösen?

Wenn bei 6 Würfen k-mal die 6 erscheinen soll, dann werden k Stellen mit einer 6 belegt und die verbleibenden 6 - k Stellen mit einer Zahl ungleich 6; im einfachsten Fall erscheinen alle 6 in den ersten k Würfen und alle Ergebnisse ungleich 6 in den letzten 6 - k Würfen.

Dafür gibt es

1^k · 5^{6 - k} Möglichkeiten.

Jetzt muss man nur noch berücksichtigen, dass die Ergebnisse 6 nicht nur zu Beginn der Versuchsreihe auftreten können, sondern an beliebigen Stellen, das heißt man muss aus den 6 Stellen k Stellen auswählen, die mit einer 6 besetzt werden:

• Für die Auswahl der ersten Stelle hat man noch 6 Möglichkeiten,
• für die zweite 6 verbleiben noch 5 Möglichkeiten,
• ...
• für die k-te 6 bleiben noch 6 - k + 1 Möglichkeiten.

Wegen der Unabhängigkeit werden diese Möglichkeiten miteinander multipliziert. Da k Stellen zu besetzen sind, sind es insgesamt k Faktoren; sie ergeben

(6 - 0) · (6 - 1) · (6 - 2) · ... · (6 - k + 1) Möglichkeiten.

Dieses Produkt ist gerade die fallende Faktorielle P(6, k), die in Gleichung (3) in Abbildung 1 definiert wurde.

Aber wie gleich gezeigt wird, ist das Ergebnis noch nicht richtig.

Um den Fehler aufzuspüren, sollte man die letzten Aussage für spezielle Werte von k durchspielen – die Werte k = 0, k = 1 sind dazu wenig geeignet, sobald aber mehrere 6 vorkommen, wird der Fehler offensichtlich:

k = 0:

Es gibt keine Stelle für die 6 auszuwählen; alle 6 Stellen müssen mit Zahlen ungleich 6 belegt werden:

5⁶ = 15625 Möglichkeiten.

k = 1:

Eine Stelle wird mit 6 belegt, 5 Stellen mit Zahlen ungleich 6. Für die 6 gibt es 6 Möglichkeiten, wo sie stehen kann; insgesamt gibt es

6 · 1 · 5⁵ = 18750 Möglichkeiten.

k = 2:

Zwei Stellen werden mit 6 belegt, 4 Stellen mit Zahlen ungleich 6.

Müssten die beiden 6 an den vorderen Stellen stehen, wären es

1 · 1 · 5 · 5 · 5 · 5 Möglichkeiten.

Da die beiden 6 an beliebigen Stellen stehen, benötigt man den zusätzlichen Faktor für die Auswahl der beiden Stellen. Verwendet man wie oben vorgeschlagen die fallende Faktorielle P(6, 2) = 6 · 5 = 30, dann gibt es

6 · 5 · 1 · 1 · 5 · 5 · 5 · 5 Möglichkeiten.

Doch ist das wirklich das richtige Ergebnis? Beschreibt die fallende Faktorielle P(6, 2) wirklich die Anzahl der Möglichkeiten, wie man 2 der 6 Stellen mit der 6 belegen kann?

Die Antwort ist Nein, denn die fallende Faktorielle P(6, 2) beschreibt, wie man 2 unterscheidbare Objekte auf 6 Positionen anordnen kann, wobei keine Position doppelt belegt werden darf. Sind die Objekte dagegen nicht unterscheidbar, zählt die fallende Faktorielle P(6, 2) diejenigen Anordnungen doppelt, bei denen nur die Objekte vertauscht werden.

Möchte man zwei unterscheidbare Objekte auf 6 Stellen verteilen (wobei keine Stelle doppelt besetzt werden soll), gibt es für das erste Objekt 6 Möglichkeiten, für das zweite Objekt noch 5 Möglichkeiten, insgesamt also 30 Möglichkeiten.

Bei nicht-unterscheidbaren Objekten fallen aber jeweils zwei dieser 30 Möglichkeiten zu einer zusammen, nämlich wenn die beiden Objekte nur vertauscht werden. Man erhält also nur 15 Möglichkeiten.

In Abbildung 2 wird der Unterschied zwischen unterscheidbaren Objekten und nicht-unterscheidbaren Objekten erklärt: Links sind zwei unterscheidbare Objekte zu sehen, die 6 Positionen einnehmen können. Für das erste Objekt stehen 6 Möglichkeiten zur Verfügung; da keine Position doppelt besetzt werden darf, bleiben für das zweite Objekt noch 5 Möglichkeiten. Es ergeben sich insgesamt 30 mögliche Anordnungen, die durch die fallende Faktorielle P(6, 2) = 6 · 5 richtig berechnet werden.

In der Abbildung sind von den 30 Möglichkeiten nur 4 dargestellt, wobei jeweils 2 nur durch Vertauschung der Objekte entstehen – da die Objekte unterscheidbar sind, müssen alle Anordnungen gezählt werden.

Rechts sind dagegen zwei nicht-unterscheidbare Objekte gezeigt, die ebenfalls die 6 Positionen einnehmen können. Man erkennt jetzt, dass die erste und die dritte sowie die zweite und vierte gezeigte Konfiguration identisch sind und nur einmal gezählt werden dürfen. Im Vergleich zur linken Seite fallen je zwei Konfigurationen zu einer Konfiguration zusammen, nämlich immer bei Vertauschung der Objekte. Es ergeben sich insgesamt nur 15 mögliche Anordnungen.

Abbildung 2: Links: Angedeutet sind die möglichen Anordnungen von 2 unterscheidbaren Objekten auf 6 Positionen, wobei keine Position doppelt besetzt werden darf. Es gibt 30 unterschiedliche Anordnungen. Rechts: dasselbe Problem für nicht-unterscheidbare Objekte. Jetzt sind jeweils 2 Anordnungen identisch und es gibt insgesamt nur 15 verschiedene Anordnungen.

Die eigentliche Frage war, wie viele Möglichkeiten es gibt, dass beim 6-maligen Würfeln genau zweimal 6 erscheint: Es sind

6 · 5 · 5⁴ / 2 = 15 · 5⁴ = 9375 Möglichkeiten.

k = 3:

Jetzt werden 3 Stellen mit einer 6 besetzt und 3 Stellen mit einer anderen Zahl. Für die Auswahl der 3 Stellen für die 6 liefert die fallende Faktorielle P(6, 3) = 6 · 5 · 4 = 120 wieder das falsche Ergebnis, da jetzt 3 nicht-unterscheidbare Objekte auf 6 Positionen verteilt werden. Die Anzahl der Möglichkeiten, wie oft die 3 Objekte untereinander ausgetauscht werden können, ist 3! = 6. Das heißt man muss die fallende Faktorielle P(6, 3) durch 6 teilen, um das richtige Ergebnis zu erhalten.

Jetzt sollte aber klar sein, wie die richtige Formel lautet, die angibt, wie viele Möglichkeiten es gibt, k 6er auf 6 Stellen zu verteilen: Die fallende Faktorielle P(6,k) muss durch k! geteilt werden, da k! Anordnungen nur durch Vertauschung entstehen. Wie aus den Formeln in Abbildung 1 zu sehen ist, erhält man dann gerade den Binomialkoeffizient "k aus n" (siehe Gleichung (5)).

Insgesamt erhält für die Anzahl der Möglichkeiten, bei 6 Würfen dreimal eine 6 zu Würfeln Gleichung (1) aus Abbildung 3 mit k = 3.

k = 6:

Jetzt sind alle Ergebnisse gleich 6, das heißt es gibt keine Wahlmöglichkeit: es existiert nur eine Realisierung für (6; 6; 6; 6; 6; 6).

Würde man dagegen von der Überlegung ausgehen, dass man für die erste 6 noch 6 mögliche Stellen zur Verfügung stehen, für die zweite 6 noch 5 Möglichkeiten und so weiter, dann würde man auf

6 · 5 · ... · 1 = 6! = 720 Möglichkeiten kommen.

Abbildung 3: Formeln zur Berechnung der Anzahl von Ereignissen beim Würfeln.

Zusammenfassung:

Der Fall k = 6 macht also besonders drastisch den Fehler deutlich, der oben angedeutet wurde.

Die Formel, die allgemein die Anzahl der Möglichkeiten dafür beschreibt, dass bei 6 Würfen k-mal eine 6 erscheint, ist als Gleichung (1) in Abbildung 3 zu sehen. In der nachfolgenden Tabelle der Abbildung werden diese Anzahlen für alle k = 0, 1, 2, ..., 6 berechnet.

Addiert man die Möglichkeiten auf, bei 6 Würfen k-mal die 6 zu erhalten (die Summe läuft also von k = 0 bis k = 6), ergibt sich 6⁶, siehe Gleichung (2) in Abbildung 3; dort ist auch gezeigt, wie die Summe mit dem binomischen Satz berechnet werden kann.

Würfeln: k-mal 6 bei N Würfen

3. Beispiel: k-mal 6 bei N Würfen

Wie viele Möglichkeiten gibt es bei N Würfen eines Würfels, dass genau k-mal die 6 erscheint, k = 0, 1, 2, ..., N.

Lösung:

Wie schon gesagt war in den bisherigen Beispielen die Anzahl der Würfe gerade gleich 6 gewählt, damit im Mittel eine 6 pro Versuchsreihe erscheint. Die 6 spielt folgende Doppelrolle:

• es gibt 6 Elementarereignisse und
• es wird 6-mal gewürfelt.

Die bisher entwickelten Formeln müssen also nur daraufhin untersucht werden, in welcher Rolle die 6 eingegangen ist.

Bei der Auswahl der k Stellen aus 6 möglichen Stellen, an denen die 6 eintritt, ist natürlich die Länge N der Versuchsreihe einzusetzen. Dagegen werden immer, wenn gesagt wird, dass es 5 Möglichkeiten dafür gibt, dass keine 6 eintritt, Elementarereignisse gezählt.

Die Verallgemeinerung von Gleichung (1) aus Abbildung 3 ist somit Gleichung (3).

Zufallsexperiment mit b Elementarereignissen

4. Beispiel: Zufallsexperiment mit b Elementarereignissen

Anstelle des Würfelns werde ein Zufallsexperiment betrachtet, bei dem es b gleichwahrscheinliche Elementarereignisse gibt. Wie viele Möglichkeiten gibt es bei N Ausführungen des Zufallsexperimentes, dass genau k-mal ein bestimmtes Ergebnis x erscheint, k = 0, 1, 2, ..., N.

Lösung:

Man muss sich nur wieder klar machen, an welcher Stelle in Formel (2) die Anzahl der Elementarereignisse eingeht. Man erhält Gleichung (4) in Abbildung 3.

Suche nach Mustern

Zuletzt soll ein Beispiel dafür vorgestellt werden, bei dem nach einem bestimmten Muster in einer Zufallsfolge gesucht wird und gezählt wird, wie oft das Muster in allen möglichen Realisierungen auftreten kann.

5. Beispiel: Suche nach Mustern

Ein Würfel wird wieder sechsmal geworfen und es sollen diejenigen Folgen gezählt werden, bei denen die 6 mindestens zweimal hintereinander vorkommt.

Lösung:

1. falscher Ansatz:

Man bildet Folgen wie in Gleichung (1) in Abbildung 4, bei denen an die Doppel-6 von vorne nach hinten durchgereicht wird; die anderen Stellen sind mit Zahlen ungleich 6 besetzt (der Strich über der 6 steht für das Komplement, also eine beliebige Zahl ungleich 6).

Dieser Ansatz ist falsch, da man jetzt nur diejenigen Ereignisse zählt, bei denen die 6 genau zweimal hintereinander vorkommt. Es fehlen Ereignisse, wo mehrere 6 hintereinander stehen; insgesamt werden zu wenige Ereignisse gezählt.

2. falscher Ansatz:

Gleichung (2) in Abbildung 4 versucht dies zu verbessern, indem jetzt wieder die Doppel-6 durchgereicht wird, aber an den anderen Stellen eine beliebige Zahl steht (die Bezeichnung ω soll andeuten, dass es sich um ein beliebiges Elementarereignis handelt).

Zählt man jetzt diese Kombinationen ab, erhält man immer noch das falsche Ergebnis, da etwa das Ereignis (6; 6; 6; 1; 1; 1) doppelt gezählt wird: Es kommt in der ersten und in der zweiten Folge in Gleichung (2) vor; insgesamt werden zu viele Ereignisse gezählt.

3. richtiger Ansatz:

Gleichung (3) in Abbildung 4 zeigt, wie man die Doppel-6 durchreichen muss, ohne einige Ereignisse doppelt zu zählen: Vor der Doppel-6 darf keine 6 stehen, nach der Doppel-6 steht eine beliebige Zahl.

Jetzt muss man nur noch die 5 Ereignisse aus Gleichung (3) abzählen, was in Abbildung 4 durchgeführt wird und 4651 ergibt.

Abbildung 4: Ansätze und Berechnung der Anzahl der Folgen mit mindestens zwei aufeinanderfolgenden 6 bei 6 Würfen.

R-Skripte: Abzählprobleme beim Würfeln

Die Problemstellung und die Berechnung mit Hilfe von brute force-Algorithmen

Im Theorieteil oben wurde gesagt, dass man bei schwierigen Abzählproblemen mit roher Gewalt (brute force) vorgehen kann. Dies soll nun an einfachen Beispiel demonstriert werden.

Beispiel:

Ein Laplace-Würfel wird 6 mal nacheinander geworfen.

• Wie viele mögliche Ergebnisse gibt es insgesamt?
• Bei wie vielen Ergebnissen tritt genau einmal eine 6 auf?
• Bei wie vielen Ergebnissen tritt genau k mal eine 6 auf, mit k = 0, 1, 2, ..., 6?

Die erste Frage ist so einfach, dass man sie sofort durch Abzählen beantworten kann:

Da es insgesamt 6 Möglichkeiten für das Ergebnis eines Wurfes gibt, gibt es insgesamt 6⁶ Möglichkeiten.

Auch die zweite Frage kann man leicht durch Abzählen beantworten. Dieses einfache Beispiel soll aber verwendet werden, um die Methode mit roher Gewalt zu erläutern.

Damit ist gemeint, dass man:

• alle Möglichkeiten für das 6-malige Werfen eines Würfels durchspielt und abzählt,
• eine Bedingung condition formuliert, die angibt, ob das gesuchte Ereignis eintritt,
• für jede Realisierung des 6-maligen Werfen des Würfels überprüft, ob die Bedingung condition eintritt und
• mitzählt, wie oft die Bedingung condition eintritt.

Abzählen aller Realisierungen beim Würfeln mit Hilfe eines Zählers

In den R-Skripten im Abschnitt Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem wurde ein Zähler vorgestellt, mit dem man in einem beliebigen Zahlensystem mit Basis base zu einer gegebenen Zahl z die nächste Zahl berechnen kann. Hier wird base = 6 gewählt. Eine Zahl z wird dann als Vektor der Länge N kodiert, wobei die erste Komponente von z die Einer angibt, die zweite Komponente die 6er, die dritte Komponente die 36er, und so weiter.

Der Zähler benötigt zwei Funktionen:

• den Halb-Addierer, der durch add.1(z, base) realisiert ist und
• die Funktion nextNumber(z, base, N) , die den Nachfolger von z als Vektor mit N Komponenten berechnet.

Reichen die N Stellen nicht mehr aus, um den Nachfolger zu kodieren, werden die Komponenten von z gleich NA gesetzt.

Die folgenden Skripte zeigen die beiden Funktionen add.1(z, base) und nextNumber(z, base, N) :

add.1 <- function(z, base){
  stopifnot(base > 1)
  stopifnot(z < base)
  if(identical(z, base - 1)) return(0)
  else return(z + 1)
}

Falls die Zahl z schon gleich der größten Ziffer base - 1 ist, liefert die Addition der 1 das Ergebnis 0; ein Übertrag wird bei der Halbaddition nicht erzeugt (Zeile 4). Für jede andere Ziffer kann 1 problemlos addiert werden (Halbaddition und Addition liefern das identische Ergebnis, siehe Zeile 5).

In der Funktion nextNumber(z, base, N) ist z ein Vektor, der höchstens die Länge N besitzt:

nextNumber <- function(z, base, N){
  stopifnot(length(z) <= N)
  stopifnot(base > 1)
  stopifnot(N > 0)
  
  n <- 1; c <- 1    # n: Index des Vektors; c: carry-Bit
  
  while(identical(c, 1)){
    # Carry-Bit ist gesetzt und alle Stellen maximal: return(NA)
    if(identical(z, rep(x = base - 1, times = N))){
      return(rep(x = NA, times = N))
    }
    # Carry-Bit zurücksetzen
    if(z[n] < base - 1) c <- 0
    z[n] <- add.1(z = z[n], base)    # Halbaddition
    n <- n + 1
  }
  return(z)
}

Zählt man jetzt ausgehend von 0 bis 36 im Zahlensystem mit Basis 6 und stellt die Ergebnisse mit 6 Stellen dar, erhält man:

# Zählen von 0 bis 36 im 6er-System

z <- rep(x = 0, times = 6)

for(i in (1:37)){
  cat("z = ", z, "\n")
  z <- nextNumber(z = z, base = 6, N = 6)
}
# z =  0 0 0 0 0 0 
# z =  1 0 0 0 0 0 
# z =  2 0 0 0 0 0 
# z =  3 0 0 0 0 0 
# z =  4 0 0 0 0 0 
# z =  5 0 0 0 0 0 
# z =  0 1 0 0 0 0 
# z =  1 1 0 0 0 0 
# z =  2 1 0 0 0 0 
# z =  3 1 0 0 0 0 
# z =  4 1 0 0 0 0 
# z =  5 1 0 0 0 0 
# z =  0 2 0 0 0 0 
# z =  1 2 0 0 0 0 
# z =  2 2 0 0 0 0 
# z =  3 2 0 0 0 0 
# z =  4 2 0 0 0 0 
# z =  5 2 0 0 0 0 
# z =  0 3 0 0 0 0 
# z =  1 3 0 0 0 0 
# z =  2 3 0 0 0 0 
# z =  3 3 0 0 0 0 
# z =  4 3 0 0 0 0 
# z =  5 3 0 0 0 0 
# z =  0 4 0 0 0 0 
# z =  1 4 0 0 0 0 
# z =  2 4 0 0 0 0 
# z =  3 4 0 0 0 0 
# z =  4 4 0 0 0 0 
# z =  5 4 0 0 0 0 
# z =  0 5 0 0 0 0 
# z =  1 5 0 0 0 0 
# z =  2 5 0 0 0 0 
# z =  3 5 0 0 0 0 
# z =  4 5 0 0 0 0 
# z =  5 5 0 0 0 0 
# z =  0 0 1 0 0 0

Klar ist dass die Ziffern im 6er-System die Zahlen von 0 bis 5 sind und dass der Würfel üblicherweise mit den Zahlen von 1 bis 6 beschriftet wird. Addiert man aber zu jeder Ziffer 1, erkennt man sofort, dass obige Ausgabe alle möglichen Ergebnisse beim 6-maligen Werfen eines Würfels liefert – man muss nur die Schleife bis 6⁶ = 46656 laufen lassen.

Abzählen derjenigen Ergebnisse, die eine zusätzliche Bedingung erfüllen

Das Abzählen aller Möglichkeiten beim 6-maligen Werfen eines Würfels kann mit dem Zähler nextNumber(z, base, N) leicht realisiert werden, indem man base = 6 und N = 6 setzt und von z <- rep(x = 0, times = 6) ausgehend zählt bis NA erreicht wird.

Jetzt muss man in die Schleife nur die Bedingung condition einfügen, die das gewünschte Ereignis charakterisiert; gezählt werden dann nur noch die Möglichkeiten, bei denen die Bedingung erfüllt ist.

Allgemein sieht dies dann folgendermaßen aus:

# condition: wird unten als geeigneter logischer Ausdruck gesetzt
N <- 6
all <- 6^N
z <- rep(x = 0, times = N)
counter <- 0

for(i in (1:all)){
    if(condition){
        # cat("z = ", z, "\n")
        counter <- counter + 1
    }
  z <- nextNumber(z = z, base = 6, N = 10)
}

cat("Anzahl der Ergebnisse: ", counter, "\n")

Zur Erklärung:

Zeile 2 bis 5: Die Anzahl der Würfe N stimmt zugleich mit der Länge des Vektors z überein. Durchgezählt werden alle 6⁶ Möglichkeiten und z wird zu Beginn als der Nullvektor gesetzt. Als Zähler wird die Variable counter verwendet.

Zeile 7 bis 13: Die Schleife durchläuft alle möglichen Ergebnisse beim 6-maligen Würfeln. In Zeile 8 muss die Bedingung eingesetzt werden, die überprüft werden soll. In Zeile 9 ist eine Ausgabe der Vektoren z vorgesehen, die die gewünschte Bedingung erfüllen; bei großen Anzahlen von Möglichkeiten sollte man die Ausgabe abschalten.

Zeile 15: Nach der Schleife wird die gesuchte Anzahl ausgegeben.

Im folgenden Skript wird mit condition überprüft, wie viele Möglichkeiten es gibt, dass bei 6 Würfen genau einmal 6 vorkommt:

N <- 6
all <- 6^N
z <- rep(x = 0, times = N)
counter <- 0

for(i in (1:all)){
  if(length(z[z == 5]) == 1){
    # cat("z = ", z, "\n")
    counter <- counter + 1
  }  
  z <- nextNumber(z = z, base = 6, N = N)
}

cat("Anzahl der Möglichkeiten: ", counter, "\n")
# Anzahl der Möglichkeiten:  18750

In Zeile 7 wird jetzt die Bedingung length(z[z == 5]) == 1 überprüft; an der Ausgabe ist zu erkennen, dass die oben berechnete Anzahl von Möglichkeiten bestimmt wurde.

Zähler für mehrere Bedingungen

Im letzten Skript wurde gezeigt, wie man beim Schleifendurchlauf eine Bedingung prüft und – falls sie erfüllt ist – einen Zähler hochzählt. Es kann dann auch nicht mehr schwer sein, mehrere Bedingungen innerhalb der Schleife zu prüfen und mehrere Zähler einzusetzen.

Das folgende Skript zeigt eine Funktion count(N, base) , die genau dies realisiert. Eingabewerte sind dabei die Länge der Versuchsreihe N und die Basis des Zahlensystems (6 um alle Ausgänge beim Würfeln zu erzeugen).

count <- function(N, base){
  all <- base^N
  z <- rep(x = 0, times = N) 
  counter <- vector(mode = "integer", length = N + 1)

  for(i in (1:all)){
    # Anzahl k der Treffer berechnen; 5 zählt als Treffer:
    k <- length(z[z == 5])    # k liegt in 0, 1, ..., N 

    # entsprechenden Zähler hochzählen
    counter[k + 1] <- counter[k + 1] + 1
    z <- nextNumber(z = z, base = base, N = N)
  }  
  return(counter)
}

# Test:
cnt <- count(N = 6, base = 6)
cnt
# [1] 15625 18750  9375  2500   375    30     1

Der Zähler durchläuft in der Schleife (Zeile 6 bis 13) alle möglichen Ergebnisse beim N-maligen Würfeln (siehe Zeile 2).

Innerhalb der Schleife wird nicht nur eine Bedingung abgefragt, sondern der Zähler counter ist als Vektor der Länge N + 1 vorbereitet, so dass er für alle Ereignisse der Form "k-mal 6 bei N Würfen", k = 0, 1, 2, ..., N, mitzählen kann (siehe Zeile 8 und 11).

Die Ergebnisse stimmen mit den oben berechneten Werten überein.

Und so wie die Funktion count(N, base) angelegt ist, können mit ihr beliebige Längen N von Versuchsreihen und beliebige Basen base verarbeitet werden.

Aufgabe:

Untersuchen Sie für welche Längen von Versuchsreihen N die Funktion count() mit zumutbarer Rechenzeit eingesetzt werden kann.

Bemerkung: Die Funktion nextNumber() ist in ihrer jetzigen Form zwar sehr einfach in ihrer Implementierung, aber nicht auf Schnelligkeit optimiert. Man sieht dies daran, dass sie bei jedem Zählschritt eine Schleife einsetzt, obwohl meist nur in einer Komponente des Vektors z eine 1 zu addieren ist.