Kombinatorik - das geschickte Abzählen


Gibt es bei bestimmten Versuchsanordnungen viele unterscheidbare Fälle, so ist ein Abzählen häufig nur möglich, wenn man ein passendes Zählmodell benutzt. Insbesondere beim Berechnen von Wahrscheinlichkeiten mithilfe des Laplace-Satzes tritt oft die Notwendigkeit zur Ermittlung der Mächtigkeit von Mengen auf, denn die Wahrscheinlichkeit eines Ereignisses A ist dann

Beispiel:

Wie groß ist die Wahrscheinlichkeit, dass sich bei zufälliger Anordnung aus den Buchstaben I,I,I,I,M,P,P,S,S,S,S das Wort MISSISSIPPI ergibt?

Die Anzahl aller (gleichwahrscheinlichen) Anordnungen von 11 Buchstaben auf 11 Plätzen ergibt |W| . Da hier genau der Fall der Permutationen von 11 verschiedenen Elementen auf 11 Plätzen vorliegt, gilt |W| = 11!. Da sich das Wort MISSISSIPPI bei den verschiedenen Reihenfolgen der vier I, der vier S und die zwei P nicht ändert, ergibt sich die Anzahl der günstigen Fälle mit dem Modell der Permutationen mit identifizierten Elementen zu |A| = 11!/ (4! 4! 2!).

Also ist die gesuchte Wahrscheinlichkeit

Es sollen im Folgenden die Standardmodelle für Permutationen, Permutationen mit identifizierten Elementen und Kombinationen hergeleitet werden. Kann man in einem Anwendungsbeispiel zeigen, dass die Aufgabe (oder ein Teil davon) auf ein solches Standardmodell zurückzuführen ist, kann in bequemer Weise durch Benutzung der betreffenden Formel die Zählerei durchgeführt werden.

Permutationen

Gesucht ist die Anzahl aller Anordnungsmöglichkeiten von n verschiedenen Elementen auf n Plätzen.
Zur Veranschaulichung wird ein n-stelliges Register gewählt. Die einzelnen Felder des Registers werden mit den n Elementen - z.B. den Zahlen von 1 bis n - belegt. Die Anzahl aller möglichen Registerbelegungen ist gesucht. Beispiel-Belegungen für n=11:

Zum Abzählen der möglichen Belegungen beginnt man systematisch die möglichen Belegungen zu zählen. Dabei wird mit dem linken Feld begonnen und dann Feld um Feld nach rechts vorgerückt.
Für das linke Feld gibt es n Belegungen.
Für das folgende Feld gibt es jeweils noch (n-1) Belegungen.
Für die beiden ersten Felder damit insgesamt n(n-1) Belegungen.
Für das folgende Feld gibt es jeweils noch (n-2) Belegungen.
Für die ersten 3 Felder damit [n(n-1)](n-2) = n(n-1)(n-2) Belegungen.
Dieses Verfahren lässt sich offensichtlich bis zum letzten Feld fortsetzen. Als Anzahl aller Belegungen P(n) ergibt sich schließlich

P(n)= n(n-1)....1 = n!.

Permutationen mit identifizierten Elementen - Kombinationen

Wieder sollen n Elemente auf n Plätzen angeordnet werden. Aber nun sollen m von den n Elementen ununterscheidbar (identifiziert) sein. Damit verringert sich die Anzahl aller Anordnungen, denn alle Fälle, die sich bei den gewöhnlichen Permutationen nur durch verschiedene Anordnungen dieser m Elemente unterscheiden, ziehen sich zu jeweils einem Fall zusammen. Jeweils m! Fälle ergeben nur einen Fall. Insgesamt ergibt sich damit für die Anzahl der Permutationen von n Elementen bei m identifizierten

Analog wird vorgegangen, wenn m,r,s der n Elemente jeweils identifiziert sind. Für die Anzahl der Anordnungen ergibt sich dann

Ein Spezialfall ist bei den Permutationen von besonderer Bedeutung: Die n Elemente ergeben sich aus 2 Mengen jeweils identifizierter Elemente. Es sind also m Elemente und der Rest, nämlich (n-m), jeweils identifiziert. Dann ergibt sich nach der obenstehenden Formel

Für diesen Spezialfall wird der Binomialkoeffizient als Schreibweise eingeführt. Es wird definiert

Es gelten folgende Sätze:

Standardweg zur Lösung kombinatorischer Abzählprobleme

Beim Lösen eines Kombinatorikproblems kann man versuchen, in folgenden Schritten vorzugehen:

Beispiel:

In einer Urne liegen 9 Kugeln. Wieviele Möglichkeiten gibt es, 6 Kugeln (ohne Rücklegen der gezogenen Kugeln) zu entnehmen? D.h., wieviele verschiedene 6er-Mengen kann man entnehmen?

Lösung:

1. Schritt
Die Kugeln werden mit 1 bis 9 nummeriert. Zur Vorbereitung des Übersetzungsvorganges in Registeranzeigen werden einige Ziehungsfälle notiert: {1,3,8,4,9,2}, {1,2,3,6,5,8}, {9,8,7,1,4,2},... - Die Menge {1,2,3,4,8,9} ist kein neuer Fall !

2. Schritt
Es wird ein 9-stelliges Register gewählt; jede Stelle steht für eine Kugel. Wird eine Kugel gezogen, so erhält die zugeordnete Stelle eine 1. Die andern Stellen erhalten eine 0. Damit kann jeder Ziehungsfall eineindeutig einer Registeranzeige mit Nullen und Einsen zugeordnet werden. Die obigen 3 Fälle ergeben die Registeranzeigen

3. Schritt
Damit kann im Register gezählt werden. Von den 9 Elementen sind 6 und (9-6) identifiziert. Die Anzahl aller Anordnungen ist also gerade die Anzahl der Permutationen

Das Ziehen von Kugeln aus einer Urne liefert also einen Fall für Kombinationen.

Eine kleine Änderung des Urnenproblems:
Wieder werden 6 der nummerierten Kugeln entnommen und dieses Mal werden die Zahlen nach der Ziehungsreihenfolge aufgeschrieben - es ergibt sich eine 6-stellige Zahl. Wieviele verschiedene 6-stellige Zahlen können gezogen werden?

Lösung:
Nun sind 138492 und 123489 verschiedene Fälle. Hat man die Lösung des ersten Problems gefunden, so kann das neue Problem so gelöst werden: Da jeder Fall des alten Problems 6! Fälle des neuen Problems liefert (Anordnungen von 6 verschiedenen Elementen auf 6 Plätzen), ist die gesuchte Anzahl