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

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Grundbegriffe der Wahrscheinlichkeitsrechnung
      • Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme
      • Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik
      • Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars

Einführung

Im Folgenden werden vier Abzählprobleme vorgestellt, die auf den ersten Blick völlig unterschiedlich sind. Das Bekannteste davon wird meist als Kombinationen mit Wiederholungen bezeichnet. Es wird gezeigt, dass alle vier Abzählprobleme äquivalent sind – und dieser Nachweis wird nebenbei zahlreiche Techniken im Umgang mit Abzählproblemen einüben.

Bei Kombinationen mit Wiederholungen denke man etwa an eine "Ziehung der Lottozahlen", bei der jede gezogene Kugel sofort wieder in die Trommel gelegt wird und erneut gezogen werden kann. Dabei sollen sich mit 1, ..., n numerierte Kugeln in der Trommel befinden, es werden k Kugeln gezogen und ihre Nummern nach der Ziehung der Größe nach angeordnet. Das Abzählproblem gilt als gelöst, wenn man die Anzahl der möglichen Ergebnisse als Funktion von n und k angeben kann.

Der einfachste Zugang zu den Abzählproblemen ist, dass man die Formel für die Anzahl der möglichen Ergebnisse angibt und beweist. Um aber die Arbeitstechniken im Umgang mit Abzählproblemen einzuüben, wird hier ein anderer Zugang gewählt:

1. Die vier Abzählprobleme werden zunächst vorgestellt (eines davon ist das Ziehen der Lottozahlen mit Wiederholungen).
2. Ihre Äquivalenz wird nachgewiesen, indem man zeigt, dass sie
   • eine identische Rekursionsformel erfüllen und
   • der Rekursionsanfang identisch ist.
3. Die Äquivalenzen lassen sich auch direkt zeigen, indem man angibt, wie ein Abzählproblem in das andere überführt werden kann.
4. Erst wenn eine gewisse Vertrautheit mit den Abzählproblemen eingetreten ist, wird die Formel für Anzahl der möglichen Ergebnisse bewiesen. Die Beweismethode wird in der Literatur oft mit "Stars and Bars" bezeichnet. Es wird sich zeigen, dass je nach Formulierung der Abzählprobleme die Beweismethode mehr oder weniger naheliegend ist.

In den R-Skripten wird dann gezeigt, wie man die Menge aller möglichen Ergebnisse der vier Abzählprobleme erzeugen kann.

Vier Abzählprobleme

Im Folgenden werden vier Abzählprobleme vorgestellt, die auf den ersten Blick unterschiedlich sind; es ist aber möglich, sie so umzuformulieren, dass die gesuchten Anzahlen mit der identischen Formel berechnet wird.

Achtung: Alle Abzählprobleme werden mit Hilfe von zwei natürlichen Zahlen n und k beschrieben. Bei ihrer Formulierung (und später beim Beweis) ist darauf zu achten, dass die Abzählprobleme nicht symmetrisch in n und k sind. Anders gesagt: Bei Vertauschung von n und k wird eine andere Anzahl von Möglichkeiten gesucht.

Eine Variation des Lottospiels: Auswahl von k aus n Kugeln mit Zurücklegen

Das – übliche – Lottospiel "k aus n" kann man wie folgt charakterisieren:

• Es gibt n Kugeln, die von 1 bis n numeriert sind.
• Daraus werden nacheinander (ohne Zurücklegen) k Kugeln gezogen.
• Die k Kugeln werden anschließend sortiert.

Um "k Richtige" zu erzielen, muss man voraussagen, welche Zahlen gezogen werden; man muss nicht voraussagen, in welcher Reihenfolge die Zahlen gezogen wurden.

Die Anzahl der Möglichkeiten, wie viele unterschiedliche Ergebnisse es geben kann, wird durch den Binomialkoeffizient "k aus n" beschrieben.

Von diesem Lottospiel soll nun eine Variation betrachtet werden, die im Folgenden als Lotto mit Wiederholungen bezeichnet wird:

• Es gibt n Kugeln, die von 1 bis n numeriert sind.
• Daraus werden nacheinander (mit Zurücklegen) k Kugeln gezogen.
• Die k Kugeln werden anschließend sortiert.

Der Unterschied zwischen Lotto und Lotto mit Wiederholungen besteht also nur darin, dass jetzt jede Kugel nachdem sie gezogen wurde, wieder in die Trommel zurückgelegt wird. Somit ist

1 2 3 4 5 6

ein mögliches Ergebnis beider Lotto-Varianten "6 aus 49", dagegen kann

1 1 2 3 4 5

nur in der Variante Lotto mit Wiederholungen vorkommen.

Ein weiterer Unterschied zwischen Lotto und Lotto mit Wiederholungen soll ausdrücklich betont werden: Beim Lotto wird die Trommel im Laufe der Zehungen geleert, daher muss k ≤ n sein. Beim Lotto mit Wiederholungen gibt es keine Einschränkung, wie groß k und n sein müssen, lediglich die Möglichkeiten k = 0 oder n = 0 werden hier nicht behandelt.

Das relevante Abzählproblem lautet: Wie groß ist die Anzahl der möglichen Ergebnisse beim Lotto mit Wiederholungen.

Beispiel:

Es ist klar, dass beim Lotto "6 aus 49" die Anzahl der möglichen Ergebnisse in der Größenordnung von Millionen liegt. Um ein überschaubares Beispiel zu demonstrieren, werden in den folgenden Tabellen alle möglichen Ergebnisse für n = 3, k = 4 sowie für n = 4, k = 3 gezeigt. Dabei erkennt man insbesondere, dass das Abzählproblem nicht symmetrisch in n und k ist.

1. Ziehung von k = 4 Zahlen aus (1, 2, 3):

Die erste Zeile der folgenden Tabelle zählt die Kombinationen – es gibt 15. Jede Spalte unter der Nummer 1, ..., 15 gibt eine mögliche Realisierung des "Lotto mit Wiederholungen 4 aus 3" an:

Tabelle 1: Mögliche Ergebnisse beim "Lotto 4 aus 3 mit Wiederholungen" in lexikographischer Anordnung (von viermal die 1 bis viermal die 3).

