Inhaltsverzeichnis
Beispiel: Kleidungsstücke kombinieren
Du stehst vor dem Kleiderschrank und möchtest dir ein Outfit aus Hose und Oberteil zusammenstellen. Du findest im Schrank drei Hosen und vier Oberteile vor. Wie viele Outfits sind möglich? Lösung: Du kannst jede der drei Hosen mit jedem der vier Oberteile kombinieren, also gibt es $3\cdot 4=12$ verschiedene Outfits.
Was hier völlig einleuchtend klingt, ist eine Anwendung der Produktregel der Kombinatorik. Diese sagt, wie viele Paare man aus den Elementen zweier Mengen bilden kann, wenn jedes Paar erlaubt ist. Das wollen wir jetzt etwas mathematischer beschreiben.
Mächtigkeit einer Menge
Die Anzahl der Elemente in einer Menge $M$ wird mit $|M|$ bezeichnet. Wir nennen sie die Mächtigkeit von $M$.
Beispiele:
- Beim Werfen eines Würfels ist die Ergebnismenge $\Omega=\{1;2;3;4;5;6\}$. Es ist $|\Omega|=6$.
- Wenn $O$ die Menge der Oberteile im Kleiderschrank ist, dann ist $|O|=4$.
- Wenn $H$ die Menge der Hosen im Kleiderschrank ist, dann ist $|H|=3$.
Paare von Elementen
Wenn wir eine Hose $h\in H$ und ein Oberteil $o\in O$ auswählen, bilden wir mathematisch gesehen ein Paar $(h,o)$. Dieses Paar, gebildet aus Hose und Oberteil, ist ein neues Element. Und alle möglichen Paare bilden eine neue Menge, wir schreiben sie als $H\times O$ und nennen sie das kartesische Produkt (oder einfach Produktmenge) von $H$ und $O$:
$$H\times O = \{\ (h,o)\ |\ h\in H\text{ und }o\in O\}$$
Diese Definition liest man in Worten so: „$H\times O$ ist die Menge aller Paare $(h,o)$, für die gilt, dass $h$ ein Element von $H$ und $o$ ein Element von $O$ ist.“
Die Frage nach der Anzahl möglicher Outfits können wir mathematisch nun so formulieren: Wie viele Elemente enthält $H\times O$? Und die Antwort hierauf liefert die Produktregel:
Produktregel der Kombinatorik
Soll aus der Menge $H$ ein Element $h$ und aus der Menge $O$ ein Element $o$ ausgewählt werden, so gibt es insgesamt $|H|\cdot |O|$ mögliche Paare $(h,o)$, wenn jedes Element aus $H$ mit jedem Element aus $O$ kombiniert werden kann.
Mit der Schreibweise des kartesischen Produktes führt das zu folgender sehr eingängigen Schreibweise:
$$|H\times O|=|H|\cdot|O|$$
In Worten: Die Mächtigkeit der Produktmenge ist gleich dem Produkt der Mächtigkeiten der einzelnen Mengen.
Die Produktregel mit mehr als zwei Mengen
Die Produktregel gilt auch, wenn man Elemente aus mehr als zwei Mengen kombiniert. Die ausgewählten Elemente bilden dann nicht mehr Paare, sondern Tripel oder allgemein Tupel, aber die Produktregel gilt entsprechend:
$$|A\times B\times C|=|A|\cdot |B|\cdot|C|$$
Beispiel: Ein Bettwaren-Fachgeschäft bietet eine Daunendecke in drei Qualitäten, vier Wärmestufen und fünf Größen an. Aus wie vielen verschiedene Decken kann man dort auswählen?
Lösung: Nach der Produktregel gibt es insgesamt $3\cdot 4\cdot 5 = 60$ verschiedene Decken zur Auswahl.
Paare aus der gleichen Menge
Es können auch beide Elemente eines Paares aus der gleichen Menge stammen. Wenn $\Omega=\{1;2;3;4;5;6\}$ die Ergebnismenge eines einzelnen Würfelwurfs ist, dann ist $\Omega\times\Omega$ die Menge aller Paare von Würfelergebnissen. Oder anders gesagt: $\Omega\times\Omega$ beschreibt die möglichen Ergebnisse beim zweimaligen Werfen eines Würfels:
$$\Omega\times\Omega=\{(1;1),(1;2),(1;3),…,(6;6)\}$$
Wenn wir alle Paare von Würfelergebnissen auflisten, erfahren wir, wie viele Ergebnisse $\Omega\times\Omega$ enthält. Oder wir wenden die Produktregel an:
$$|\Omega\times\Omega|=|\Omega|\cdot|\Omega|=6\cdot 6=36$$
Mit zwei Würfen sind also insgesamt 36 verschiedene Ergebnisse möglich.
Entsprechend mit 4 Würfen: $$|\Omega\times\Omega\times\Omega\times\Omega|=|\Omega|^4=6^4=1296$$
Wir sehen, dass Ergebnismengen mehrstufiger Experimente schnell sehr groß werden. Diesem Umstand wollen wir im Kapitel Zufallsgrößen Herr werden. Und außerdem haben wir nebenbei unsere erste Kombinatorik-Formel hergeleitet: die Anzahl möglicher Ergebnisse bei einer geordneten Stichprobe mit Wiederholung. Auch die anderen Kombinatorik-Formeln sind mehr oder weniger Anwendungen der Produktregel.
Wann kann man die Produktregel nicht anwenden?
Die Produktregel der Kombinatorik gilt nur, wenn die zweite Entscheidung unabhängig von der ersten getroffen werden kann. Für das Outfit bedeutet das: Jede Hose kann mit jedem Oberteil kombiniert werden. Wenn jedoch zu der dunkelbraunen Jeans nur zwei Oberteile passen und zum blauen T-Shirt nur ein passendes Beinkleid zur Verfügung steht, dann hilft die Produktregel nicht weiter, und man muss die möglichen Kombinationen anders ermitteln – zum Beispiel mit Durchzählen oder Subtrahieren der ungültigen Kombinationen.
