Kombinatorik

Dieses Kapitel dient als Einführung in die Kombinatorik.

Inhaltsverzeichnis

Einordnung

Die Kombinatorik hilft bei der Bestimmung der Anzahl möglicher Anordnungen (Permutationen) oder Auswahlen (Variationen oder Kombinationen) von Objekten.

Anordnung vs. Auswahl

Bei einer Anordnung (Permutation) werden alle Elemente der Grundmenge betrachtet.
Bei Auswahlen (Variationen oder Kombinationen) wird nur eine Stichprobe der Grundmenge betrachtet.

Arten von Auswahlen

Eine Auswahl, bei der die Reihenfolge der Elemente berücksichtigt wird, heißt geordnete Stichprobe oder Variation.
Eine Auswahl, bei der die Reihenfolge der Elemente nicht berücksichtigt wird, heißt ungeordnete Stichprobe oder Kombination.

Merke: Bei Anordnungen (Permutationen) wird die Reihenfolge immer berücksichtigt.

Ohne oder mit Wiederholung? Ohne oder mit Zurücklegen?

Bei Permutationen, Variationen und Kombinationen gilt es, jeweils zwei Fälle zu unterscheiden:

Wenn die Objekte untereinander unterscheidbar sind, spricht man von einer Permutation/Variation/Kombination ohne Wiederholung (derselben Objekte). Im Urnenmodell sagt man statt ohne Wiederholung auch ohne Zurücklegen.
Wenn die Objekte nicht unterscheidbar sind, spricht man von einer Permutation/Variation/Kombination mit Wiederholung. Im Urnenmodell sagt man statt mit Wiederholung auch mit Zurücklegen.

Allgemeines Zählprinzip

Bevor wir tiefer in die Kombinatorik eintauchen, schauen wir uns zuerst die Produktregel der Kombinatorik an. Diese Regel ist auch unter dem Begriff Allgemeines Zählprinzip bekannt.

Einführungsbeispiel

Beispiel 1

Markus besitzt 3 Paar Schuhe, 2 Hosen und 4 T-Shirts.

Wie oft muss er sich anziehen, wenn er alle Kombinationsmöglichkeiten ausprobieren will?

Zu jedem seiner 3 Paar Schuhe hat er 2 Möglichkeiten, eine Hose hinzuzufügen: Damit gibt es $3 \cdot 2 = 6$ Schuhe-Hose-Kombinationen.

Zu jeder dieser 6 Möglichkeiten hat er 4 verschiedene T-Shirts zur Auswahl:
Damit gibt es insgesamt $3 \cdot 2 \cdot 4 = 24$ Schuhe-Hose-T-Shirt-Kombinationen.

Definition

Gegeben seien $k$ Mengen $M_1, M_2, \dots, M_k$ , die jeweils $n_1, n_2, \dots, n_k$ Elemente enthalten, dann lassen sich

$$ n_1 \cdot n_2 \cdot \ldots \cdot n_k $$

verschiedene $k$ -Tupel $(x_1, x_2, \dots, x_k)$ zusammenstellen.

Zur Erinnerung: Unter einem $k$ -Tupel versteht man eine Aufzählung von $k$ nicht notwendig voneinander verschiedenen mathematischen Objekten in einer vorgegebenen, festen Reihenfolge aus einer $n$ -Menge.

Beispiel 2

Gehen wir zurück zu unserem Schuhe-Hose-T-Shirt-Beispiel: Die $n$ -Menge sind die 24 verschiedenen Schuhe-Hose-T-Shirt-Kombinationen, die wir berechnet haben. Eine Kombination – z. B. (Schuh 2, Hose 1, T-Shirt 3) – ist dann ein $k$ -Tupel. Dieser Tupel besteht aus dem zweiten Paar Schuhen, der ersten Hose und dem dritten T-Shirt. Ein anderer Tupel wäre (Schuh 3, Hose 2, T-Shirt 2).

Mehr dazu: Allgemeines Zählprinzip

Permutationen

$k$ -Auswahl aus $n$ -Menge (mit $k = n$ )
$\Rightarrow$ Es werden alle Elemente $k$ der Grundmenge $n$ betrachtet.
Reihenfolge der Elemente wird berücksichtigt

Permutation ohne Wiederholung

Eine Permutation ohne Wiederholung ist eine Anordnung von $n$ Objekten, die alle unterscheidbar sind.

$$ n! $$

Herleitung der Formel: Permutation ohne Wiederholung

Der Ausdruck $n!$ wird n Fakultät gesprochen und ist eine abkürzende Schreibweise für $n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 1$ .

Beispiel 3

In einer Urne befinden sich fünf verschiedenfarbige Kugeln.

Wie viele Möglichkeiten gibt es, die Kugeln in einer Reihe anzuordnen?

$$ 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 $$

Es gibt 120 Möglichkeiten fünf verschiedenfarbige Kugeln in einer Reihe anzuordnen.

Permutation mit Wiederholung

Eine Permutation mit Wiederholung ist eine Anordnung von $n$ Objekten, von denen manche nicht unterscheidbar sind.

$$ \frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_s!} $$

Herleitung der Formel: Permutation mit Wiederholung

Beispiel 4

In einer Urne befinden sich drei blaue und zwei rote Kugeln.

Wie viele Möglichkeiten gibt es, die Kugeln in einer Reihe anzuordnen?