2. Ziehung von k = 3 Zahlen aus (1, 2, 3, 4):

Jetzt gibt es 20 Realisierungen, die in der ersten Zeile gezählt werden. Jede Realisierung besteht aus 3 Zahlen (wieder die Spalte unter der Nummer):

Tabelle 2: Mögliche Ergebnisse beim "Lotto 3 aus 4 mit Wiederholungen".

Verteilung von k identischen Kugeln auf n unterscheidbare Urnen

Es sollen n Urnen bereitstehen, die unterscheidbar sind, also etwa in der Reihe angeordnet und durchnumeriert mit 1, ..., n. Auf diese Urnen werden k identische Kugeln verteilt, wobei gelten soll:

• Jede Urne kann beliebig viele Kugeln aufnehmen, kann also auch leer bleiben.
• Aufgrund der letzten Bedingung, muss man keine Einschränkung an k und n machen, lediglich k = 0 oder n = 0 wird ausgeschlossen.

Da die Urnen unterscheidbar sind, die Kugeln aber identisch sind, wird eine Konfiguration charakterisiert durch die n Besetzungszahlen der Urnen:

k₁, k₂, ..., k_n, mit

k₁ + k₂ + ... + k_n = k.

Gesucht ist die Anzahl der Konfigurationen, wie sich die k Kugeln auf die n Urnen verteilen lassen.

Beispiel:

Die folgende Tabelle zeigt die möglichen Besetzungszahlen, wenn k = 4 Kugeln auf n = 3 Urnen verteilt werden. Es gibt 15 Konfigurationen, die in der ersten Spalte der Tabelle gezählt werden; die Besetzungszahlen einer Konfiguration stehen dann jeweils in einer Zeile:

Tabelle 3: Die möglichen Besetzungszahlen, wenn k = 4 Kugeln auf n = 3 Urnen verteilt werden. Es gibt 15 unterschiedliche Konfigurationen, die in der ersten Spalte gezählt werden.

Darstellung einer gegebenen Zahl k durch n Summanden

Eine natürliche Zahl k soll durch n Summanden dargestellt werden, wobei folgende Regeln gelten:

• Jeder Summand darf die Werte 0, 1, ..., k annehmen.
• Jeder Summand darf beliebig oft vorkommen.
• Auch wenn die Summanden lediglich vertauscht werden, zählt dies als eine neue Anordnung.

Ist zum Beispiel k = 7 und n = 3, so sind – unter anderem – folgende Summen-Darstellung erlaubt:

0 + 0 + 7 = 7, 0 + 1 + 6 = 7, 0 + 6 + 1 = 7 und so weiter.

Ein Tupel wie (0, 0, 7) wird dann eine Partition von k = 7 der Länge n = 3 bezeichnet. So wie hier der Begriff Partition verwendet wird, sind (0, 1, 6) und (0, 6, 1) unterschiedlich. Der Deutlichkeit halber spricht man auch von geordneten Partitionen, wenn derartige Tupel unterschieden werden (das soll heißen, dass man auf die Anordnung der Summanden achtet, andernfalls spricht man von ungeordneten Partitionen).

Gesucht ist die Anzahl der Möglichkeiten, wie sich eine Zahl k durch n Summanden darstellen lässt.

Anzahl der Pfade im Gitter

In Abbildung 1 ist ein Gitter dargestellt, das über den ganzen Zahlen in der Ebene errichtet wird (relevant ist eigentlich nur der 1. Quadrant des Koordinatensystems). Im Gitter sind die beiden Punkte mit den Koordinaten

(1, 0) und (n, k), n, k ≥ 1,

hervorgehoben (blau).

Abbildung 1: Oben links: Rot eingezeichnet ist ein Pfad, der von (1, 0) nach (3, 4) führt. Oben rechts: Angegeben sind die Koordinaten und die erlaubten Schritte, aus denen ein Pfad zusammengesetzt werden kann. Unten: Die Anzahl der erlaubten Pfade erfüllt eine Rekursionsformel (genauere Erläuterung im Text).

Ein Pfad in diesem Gitter entsteht dadurch, dass man sich in jedem Schritt entweder um 1 nach oben oder um 1 nach rechts bewegt; Bewegungen nach unten oder links sind verboten.

In Abbildung 1 oben ist ein erlaubter Pfad eingezeichnet (rot), der von (1, 0) nach (3, 4) führt, indem man

• zuerst 2 Schritte nach oben,
• einen Schritt nach rechts,
• 2 Schritte nach oben und zuletzt
• wieder einen Schritt nach rechts geht.

Gesucht ist hier die Anzahl der Pfade, die von (1, 0) zu (n, k) führen und sich aus den erlaubten Schritten zusammensetzen.

Die Äquivalenz der vier Abzählprobleme

Rekursionsformel und Rekursionsanfang

Anstatt sofort die Lösung des Abzählproblems in Angriff zu nehmen, wird zunächst gezeigt, dass die gesuchten Anzahlen der vier geschilderten Abzählprobleme die Rekursionsformel (Gleichung (1) in Abbildung 2) und den Rekursionsanfang erfüllen (Gleichungen (2) und (3) in Abbildung 2). Damit ist bewiesen, dass die 4 Abzählprobleme äquivalent sind und durch eine geeignete Umformulierung ineinander übergeführt werden können.

Die gesuchte Anzahl von möglichen Ergebnissen der Abzählprobleme wird dabei jeweils mit

C(n, k), n, k ≥ 1,

bezeichnet; es sei nochmals betont, dass die Abzählprobleme nicht symmetrisch in n und k sind und sich die Bezeichnung C(n, k) auf obige Beschreibungen bezieht.

Abbildung 2: Alle 4 Abzählprobleme erfüllen die Rekursionsformel, die in Gleichung (1) dargestellt ist. Der Rekursionsanfang, also der Ausdruck für C(n = 1, k) beziehungsweise C(n, k = 1) ist in den Gleichungen (2) und (3) gezeigt. Setzt man die Rekursionsformel immer wieder in sich selbst ein, erhält man Gleichung (4).

Rekursionsformel beim Lotto mit Wiederholungen

Der Rekursionsanfang ist leicht zu sehen.

1. C(n = 1, k) = 1, k ≥ 1

