Übersicht über die Kombinatorik

Beim Lösen von Kombinatorikaufgaben ist es wichtig, den Überblick zu bewahren. Wenn wir uns mit Kombinationen aller Elemente beschäftigen und nicht mit einer Auswahl von Stück aus allen möglichen Elementen, dann handelt es sich um eine klassische Permutation. Hier müssen wir nur noch unterscheiden, ob wir sich wiederholende Elemente haben oder nicht:

Die Anzahl möglicher Permutationen von verschiedenen Objekten ist:

Die Anzahl möglicher Permutationen von Objekten, wovon gleiche Objekte sind, ist:

Wenn wir jetzt aber mit einer Auswahl von Elementen aus den möglichen Elementen zu tun haben, dann benutzen wir den folgenden Quadranten, der uns hilft, die vier möglichen Fälle zu unterscheiden:

Um die richtige Formel zu finden, sollten die beiden folgenden Fragen gestellt werden:

Kriterium: Mit oder ohne Reihenfolge

Handelt es sich um eine -Permutation oder um eine Kombination? Ist die Reihenfolge relevant, d.h. werden Permutationen als einzeln gezählt oder werden sie als nur eins gezählt?

Wir erinnern uns: Die Gold-, Silber- und Bronzemedaille beinhaltet klar eine Reihenfolge. Es ist ein grosser Unterschied, welche Reihenfolge die -Permutation hat:

In der Problemstellung, in welcher die ersten drei Plätze sich qualifizieren, ist die Reihenfolge nicht relevant. Die drei Ersten kommen in den gleichen Topf der Qualifizierten und einzelne Permutationen der drei werden nicht einzeln gezählt, sondern gehören zur gleichen und einzigen Kombination ohne Reihenfolge:

Die Beantwortung der Frage zur Reihenfolge gibt uns die Spalte im Quadranten.

Kriterium: Mit oder ohne Zurücklegen

Können die einzelnen Objekte mehrfach vorkommen oder sind sie einzigartig und können deshalb nur einmal vorkommen? Bei Personen ist eine Wiederholung meistens ausgeschlossen, denn die Person kann meistens nur genau einmal zu einer Gruppe gehören oder nicht. Bei Kugeln, Ziffern, Buchstaben, Zutaten etc. ist es durchaus möglich, dass sie sich wiederholen.

Wenn wir also eine Aufgabenstellung haben wie, «aus einer Klasse von 20 Schülerinnen und Schüler sollen Dreiergruppen gebildet werden…» wird nicht möglich sein, dass der gleiche Schüler mehrfach in einer Gruppe vorkommt. Hier haben wir keine Wiederholung und damit kein «Zurücklegen».

Andererseits sagt uns die Aufgabenstellung «ein Code wird aus den Ziffern 0 bis 9 gebildet…», dann kann der Code durchaus mehrere gleich Ziffern beinhalten, ausser die Aufgabenstellung verbietet dies explizit. Falls die Wiederholung erlaubt ist, haben wir eine Aufgabe mit Zurücklegen, denn wir können die eine Ziffer mehrfach «ziehen».

Die Beantwortung dieser Frage zum Zurücklegen gibt uns die Zeile im Quadranten.

Beispiel

Ein französisches Kartenset hat total 52 Karten mit 4 Farbwerten. Den Spielern werden 5 zufällige Karten verteilt. Wie viele verschiedene Fünfersets sind überhaupt möglich? Wie viele Fünfersets enthalten genau 3 Assen?

Es werden 5 Karten aus 52 gezogen. Wir stellen uns die erste Frage zur Reihenfolge. Hier spielt die Reihenfolge keine Rolle, denn es kommt nicht darauf an, ob ich ein Ass mit der ersten Karte erhalten oder erst mit der Fünften. Die Reihenfolge spielt keine Rolle und wir beschränken uns auf die Kombinationen in der rechten Spalte.

Können Karten zweimal vorkommen? Werden sie gezogen und dann zurückgelegt, bevor sie nochmals gezogen werden? Nein, natürlich nicht. Wir haben hier eine Kombination ohne Zurücklegen, d.h. wir schauen uns den Quadranten rechts oben an.

Jetzt berechnen wir einfach die Anzahl Kombinationen ohne Zurücklegen:

Es gibt rund 3 Millionen verschiedene Fünfersets.

Für die Berechnung der speziellen Fünfersets mit genau 3 Assen, rechnen wir in zwei Schritten. Zuerst brauchen wir die Anzahl Kombinationen, 3 Asse aus total 4 Assen zu kriegen:

Das sind natürlich nur 4 Möglichkeiten, denn es gibt 4 verschiedene Asse, die im Dreierset fehlen können. Nun brauchen wir die Anzahl Kombinationen dafür, zwei Karten aus den verbleibenden 48 Karten zu ziehen:

Warum 48 verbleibende Karten? Nun, wir haben 3 Asse gezogen und möchten jetzt nochmals 2 Karten ziehen, die aber kein Ass sein dürfen. Wir nehmen deshalb das vierte Ass aus dem Spiel, so dass wir nur noch Karten haben.

Gemäss Fundamentalprinzip der Kombinatorik multiplizieren wir die 3-Ass-Kombinationen mit den 2-Nichtass-Kombinationen und erhalten:

Das zweite Resultat ist rund 0.17% vom ersten Resultat, d.h. von allen möglichen Fünfersets, die die Spieler erhalten, steht die Chance genau 3 Assen zu haben bei rund 0.17% der Fälle.