$$ \frac{5!}{3! \cdot 2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(3 \cdot 2 \cdot 1) \cdot (2 \cdot 1)}=10 $$

Es gibt 10 Möglichkeiten drei blaue und zwei rote Kugeln in einer Reihe anzuordnen.

Variationen

$k$ -Auswahl aus $n$ -Menge
$\Rightarrow$ Es wird eine Stichprobe betrachtet.
Reihenfolge der Elemente wird berücksichtigt
$\Rightarrow$ Geordnete Stichprobe

Variation ohne Wiederholung

Bei einer Variation ohne Wiederholung werden $k$ aus $n$ Objekten unter Beachtung der Reihenfolge ausgewählt, wobei jedes Objekt nur einmal ausgewählt werden kann.

$$ \frac{n!}{(n-k)!} $$

Herleitung der Formel: Variation ohne Wiederholung

Beispiel 5

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln unter Beachtung der Reihenfolge und ohne Zurücklegen gezogen werden.

Wie viele Möglichkeiten gibt es?

$$ \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} = 5 \cdot 4 \cdot 3 = 60 $$

Es gibt 60 Möglichkeiten 3 aus 5 Kugeln unter Beachtung der Reihenfolge und ohne Zurücklegen zu ziehen.

Variation mit Wiederholung

Bei einer Variation mit Wiederholung werden $k$ aus $n$ Objekten unter Beachtung der Reihenfolge ausgewählt, wobei Objekte auch mehrfach ausgewählt werden können.

$$ n \cdot n \cdot \ldots \cdot n =n^k $$

Herleitung der Formel: Variation mit Wiederholung

Beispiel 6

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln unter Beachtung der Reihenfolge und mit Zurücklegen gezogen werden.

Wie viele Möglichkeiten gibt es?

$$ 5^3 = 5 \cdot 5 \cdot 5 = 125 $$

Es gibt 125 Möglichkeiten 3 aus 5 Kugeln unter Beachtung der Reihenfolge und mit Zurücklegen zu ziehen.

Kombinationen

$k$ -Auswahl aus $n$ -Menge
$\Rightarrow$ Es wird eine Stichprobe betrachtet.
Reihenfolge der Elemente wird nicht berücksichtigt
$\Rightarrow$ Ungeordnete Stichprobe

Kombination ohne Wiederholung

Bei einer Kombination ohne Wiederholung werden $k$ aus $n$ Objekten ohne Beachtung der Reihenfolge ausgewählt, wobei jedes Objekt nur einmal ausgewählt werden kann.

$$ {n \choose k} $$

Herleitung der Formel: Kombination ohne Wiederholung

${n \choose k}$ ist der sog. Binomialkoeffizient.

Beispiel 7

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln ohne Beachtung der Reihenfolge und ohne Zurücklegen gezogen werden.

Wie viele Möglichkeiten gibt es?

$$ {5 \choose 3} = 10 $$

Es gibt 10 Möglichkeiten 3 aus 5 Kugeln ohne Beachtung der Reihenfolge und ohne Zurücklegen zu ziehen.

Kombination mit Wiederholung

Bei einer Kombination mit Wiederholung werden $k$ aus $n$ Objekten ohne Beachtung der Reihenfolge ausgewählt, wobei Objekte auch mehrfach ausgewählt werden können.

$$ {n+k-1 \choose k} $$

Herleitung der Formel: Kombination mit Wiederholung

Beispiel 8

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln ohne Beachtung der Reihenfolge und mit Zurücklegen gezogen werden.

Wie viele Möglichkeiten gibt es?

$$ {5+3-1 \choose 3} = {7 \choose 3} = 35 $$

Es gibt 35 Möglichkeiten 3 aus 5 Kugeln ohne Beachtung der Reihenfolge und mit Zurücklegen zu ziehen.

Aufgaben systematisch lösen

In einer Prüfung reicht es nicht, wenn du die obigen Formeln beherrscht, sondern du musst auch wissen, wann welche Formel zum Einsatz kommt. Nur sehr wenige Lehrer werden in die Aufgabenstellung schreiben, welcher Fall vorliegt.

Wenn du bei einer Aufgabenstellung unsicher bist, welcher Fall vorliegt, kannst du das folgende Schema benutzen, um die richtige Formel zu finden:

Alle Elemente der Grundmenge für die Aufgabe relevant?
    JA $\Rightarrow$ Permutation
        Elemente unterscheidbar? Ohne Wiederholung? Ohne Zurücklegen?
            JA $\Rightarrow$ Permutation ohne Wiederholung
            NEIN $\Rightarrow$ Permutation mit Wiederholung
    NEIN $\Rightarrow$ Variation oder Kombination
        Reihenfolge ist zu berücksichtigen?
            JA $\Rightarrow$ Variation
                Elemente unterscheidbar? Ohne Wiederholung? Ohne Zurücklegen?
                    JA $\Rightarrow$ Variation ohne Wiederholung
                    NEIN $\Rightarrow$ Variation mit Wiederholung
            NEIN $\Rightarrow$ Kombination
                Elemente unterscheidbar? Ohne Wiederholung? Ohne Zurücklegen?
                    JA $\Rightarrow$ Kombination ohne Wiederholung
                    NEIN $\Rightarrow$ Kombination mit Wiederholung