Die Forderung n = 1 bedeutet, dass in der Lottotrommel lediglich eine Kugel liegt; sie sei mit 1 beschriftet. Egal wie viele Kugeln gezogen werden, also unabhängig von der Größe von k, gibt es nur ein Ergebnis, nämlich die k-fache Wiederholung der 1.

2. C(n, k = 1), n ≥ 1

Jetzt befinden sich in der Trommel beliebig viele Kugeln, aber es wird nur eine Kugel gezogen. Dann gibt es so viele Ergebnisse wie Kugeln in der Trommel sind, nämlich n.

Die Rekursionsformel ist schwieriger herzuleiten. Die Beweisidee ist in Abbildung 3 dargestellt.

Befinden sich in der Lottotrommel n Kugeln (beschriftet von 1 bis n) und werden k Kugeln mit Zurücklegen gezogen, so gibt es C(n, k) mögliche Ergebnisse, die in Abbildung 3 links oben symbolisiert sind. Üblicherweise wird man die Ergebnisse anordnen wie es rechts zu sehen ist; dabei steht jede Spalte für ein Ergebnis, also einer Folge von k Zahlen:

• In lexikographischer Anordnung besteht das erste Ergebnis aus k Wiederholungen der 1,
• das zweite Ergebnis besteht aus k-1 Wiederholungen der 1 und hat an letzter Stelle eine 2.
• Und so weiter.
• Das letzte Ergebnis besteht aus k Wiederholungen von n.

Abbildung 3: Links oben: Die Menge aller Kombinationen "k aus n" mit Wiederholungen besitzt die Mächtigkeit C(n, k). Oben rechts: Üblicherweise werden die Kombinationen lexikographisch angeordnet, was aber zum Abzählen ungeeignet ist. Unten links: Die Kombinationen werden in zwei Mengen eingeteilt, bei denen die letzte Komponente entweder gleich n oder ungleich n ist. Mit dieser Einteilung lässt sich leicht die Rekursionsformel (unten rechts) herleiten.

Um diese Folgen abzuzählen, werden sie in zwei Gruppen eingeteilt (Abbildung 3 unten):

1. Folgen, die mit n enden.
2. Folgen, die mit einer anderen Zahl als n enden (dies soll der Strich über n andeuten).

Aufgrund dieser Bedingung kommt jedes mögliche Ergebnis nur in einer der beiden Gruppen vor. Und diese beiden Mengen lassen sich leichter abzählen:

1. Da in der linken Gruppe das letzte Element eindeutig festgelegt ist, ändert sich die Mächtigkeit nicht, wenn man in Abbildung 3 die letzte Zeile wegstreicht. Übrig bleiben dann Folgen der Länge k-1, die aus den Elementen 1, 2, ..., n bestehen können. Aber deren Anzahl ist gerade C(n, k-1).
2. In der rechten Gruppe sind Folgen der Länge k, die aus den Elementen 1, 2, ..., n-1 bestehen. Davon gibt es C(n-1, k).

Da die beiden Mengen disjunkt sind, erhält man insgesamt:

C(n, k) = C(n, k-1) + C(n-1, k),

also die gesuchte Rekursionsformel.

Diese Aufspaltung der möglichen Ergebnisse in zwei Gruppen wird unten verwendet, um zu gegebenem n und k alle möglichen Ergebnisse beim Lotto mit Wiederholungen zu erzeugen.

Rekursionsformel für k Kugeln in n Urnen

Die Argumentation ist hier ganz ähnlich wie bei der Ziehung der Lottozahlen mit Wiederholungen.

Es werden n unterscheidbare Urnen betrachtet (man sollte sie sich numeriert denken mit 1, ..., n), in die k Kugeln verteilt werden; die Kugeln lassen sich nicht unterscheidbar. Eine mögliche Verteilung wird somit durch die Angabe von n Besetzungszahlen charakterisiert. Die i-te Besetzungszahl gibt an, wie viele Kugeln sich in der Urne i befinden. Für eine Besetzungszahl ist jede Zahl von 0 bis k erlaubt.

Der Rekursionsanfang ist wieder leicht zu sehen.

1. C(n = 1, k) = 1, k ≥ 1

Die Forderung n = 1 bedeutet, dass es nur eine Urne gibt. In diese müssen dann alle Kugeln gelegt werden und es gibt nur eine Möglichkeit.

2. C(n, k = 1), n ≥ 1

Jetzt gibt es n Urnen, aber nur eine Kugel. Daher gibt es n Möglichkeiten, wo die Kugel abgelegt werden kann.

Die Rekursionsformel wird mit einer ähnlichen Überlegung hergeleitet wie beim Lotto mit Wiederholungen. Es besteht aber ein großer Unterschied: Jetzt werden Folgen der Länge n abgezählt, nämlich die Folgen der Besetzungszahlen. Beim Lotto wurden Folgen der Länge k betrachtet, die das Ergebnis der Ziehung von k Kugeln aus der Trommel beschreiben. Und für die Folgen der Besetzungszahlen gibt es keine Monotonie-Eigenschaft, da die Besetzungszahlen nicht sortiert werden (wie die Ergebnisse bei der Ziehung der Lottozahlen).

Abbildung 4 versucht die Vorgehensweise darzustellen:

• Oben ist die Ausgangssituation mit den k Kugeln und den n (numerierten) Urnen zu sehen.
• Die Tabelle darunter deutet die lexikographische Anordnung der Folgen von Besetzungszahlen an.
• Es soll die (bekannte) Rekursionsformel für C(n, k) hergeleitet werden, wobei C(n, k) jetzt für die Anzahl der möglichen Folgen von Besetzungszahlen steht.

Abbildung 4: Darstellung der Vorgehensweise zur Herleitung der Rekursionsformel für die Anzahl der Folgen von Besetzungszahlen bei der Aufteilung von k Kugeln auf n unterscheidbare Urnen.

Unten in Abbildung 4 wird eine ähnliche Überlegung wie beim Lotto mit Wiederholungen angedeutet: Man zerlegt die Folgen von Besetzungszahlen in zwei Gruppen:

1. Diejenigen Folgen, bei denen die letzte Urne (Nummer n) nicht belegt ist (Besetzungszahl 0).
2. Diejenigen Folgen mit einer oder mehr Kugeln in der letzten Urne (symbolisiert durch das "Komplement" von 0).

