Kombinatorik

Du möchtest wissen, wie viele verschiedene Fünferkombinationen von Karten du aus einem Kartenspiel mit 32 Karten auswählen kannst? Genau diese Art von Aufgaben löst die Kombinatorik. Es gibt zwei kombinatorische Grundregeln – die Summenregel und die Produktregel. Alle weiteren Verfahren sind nur Erweiterungen dieser Grundprinzipien.

Kombinatorische Summenregel

Die Summenregel ist sehr einfach – sie besagt: Haben wir Mengen A, B ohne gemeinsames Element, so ist die Anzahl aller Möglichkeiten, ein Element aus der Vereinigungsmenge A ∪ B auszuwählen, gleich |A| + |B|, also der Summe der Mächtigkeiten der Mengen.

Wir beginnen mit einem leichten Beispiel. Wir haben 6 rote und 8 blaue Kugeln. Diese Kugeln schütten wir in eine Urne. Wie viele Möglichkeiten gibt es insgesamt, wenn wir eine Kugel ziehen? Am Anfang hatten wir die Menge der roten Kugeln, die wir mit A bezeichnen, und die Menge der blauen Kugeln, die wir mit B bezeichnen. Diese Mengen sind disjunkt, d. h. sie haben keine gemeinsame Kugel. Wir wollen eine Kugel ziehen, also haben wir insgesamt |A| + |B| = 6 + 8 = 14 Möglichkeiten. Das ist schon alles.

Kombinatorische Produktregel

Wir haben wieder zwei Mengen, F und M. Die Menge F enthält drei Frauen und die Menge M vier Männer. Nun fragen wir, wie viele verschiedene Paare Mann–Frau wir aus diesen Mengen bilden können. Was wollen wir tun – wir nehmen immer eine Frau und ordnen ihr einen Mann zu. Die Anzahl aller Paare berechnen wir so: Wir nehmen eine Frau, Anna, und ordnen ihr nacheinander alle Männer zu. So erhalten wir 4 verschiedene Paare, weil wir ihr insgesamt 4 verschiedene Männer zuordnen können. Dasselbe machen wir für die übrigen zwei Frauen, auch sie bilden jeweils weitere 4 Paare. Und das war's, wir haben insgesamt 4 + 4 + 4 = 12 Paare.

Was haben wir eigentlich gemacht? Wir haben die Größen beider Mengen multipliziert. Wir hatten 3 Damen und 4 Herren, die Gesamtzahl der Paare ist also 3 · 4 = 12. Daher der Name Produktregel. Haben wir also zwei Mengen, aus denen wir Paare bilden, so multiplizieren wir einfach die Anzahl der Elemente der einen Menge mit der Anzahl der Elemente der anderen Menge.

Weiter kannst du dir ansehen, dass das tatsächlich gilt. Es folgen alle Paare, die wir aus 3 Frauen und 4 Männern bilden können. Jede Zeile stellt die Möglichkeiten für eine der Frauen dar und jede Spalte die Möglichkeiten für einen der Herren. Wir haben also drei Zeilen und vier Spalten, insgesamt Zeilen · Spalten Möglichkeiten.

$$\begin{array}{rcl}& & (F_1,M_1),(F_1,M_2),(F_1,M_3),(F_1,M_4),\\ & & (F_2,M_1),(F_2,M_2),(F_2,M_3),(F_2,M_4),\\ & & (F_3,M_1),(F_3,M_2),(F_3,M_3),(F_3,M_4)\end{array}$$

Gelöste Beispiele

1. Wie viele verschiedene zweistellige Zahlen gibt es? Wie sieht so eine zweistellige Zahl aus? An der ersten Stelle steht eine der Ziffern 1; …; 9, an der zweiten Stelle kann zusätzlich auch die Null stehen: 0; …; 9. In der ersten Menge haben wir also 9 Ziffern, in der zweiten 10. Wir wenden die Produktregel an und erhalten das Endergebnis: 9 · 10 = 90.

• Wie viele verschiedene dreistellige Zahlen gibt es, in denen keine Ziffer zweimal vorkommen darf? An der ersten Stelle können wieder neun Ziffern stehen, mit einer Null kann die Zahl nicht beginnen. An der zweiten Stelle können alle Ziffern einschließlich der Null stehen, aber nicht die Ziffer von der ersten Stelle, also ziehen wir von den zehn möglichen Ziffern eins ab (beginnt unsere dreistellige Zahl zum Beispiel mit einer Vier, ist klar, dass an der zweiten Stelle keine Vier mehr stehen kann, denn sie käme in der ganzen Zahl zweimal vor). An der dritten Stelle können wieder alle Ziffern stehen, aber nicht die Ziffer von der ersten oder von der zweiten Stelle. Der Grund ist wieder derselbe. Steht an der ersten Stelle die Ziffer 4 und an der zweiten die Ziffer 7, so können wir an die dritte Stelle eine Ziffer aus {0; …; 9} ∖ {4; 7} setzen. Von den insgesamt zehn Ziffern müssen wir zwei abziehen. Jetzt multiplizieren wir nur noch 9 · 9 · 8 = 648. Insgesamt gibt es also 648 solche Zahlen.
• Wir werfen zweimal hintereinander einen gewöhnlichen Spielwürfel. Wie viele verschiedene Ergebnisse können wir erhalten? Beim ersten Wurf können auf dem Würfel 6 verschiedene Augenzahlen fallen. Beim zweiten Wurf ebenfalls, die Gesamtzahl der Möglichkeiten ist also 6 · 6 = 36.
• Wir werfen zweimal hintereinander einen Würfel. Wie viele verschiedene Ergebnisse können wir erhalten, wenn beim ersten Wurf eine gerade Zahl gefallen ist? Beim ersten Wurf ist eine gerade Zahl gefallen, d. h. eine der Zahlen 2; 4; 6, das sind insgesamt 3 Möglichkeiten. Beim zweiten Wurf kann jede beliebige Zahl fallen, also haben wir insgesamt 3 · 6 = 18 Möglichkeiten.