Diese beiden Mengen sind disjunkt und ihre Mächtigkeit kann mit Hilfe der Funktion C ausgedrückt werden:

1. Wenn die letzte Urne leer ist, wurden die k Kugeln auf n-1 Urnen verteilt, somit besteht diese Gruppe aus C(n-1, k) Elementen.
2. Liegt mindestens eine Kugel in der letzten Urne, so wurden k-1 Kugeln auf n Urnen verteilt, wofür es C(n, k-1) Möglichkeiten gibt.

Insgesamt ergibt sich auch für die Anzahl der Folgen von Besetzungszahlen die Rekursionsformel:

C(n, k) = C(n, k-1) + C(n-1, k).

Rekursionsformel für die Anzahl der Partitionen

Soll eine ganze Zahl k durch n Summanden dargestellt werden, wobei die 0 als Summand erlaubt ist und die Reihenfolge der Summanden beachtet wird, so kann man das Problem leicht umformulieren in das Aufteilen von k Kugeln auf n Urnen. Dazu identifiziert man

• die Urnen mit den Stellen, an denen die Summanden stehen und
• die Anzahl der Kugeln in einer Urne (sie wurde als Besetzungszahl bezeichnet) als einen Summanden.

Jetzt kann die identische Überlegung wie im letzten Unterabschnitt angestellt werden, um die Rekursionsformel für die Anzahl der Partitionen zu zeigen.

Rekursionsformel für die Anzahl der Pfade

Mit C(n, k) wird jetzt die Anzahl der Pfade bezeichnet, die vom Punkt (1,0) zu (n, k) führen, wobei jeder Pfad aus zwei erlaubten Schritten aufgebaut wird (siehe Abbildung 1):

• man darf sich nach oben oder
• nach rechts bewegen.

Pfade, die zwar identische Schritte gehen, dies aber in unterschiedlicher Reihenfolge, werden hierbei unterschieden.

Der Rekursionsanfang ist auch hier leicht zu sehen.

1. C(n = 1, k) = 1, k ≥ 1

Ist n = 1 und nimmt k einen beliebigen Wert an, so liegt der Zielpunkt genau über dem Start und es gibt nur eine Möglichkeit, wie man das Ziel erreichen kann: alle Schritte führen nach oben.

2. C(n, k = 1), n ≥ 1

Jetzt muss man einen Schritt nach oben und n-1 Schritte nach rechts gehen. Man muss insgesamt n Schritte ausführen und für den Schritt nach oben gibt es n Möglichkeiten, "wann" er ausgeführt wird.

Der Beweis der Rekursionsformel ist in Abbildung 1 unten angedeutet: Um zum Punkt (n, k) zu gelangen, muss man im vorherigen Schritt

• entweder den Punkt (n-1, k) erreichen
• oder den Punkt (n, k-1).

In der Menge der Pfade, die zu (n-1, k) führen ist kein Pfad enthalten, der zu (n, k-1) führt und umgekehrt. Somit wird in C(n, k-1) + C(n-1, k) kein Pfad mehrfach gezählt und man erhält die gesuchte Rekursionsformel:

C(n, k) = C(n, k-1) + C(n-1, k).

Vorläufige Zusammenfassung

Bisher wurde nur gezeigt, dass die Anzahl der möglichen Ergebnisse bei den vier oben beschriebenen Abzählproblemen mit der identischen Funktion C(n, k) beschrieben wird, für die die Rekursionsformel (Gleichung (1) in Abbildung 2) und der Rekursionsanfang (Gleichungen (2) und (3) in Abbildung 2) gelten. Da sich die Werte von C(n, k) damit eindeutig berechnen lassen, ist gezeigt, dass die vier Abzählprobleme äquivalent sind. Allerdings ist die Äquivalenz damit nur indirekt nachgewiesen. Es ist noch nicht gezeigt:

1. Wie man die Abzählprobleme direkt ineinander überführen kann.
2. Wie der Funktionsterm für C(n, k) lautet.

(Der erste Punkt wurde zumindest für die Verteilung von k Kugeln auf n Urnen und die Anzahl der Partitionen von k der Länge n gezeigt, indem man die Besetzungszahlen und die Summanden miteinander identifiziert.)

Im folgenden Abschnitten werden diese noch fehlenden Eigenschaften der Abzählprobleme besprochen.

Der direkte Nachweis der Äquivalenz der Abzählprobleme

Wie die Verteilung der k Kugeln auf die n Urnen und die Anzahl der Partitionen der Länge n einer Zahl k zusmmenhängen, wurde bereits erklärt.

Deutlich schwieriger ist der Zusammenhang zwischen "Lotto mit Wiederholungen" und den "Partitionen". Denn betrachtet man den Nachweis der Rekursionsformel, so sieht man, dass hier Folgen abgezählt wurden, die auf den ersten Blick nichts miteinander zu tun haben. Diese Äquivalenz soll zuerst nachgewiesen werden, indem man zeigt, wie die Folgen ineinander transformiert werden.

Der Nachweis, dass die Abzählprobleme "Lotto mit Wiederholungen" und "Partitionen" jeweils äquivalent zu den "Pfaden" sind, ist dagegen sehr einfach und erfolgt im Anschluss.

Äquivalenz von Lotto mit Wiederholungen und Partitionen

1. Konstruktion einer Partition aus einer Auswahl:

Das Ergebnis einer Ziehung beim "Lotto k aus n mit Wiederholungen" kann durch eine monoton zunehmende Folge

a₁ ≤ a₂ ≤ ... ≤ a_k

dargestellt werden. Beim Lotto k aus n sind die Zahlen echt verschieden und man könnte sie mit < anordnen; da jetzt Wiederholungen möglich sind, können aufeinander folgende Zahlen auch identisch sein.

Durch die Angabe der Auswahl a₁ ≤ a₂ ≤ ... ≤ a_k aus den Zahlen der Menge

M_n = {1, 2, ..., n}

sind zwei Dinge eindeutig festgelegt:

1. Eine Teilmenge M_a von M_n, die angibt welche Zahlen gezogen wurden.
2. Wie oft diese Zahlen in der Auswahl enthalten sind, also die absoluten Häufigkeiten der Elemente von M_a. Für Zahlen aus M_n, die nicht in der Auswahl enthalten sind, wird die Häufigkeit gleich 0 gesetzt.

Da insgesamt k Zahlen gezogen wurden, addieren sich die Häufigkeiten zu k. Das Tupel der Häufigkeiten bildet somit eine Partition der Zahl k; die Anzahl der Summanden dieser Partition stimmt mit der Mächtigkeit von M_n überein, wenn man auch 0 als Summanden zulässt (wird 0 nicht zu den Summanden gezählt, stimmt die Anzahl der Summanden mit der Mächtigkeit von M_a überein.)

Beispiel:

Wird beim Lotto "4 aus {1, 2, 3}" die Auswahl 1, 3, 3, 3 getroffen, so ist

M_a = {1, 3}

und die absoluten Häufigkeiten sind

h₁ = 1, h₂ = 0, h₃ = 3.

Und es gilt:

h₁ + h₂ + h₃ = 1 + 0 + 3 = 4.

2. Konstruktion einer Auswahl aus einer Partition:

Ist eine Partition der Zahl k mit der Länge n gegeben, wobei 0 als Summand zugelassen ist, so gibt es Zahlen h₁, h₂, ..., h_n mit

h₁ + h₂ + ... + h_n = k und 0 ≤ h_i ≤ k.

Bildet man jetzt das Tupel der k Zahlen nach folgendem Verfahren:

• Man wählt h₁ mal die Zahl 1.
• Man wählt h₂ mal die Zahl 2.
• ...
• Man wählt h_n mal die Zahl n.

so erhält man ein Tupel von k Zahlen, das monoton zunehmend ist und somit beim "Lotto k aus n mit Wiederholungen" entstanden sein könnte.

Beispiel:

Zur Partition der Zahl k = 4 mit

h₁ = 1, h₂ = 0, h₃ = 3

lautet die Auswahl:

1, 3, 3, 3.

Äquivalenz von Lotto mit Wiederholungen und Pfaden im Gitter

1. Konstruktion eines Pfades aus einer Auswahl

Es wird wieder von einer monoton zunehmende Folge

a₁ ≤ a₂ ≤ ... ≤ a_k

ausgegangen, die beim "Lotto k aus n mit Wiederholungen" entstanden ist.

Ein Pfad, der von (1, 0) nach (n, k) führt, muss aus n - 1 + k Anweisungen bestehen, die jeweils angeben, ob man sich im nächsten Schritt nach rechts → oder nach oben %uarr; bewegen muss. Dabei müssen k Pfeile nach oben und n - 1 Pfeile nach rechts zeigen.

Wie oben (als aus einer Auswahl die Partition konstruiert wurde) werden Häufigkeiten h₁, h₂, ..., h_n mit

h₁ + h₂ + ... + h_n = k und 0 ≤ h_i ≤ k

gebildet. Der Index der Häufigkeit h_i gibt an, an welcher n-Koordinate man sich im Pfad befindet (i läuft von 1 bis n). Der Wert der Häufigkeit gibt an, um wie viele Schritte man sich nach oben bewegen muss.

Man geht also folgendermaßen vor:

• Ist h₁ = 0, so geht man einen Schritt nach rechts →.
• Ist h₁ ungleich 0, so geht man h₁ Schritte nach oben ↑ und anschließend einen Schritt nach rechts.
• Analog wird h₂ abgearbeitet.
• Und so weiter.
• Zuletzt wird h_n abgearbeitet, aber der anschließende Schritt nach rechts unterbleibt.

Da sich die h_i zu k addieren und man bei n-1 Häufigkeiten jeweils einen Schritt nach rechts macht, erreicht man den Punkt (n, k).

Beispiel:

Ist n = 3 und k = 4 und wurden die Zahlen 1, 1, 2, 2 gezogen, so ist

h₁ = 2, h₂ = 2, h₃ = 0.

Nach obigen Regeln erhält man die Anweisungen:

↑ ↑ → ↑ ↑ →

Dies entspricht dem Pfad, der in Abbildung 1 oben dargestellt ist.

2. Konstruktion einer Auswahl aus einem Pfade

Ein Pfad kann in eine Folge von Einzelschritten zerlegt, die entweder → oder ↑ lauten. Aus der Folge von Pfeilen kann man jetzt die Häufigkeiten h_i konstruieren:

• Jeder Pfeil ↑ wird als Anweisung gelesen zum nächsten h_i zu gehen. Startet die Folge mit einem Pfeil nach rechts →, wird h₀ = 0 gesetzt. Startet die Folge mit einem Pfeil nach oben ↑ wird zuerst h₁ abgelesen.
• Die Anzahl aufeinander folgender Pfeile ↑ gibt an, wie groß das entsprechende h_i ist.

Die Häufigkeiten h_i können wie oben beschrieben in eine Auswahl a_i übersetzt werden (siehe oben: Konstruktion einer Auswahl aus einer Partition).

Beispiel:

Ist die Schrittfolge

↑ ↑ → ↑ ↑ →

gegeben, so muss man zuerst h₁ ablesen (kein Pfeil nach rechts zu Beginn der Folge). Da zwei Pfeile ↑ folgen, ist h₁ = 2.

Der folgende Pfeil → gibt an zu h₂ zu gehen. Auch h₁ = 2. Da es keinen weiteren Pfeil nach oben gibt, ist h₃ = 0. Die Häufigkeiten sind also

h₁ = 2, h₂ = 2, h₃ = 0.

Die Beweismethode "Stars and Bars"

Nachdem ausführlich gezeigt wurde, dass die vier oben vorgestellten Abzählprobleme äquivalent sind, ist es unerheblich, welches gewählt wird, um endlich die Formel für die Anzahl C(n, k) herzuleiten. Die Methode zu ihrer Berechnung wird in der Literatur oft als "Stars and Bars" bezeichnet. Sie ist vermutlich nicht einfach zu finden, wenn man zum ersten Mal mit einem der Abzählprobleme konfrontiert wird, aber erstaunlich einfach, wenn man einmal den Kern der Probleme erkannt hat. Und die zuletzt besprochenen Umformulierung zwischen den Abzählproblemen und insbesondere die Formulierung mit Hilfe der Folge von Pfeilen geben den entscheidenden Hinweis darauf, dass es sich um ein Problem ähnlich der Auswahl der Treffer aus einer Folge von Spielen handelt, was zu den Binomialkoeffizienten führt.

Man könnte diesen Gedanken jetzt leicht mit der Folge von Pfeilen beim Abzählen der Pfade durchführen. Um die Beweisidee klarer herauszustellen, wird das Problem der Partitionen verwendet.

Jede Partition der Länge n einer Zahl k ist eine Summe der Art:

s₁ + s₂ + ... + s_n = k.

Man wandelt diese Summe in eine Folge der Symbole Star * und Bar | um, wobei folgende Regeln gelten:

1. Jedes Pluszeichen wird in das Symbol | verwandelt.
2. Jeder Summand s_i wird durch die entsprechende Anzahl von * dargestellt. (Ist ein Summand gleich 0, so folgt der nächste Stab | .)

Beispiel: Die Partitionen

1 + 0 + 3 = 4

0 + 2 + 2 = 4

werden symbolisiert durch:

*||***
|**|**

Man erkennt:

• Es werden bei jeder Partition der Länge n der Zahl k genau n - 1 + k Symbole vergeben, nämlich n - 1 mal der Stab | und k-mal der Stern * .
• Die Symbole * und | können an beliebiger Stelle stehen.

Aber dann lässt sich die Anzahl der möglichen Partitionen durch den Binomialkoeffizienten "k aus n - 1 + k" beschreiben; aufgrund der Symmetrie der Binomialkoeffizienten, stimmt er mit "n - 1 aus n - 1 + k" überein (siehe Abbildung 5, Gleichung (1)).

Abbildung 5: Gleichung (1) zeigt die Anzahl C(n, k), die bei allen vier Abzählproblemen die gesuchte Anzahl von Realisierungen beschreibt. Aufgrund der Symmetrie des Binomialkoeffizienten gibt es zwei Darstellungsarten. Gleichung (2) bis (4) zeigen nochmals die Rekursionsformel und den Rekursionsanfang. Anschließend wird gezeigt, dass beide von C(n, k) aus (1) erfüllt werden. Dazu müssen nur die Binomialkoeffizienten durch Fakultäten ausgedrückt und geeignet umgeformt werden.

Es bleibt jetzt nur noch zu zeigen, dass auch der Binomialkoeffizient "k aus n - 1 + k" die Rekursionsformel für C(n, k) erfüllt. Der Nachweis erfolgt in Abbildung 5.

In der folgenden Tabelle sind die Werte von C(n, k) für 1 ≤ n, k ≤ 10 dargestellt.

Tabelle 4: Die möglichen Anzahlen C(n, k) der geschilderten Abzählprobleme mit 1 ≤ n, k ≤ 10.

Aufgabe: Oben wurde nur gezeigt, wie man das Abzählproblem für die Partitionen mit Hilfe von "Stars and Bars" behandelt. Zeigen Sie dies für die anderen Abzählprobleme.

R-Skripte

Die Berechnung der Anzahl C(n, k)

In Tabelle 4 wurden die Anzahlen C(n, k) für n- und k-Werte bis 10 gezeigt. Da man auf diese Anzahl im Folgenden öfters zurückgreifen wird, wird eine Funktion StarsBars() implementiert. Eigentlich kann man den Zahlenwert mit einer Anweisung mit Hilfe von choose() berechnen, da man aber – wie oben im Theorieteil – mit den Argumenten n und k arbeiten möchte, ist es weniger fehleranfällig, wenn man auf die entsprechende Funktion zugreifen kann.

StarsBars <- function(n, k){
  return(choose(n = n + k - 1, k = k))
}

Die Zahlenwerte aus Tabelle 4 lassen sich dann mit Hilfe von outer() berechnen:

xs <- (1:10)
m.10 <- outer(X = xs, Y = xs, FUN = StarsBars)
m.10
#      [,1] [,2] [,3] [,4] [,5] [,6]  [,7]  [,8]  [,9] [,10]
# [1,]    1    1    1    1    1    1     1     1     1     1
# [2,]    2    3    4    5    6    7     8     9    10    11
# [3,]    3    6   10   15   21   28    36    45    55    66
# [4,]    4   10   20   35   56   84   120   165   220   286
# [5,]    5   15   35   70  126  210   330   495   715  1001
# [6,]    6   21   56  126  252  462   792  1287  2002  3003
# [7,]    7   28   84  210  462  924  1716  3003  5005  8008
# [8,]    8   36  120  330  792 1716  3432  6435 11440 19448
# [9,]    9   45  165  495 1287 3003  6435 12870 24310 43758
# [10,]   10   55  220  715 2002 5005 11440 24310 48620 92378

Die rekursive Berechnung aller Kombinationen k aus n mit Wiederholungen

Die Zurückführung auf eine Rekursion

Im Folgenden soll eine Funktion entwickelt werden, die sämtliche Kombinationen mit Wiederholungen berechnet, wobei

• n wieder für die Anzahl der Elemente steht, aus denen die Auswahl getroffen wird und
• k für die Länge der Auswahl.

Die möglichen Kombinationen sollen spaltenweise in einer Matrix angeordnet werden und ihre Anordnung soll in lexikographischer Reihenfolge geschehen.

In Abbildung 6 wird versucht zu erklären, wie man diese Matrix durch einen rekursiven Funktionsaufruf aufbauen kann. Dazu ist wieder für das Beispiel mit n = 3 und k = 4 die Tabelle der möglichen Ziehungen gezeigt – diese Tabelle soll in eine Matrix verwandelt werden (natürlich ohne die Kopfzeile, die die Ergebnisse zählt).

Wie man sofort sehen wird, ist es suggestiver in der Anzahl C(n, k) nicht die Mächtigkeit n anzugeben, sondern die tatsächliche Menge M, aus der die Auswahl getroffen wird, hier

M = {1, 2, 3}.

Abbildung 6: Veranschaulichung des Algorithmus zur rekursiven Berechnung aller Kombinationen mit Wiederholungen. Die Kombinationen werden spaltenweise angeordnet (wie es in der Tabelle oben zu sehen ist). Der Algorithmus berechnet die entsprechende Matrix, wobei diese zuerst in Teilmatrizen zerlegt wird. Diese Teilmatrizen haben in der ersten Zeile jeweils identische Einträge und eine Breite (Spalten-Anzahl), die davon abhängt, welcher Eintrag in der ersten Zeile steht. Die rekursive Funktion erzeugt die Teilmatrizen, setzt die jeweils ersten Zeilen und ruft zur Berechnung der unteren Block-Matrizen sich selbst auf.

Wie man die Berechnung der Matrix auf eine Rekursion zurückführt, wird unter der Tabelle gezeigt:

1. Da im Beispiel n = 3 ist, werden drei Matrizen gebildet, die am Ende spaltenweise aneinandergehängt werden.
2. Um die erste Zeile dieser Matrizen zu erzeugen, müssen die Elemente aus M mit gewissen Häufigkeiten der Reihe nach angeordnet werden.
3. Die Häufigkeit richtet sich danach, wie wie viele Kombinationen es mit einer 1, 2 beziehungsweise 3 an erster Stelle gibt. Die Häufigkeit berechnet sich mit Hilfe der Funktion C(n, k):
   • Steht eine 1 an erster Stelle, können die weiteren Elemente wieder aus der Menge M gewählt werden, aber die Fortsetzungen der Kombinationen haben nur noch die Länge k - 1. Die Anzahl der entsprechenden Kombinationen ist daher C({1, 2, 3}, k = 3).
   • Steht eine 2 an erster Stelle, kann keine 1 mehr in der Kombination auftreten. Die Anzahl der Kombinationen mit führender 2 ist daher C({2, 3}, k = 3).
   • Steht eine 3 an erster Stelle, müssen alle weiteren Elemente ebenfalls gleich 3 sein; es gibt nur eine Auswahl.
4. Mit diesen Angaben kann man jeweils die erste Zeile der 3 Teilmatrizen berechnen, sie bestehen aus 3 Blöcken der Zahlen 1, 2 beziehungsweise 3. Die Berechnung der Matrix unterhalb der Blöcke kann jetzt rekursiv erfolgen, da man jeweils die Menge kennt, aus der die Elemente ausgewählt werden und die Länge der verbleibenden Auswahl.
5. Die Teilmatrizen werden spaltenweise zusammengefügt.

Der Quelltext

Der folgende Quelltext realisiert die rekursive Funktion aus obiger Beschreibung; sie erhält den Namen combinations().

Nach den Erklärungen zu Abbildung 6 wird man erwarten, dass für die Elemente, aus denen die Auswahl getroffen wird, eine Menge als Eingabewert zur Verfügung steht – wobei eine Menge in R als Vektor realisiert wird. Dies hätte aber den Nachteil, dass man eine Menge wie c(1, 1, 2) eingeben kann; dann müsste aber klären, wie dies zu verstehen ist. Einfacher ist es daher für die Menge den Start- und Endwert einzugeben. Dann müssen die Mengen nicht die Gestalt (1:n) haben, mehrfache Einträge sind aber ausgeschlossen.

Der Rückgabewert ist eine Matrix mit k Zeilen und end - start + 1 Zeilen.

combinations <- function(start = 1L, end = 2L, k = end){
  start <- as.integer(start)
  end <- as.integer(end)
  k <- as.integer(k)
  delta <- end - start
  stopifnot(start > 0, delta > -1, end > 0, k > 0)
  # Abbruchbedingungen:
  if(identical(k, 1L)){
    return( matrix(data = (start:end), nrow = 1, byrow = TRUE) )
  }
  if(identical(delta, 0L)){
    return( matrix(data = rep(x = start, times = k), ncol = 1, byrow = FALSE) )
  }
  # Matrizen: je eine für start, ..., end;
  matrices <- vector(mode = "list", length = delta + 1L)
  
  for(i in (start:end)){
    v <- rep(x = i, times = StarsBars(end - i + 1, k-1L))
    matrices[[i]] <- rbind(v , combinations(start = i, end = end, k = k-1L))
    dimnames(matrices[[i]]) <- NULL
  }
  # Zusammnefügen der Matrizen und Rückgabe:
  return(Reduce(x = matrices, f = cbind))
}

Zur Erklärung:

Zeile 1: Die Menge, aus der die Auswahl getroffen wird, ist durch Anfangs- und Endwert charakterisiert; die Anzahl der auszuwählenden Elemente wird wieder mit k bezeichnet.

Zeile 2 bis 6: Da man später öfters identical() aufrufen muss, ist es besser, wenn sichergestellt ist, dass alle Zahlen den Speichermodus integer besitzen.

Zeile 5: Die Variable delta hätte in der bisher verwendeten Nomenklatur den Wert n-1; später wird im Quelltext daher delta + 1 verwendet (Zeile 15).

Zeile 7 bis 13: Es gibt zwei Abbruchbedingungen, für die man sofort die Matrix angeben kann:

1. Falls k = 1, besteht die Matrix aus einer Zeile mit den Werten start, ..., end (siehe Zeile 9).
2. Falls n = 1 (also start = end oder delta = 0), gibt es nur einen Wert zur Auswahl und dieser muss k-mal ausgewählt werden. Die zugehörige Matrix besitzt eine Spalte der Länge k (siehe Zeile 12).

Zeile 15: Für jedes Element start, ..., end wird eine Teilmatrix vorbereitet; sie werden zu einer Liste zusammengefasst.

Zeile 17 bis 21: Das Herzstück des Algorithmus, das in Abbildung 6 oben erklärt wurde. Man iteriert mit dem Index i über die Elemente start, ..., end. In den Teilmatrizen wird jeweils die erste Zeile gesetzt; der Rest der Matrix wird durch den rekursiven Aufruf von combinations() gesetzt. Dazu muss die Funktion combinations() richtig konfiguriert werden: Der Wert start ist jetzt gleich i (entlang einer Spalte dürfen die Einträge nicht kleiner werden), end bleibt unverändert und k wird um 1 verringert.

Zeile 23: Mit Hilfe von Reduce() werden die Teilmatrizen spaltenweise aneinandergehängt.

Beim Aufruf von combinations() wird dann eine Matrix ohne dimnames gebildet (siehe Zeile 20):

combinations(start = 1, end = 3, k = 4)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15]
# [1,]    1    1    1    1    1    1    1    1    1     1     2     2     2     2     3
# [2,]    1    1    1    1    1    1    2    2    2     3     2     2     2     3     3
# [3,]    1    1    1    2    2    3    2    2    3     3     2     2     3     3     3
# [4,]    1    2    3    2    3    3    2    3    3     3     2     3     3     3     3

Man erkennt, dass die Auswahlen in lexikographischer Anordnung in die Matrix eingefügt werden. Dies liegt daran, dass die for-Schleife von start bis end durchlaufen wird. Dreht man hier die Richtung um, wird auch die Anordnung der Auswahlen vertauscht.

Die Berechnung aller Partitionen der Länge n einer Zahl k

Es gibt jetzt zwei einfache Möglichkeiten, eine Funktion zu implementieren, die zu gegebenem n und k die Menge aller Partitionen von k der Länge n berechnet:

1. Entweder man geht ähnlich vor wie oben bei der Funktion combinations() und implementiert eine geeignete Rekursion.
2. Oder man verwendet die Funktion combinations() und die oben beschriebene Umformulierung von Auswahlen "k aus n mit Wiederholungen" in Partitionen.

Für den zweiten Ansatz wird hier mit der Funktion partitions() eine Lösung gezeigt. Sie besitzt 3 Eingabewerte:

partitions(k = 5L, n = 1L, printSB = FALSE)

1. Die Zahl k soll in Summanden zerlegt werden.
2. Die Länge n der Partition.
3. Die Angabe, ob die Menge der Partitionen als "Stars and Bars" auf der Konsole ausgegeben werden sollen (Beispiel siehe unten).

Dar Rückgabewert von partitions() ist wieder eine Matrix, die sämtliche Partitionen von k mit Länge n enthält. Wie in Abbildung 4 werden die Partitionen jetzt zeilenweise angeordnet – dies geschieht lediglich zur besseren Unterscheidung von den Kombinationen mit Wiederholungen.

Die Vorgehensweise ist nach den Erklärungen zur Funktion combinations() und dem Zusammenhang zwischen Kombinationen mit Wiederholungen und Partitionen nicht mehr schwer:

1. Mit combinations() wird eine Matrix m.combn der Kombinationen berechnet (Zeile 3).
2. Es wird eine Matrix m.part für die Partitionen vorbereitet, so dass pro Zeile eine Partition steht. Sie hat daher C(n, k) Zeilen und n Spalten (Zeile 5 und 6).
3. Man iteriert über die Spalten von m.combn, so dass jede Kombination eine Partition liefert, die als Zeile der Matrix m.part gesetzt wird (Zeile 8 bis 13).
4. Falls der Eingabewert printSB gesetzt ist, werden die entsprechenden Konsolen-Ausgaben erzeugt (Zeile 15 bis 29).

partitions <- function(k = 5L, n = 1L, printSB = FALSE){
  # Matrix der Kombinationen:
  m.combn <- combinations(end = n, k = k)
  # Matrix der Partitionen (jede Zeile eine Part.):
  C.n.k <- StarsBars(n = n, k = k)
  m.part <- matrix( data = 0, nrow = C.n.k, ncol = n )

  for(i in (1:C.n.k)){
    for(j in (1:n)){
      # Berechnung der Häufigkeiten:
      m.part[C.n.k + 1 - i, j] <- length( which( m.combn[ , i] ==  j ) )
    }
  }
  # eventuell: Ausgabe Stars and Bars
  if(printSB){
    cat("Stars and Bars: \n")
    for(i in (1:C.n.k)){
      v <- vector(mode = "character", length = n)
      # Zeile der Matrix m.part untersuchen und String bilden:
      for(j in (1:n)){
        if( identical(m.part[i, j], 0) ){
          v[j] <- ""
        } else {
          v[j] <- paste(rep("*", times = m.part[i, j]), collapse = "")
        }
      }
      cat(paste(v, sep = "", collapse = "|"), "\n")
    }
  }
  return(m.part)
}

Zur genaueren Erklärung:

Zeile 11: Die wichtigste und gleichzeitig am schwersten zu verstehende Anweisung der Funktion partitions() ist die Übersetzung einer Kombination in eine Partition. Dazu wird auf der rechten Seite die i-te Zeile von m.combn untersucht. Es wird geprüft, wie oft der Wert j in der Kombination vorkommt (j durchläuft dabei die Zahlen von 1 bis n). Diese Häufigkeit wird der Komponente m.part[C.n.k + 1 - i, j] zugewiesen. Naheliegender wäre vermutlich m.part[i, j] . Aber dann werden die Partitionen nicht in lexikographischer Anordnung erzeugt, sondern genau umgekehrt. Insgesamt erzeugt die Doppelschleife über i und j sämtliche Einträge in der Matrix für die Partitionen.

Zeile 24: Zu einem Summanden der Partition wird die entsprechende Anzahl von * erzeugt (oder der leere String in Zeile 22).

Zeile 27: Zwischen den * werden die | plaziert.

Die bereits mehrfach besprochenen Partitionen von k = 4 der Länge 3 werden erzeugt mit:

partitions(k = 4, n = 3, printSB = TRUE)

Stars and Bars: 
||**** 
|*|*** 
|**|** 
|***|* 
|****| 
*||*** 
*|*|** 
*|**|* 
*|***| 
**||** 
**|*|* 
**|**| 
***||* 
***|*| 
****||

#    [,1] [,2] [,3]
# [1,]    0    0    4
# [2,]    0    1    3
# [3,]    0    2    2
# [4,]    0    3    1
# [5,]    0    4    0
# [6,]    1    0    3
# [7,]    1    1    2
# [8,]    1    2    1
# [9,]    1    3    0
# [10,]    2    0    2
# [11,]    2    1    1
# [12,]    2    2    0
# [13,]    3    0    1
# [14,]    3    1    0
# [15,]    4    0    0

Aufgabe: Implementieren Sie eine Funktion, die die Aufgabe von partitions() erfüllt, aber nicht auf combinations() zurückgreift.