Kombinatorik

Dieses Kapitel dient als Einführung in die Kombinatorik.

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

Bei einer Anordnung (Permutation) werden alle Elemente der Grundmenge betrachtet, wohingegen bei Auswahlen (Variationen oder Kombinationen) nur eine Stichprobe der Grundmenge im Fokus des Interesses liegt.

Es gibt geordnete und ungeordnete Stichproben, je nachdem, ob die Reihenfolge der Elemente berücksichtigt wird (Variation) oder nicht (Kombination). Bei Anordnungen (Permutationen) wird dagegen immer die Reihenfolge berücksichtigt.

Permutation

  • \(k = n\)
    (d.h. es werden alle Elemente \(k\) der Grundmenge \(n\) betrachtet)
  • Reihenfolge der Elemente wird berücksichtigt

Variation

  • \(k < n\)
    (d.h. es wird nur eine Stichprobe - also \(k\) Elemente der Grundmenge \(n\) - betrachtet)
  • Reihenfolge der Elemente wird berücksichtigt
    -> Variation = geordnete Stichprobe

Kombination

  • \(k < n\)
    (d.h. es wird nur eine Stichprobe - also \(k\) Elemente der Grundmenge \(n\) - betrachtet)
  • Reihenfolge der Elemente wird nicht berücksichtigt
    -> Kombination = ungeordnete Stichprobe

Weiterhin gilt es bei Permutationen, Variationen und Kombinationen jeweils zwei Fälle zu unterscheiden: Sind die Objekte untereinander unterscheidbar, so spricht man von einer Permutation/Variation/Kombination "ohne Wiederholung" (derselben Objekte). Falls die Objekte jedoch nicht unterscheidbar sind, spricht man von einer Permutation/Variation/Kombination "mit Wiederholung". Im Urnenmodell sagt man statt "ohne Wiederholung" einfach "ohne Zurücklegen" und zu "mit Wiederholung" entsprechend "mit Zurücklegen".

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.

Allgemeines Zählprinzip

Beispiel

Markus besitzt 3 Paar Schuhe, 2 Hosen und 4 T-Shirts. Wie oft muss er sich anziehen, wenn er alle Kombinationsmöglichkeiten ausprobieren will?

Lösung

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.

Allgemein

Gegegeben seinen k Mengen \(M_1, M_2,\text{...}, M_k\), die jeweils \(n_1, n_2,\text{...}, n_k\) Elemente enthalten, dann lassen sich

\(n_1 \cdot n_2 \cdot \text{...} \cdot n_k\)

verschiedene "k-Tupel" (\(x_1,x_2,\text{...},x_k)\) zusammenstellen.

...doch was ist eigentlich ein k-Tupel?

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.

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 zu diesem Thema findest du im Kapitel "Allgemeines Zählprinzip"! <<

1. Permutationen

  • \(k = n\)
    (d.h. es werden alle Elemente \(k\) der Grundmenge \(n\) betrachtet)
  • Reihenfolge der Elemente wird berücksichtigt

1.1 Permutation ohne Wiederholung

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

Wir haben \(n\) unterscheidbare Objekte, die wir auf \(n\) Plätze in einer Reihe nebeneinander anordnen wollen.

Für das erste Objekt gibt es \(n\) Platzierungsmöglichkeiten. Für das zweite Objekt verbleiben \((n-1)\) Möglichkeiten, für das dritte Objekt \((n-2)\)....und für das letzte Objekt verbleibt nur noch eine Möglichkeit.

In mathematischer Schreibweise sieht das folgendermaßen aus:

\(n \cdot (n-1) \cdot (n-2) \cdot \text{...} \cdot 1 = n!\)

Abkürzend kann man also für eine Permutation ohne Wiederholung \(n!\) schreiben. Dieser Ausdruck heißt "Fakultät".

Beispiel

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Wie viele Möglichkeiten gibt es, die Kugeln in einer Reihe anzuordnen?

Lösung

\(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\)

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

>> Mehr zu diesem Thema findest du im Kapitel zur Permutation ohne Wiederholung. <<

1.2 Permutation mit Wiederholung

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

Wir haben bereits gelernt, dass es \(n!\) Möglichkeiten gibt, um \(n\) unterscheidbare (!) Objekte auf \(n\) Plätze zu verteilen.

Sind jedoch genau \(k\) Objekte identisch, dann sind diese auf ihren Plätzen vertauschbar, ohne dass sich dabei eine neue Reihenfolge ergibt. Auf diese Weise sind genau \(k!\) Anordnungen gleich.

Die Anzahl der Permutationen von \(n\) Objekten, von denen \(k\) identisch sind, berechnet sich zu

\[\frac{n!}{k!}\]

Gibt es nicht nur eine, sondern \(s\) Gruppen, mit jeweils \(k_1, k_2 \cdot \text{...} \cdot k_s\) identischen Objekten, so lautet die Formel

\[\frac{n!}{k_1! \cdot  k_2! \cdot \text{...} \cdot k_s!}\]

Beispiel

In einer Urne befinden sich drei blaue und zwei rote Kugeln. Wie viele Möglichkeiten gibt es, die Kugeln in einer Reihe anzuordnen?

Lösung

\[\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\]

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

>> Mehr zu diesem Thema findest du im Kapitel zur Permutation mit Wiederholung. <<

2. Variationen

  • \(k < n\)
    (d.h. es wird nur eine Stichprobe - also \(k\) Elemente der Grundmenge \(n\) - betrachtet)
  • Reihenfolge der Elemente wird berücksichtigt

2.1 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.

Für das erste Objekt gibt es \(n\) Platzierungsmöglichkeiten. Für das zweite Objekt verbleiben (n-1) Möglichkeiten, für das dritte Objekt (n-2)....und für das letzte Objekt verbleiben noch (n-k+1) Möglichkeiten.

\[n \cdot (n-1) \cdot (n-2) \cdot \text{...} \cdot (n-k+1) = \frac{n!}{(n-k)!}\]

Beispiel

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln ohne Zurücklegen (= ohne Wiederholung) und unter Beachtung der Reihenfolge gezogen werden. Wie viele Möglichkeiten gibt es?

Lösung

\[\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\]

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

>> Mehr zu diesem Thema findest du im Kapitel zur Variation ohne Wiederholung. <<

2.2 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.

Für das erste Objekt gibt es \(n\) Auswahlmöglichkeiten. Da Objekte mehrfach ausgewählt werden dürfen, gibt es auch für das zweite, dritte und k-te Objekt \(n\) Möglichkeiten. Dementsprechend gilt:

\[n \cdot n \cdot \text{...} \cdot n =n^k\]

Beispiel

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln mit Zurücklegen (= mit Wiederholung) und unter Beachtung der Reihenfolge gezogen werden. Wie viele Möglichkeiten gibt es?

Lösung

\[5^3 = 5 \cdot 5 \cdot 5 = 125\]

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

>> Mehr zu diesem Thema findest du im Kapitel zur Variation mit Wiederholung. <<

3. Kombinationen

  • \(k < n\)
    (d.h. es wird nur eine Stichprobe - also \(k\) Elemente der Grundmenge \(n\) - betrachtet)
  • Reihenfolge der Elemente wird nicht berücksichtigt

3.1 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.

Der einzige Unterschied zwischen einer Variation ohne Wiederholung und einer Kombination ohne Wiederholung ist die Tatsache, dass bei der Kombination im - Gegensatz zur Variation - die Reihenfolge der Objekte keine Rolle spielt.

Die Formel für die Variation ohne Wiederholung kennen wir bereits

\[\frac{n!}{(n-k)!}\]

Dabei können die \(k\) ausgewählten Objekte auf \(k!\) verschiedene Weisen angeordnet werden. Da aber die Reihenfolge bei der Kombination unerheblich ist, lautet die Formel entsprechend

\[\frac{n!}{(n-k)! \cdot k!} = {n \choose k}\]

Dabei bezeichnet man \({n \choose k}\) auch als Binomialkoeffizient.

Beispiel

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln ohne Zurücklegen (= ohne Wiederholung) und ohne Beachtung der Reihenfolge gezogen werden. Wie viele Möglichkeiten gibt es?

Lösung

\[{5 \choose 3} = 10\]

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

>> Mehr zu diesem Thema findest du im Kapitel zur Kombination ohne Wiederholung. <<

3.2 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.

Der einzige Unterschied zwischen einer Kombination ohne Wiederholung und einer Kombination mit Wiederholung ist die Tatsache, dass bei der Kombination mit Wiederholung die Objekte auch mehrmals ausgewählt werden können.

Die Formel für die Kombination ohne Wiederholung kennen wir bereits

\[\frac{n!}{(n-k)! \cdot k!} = {n \choose k}\]

Durch eine kleine Modifikation des Zählers und des Nenners gelangen wir schließlich zur Formel für eine Kombination mit Wiederholung

\[\frac{(n+k-1)!}{(n-1)! \cdot k!} = {n+k-1 \choose k}\]

Beispiel

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln mit Zurücklegen (= mit Wiederholung) und ohne Beachtung der Reihenfolge gezogen werden. Wie viele Möglichkeiten gibt es?

Lösung

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

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

>> Mehr zu diesem Thema findest du im Kapitel zur Kombination mit Wiederholung. <<

Kombinatorik-Aufgaben systematisch lösen

Wenn du dich erstmals mit der Kombinatorik beschäftigst, musst du dich zunächst mit den obigen Formel auseinandersetzen und diese üben. In einer Prüfung musst du jedoch nicht nur die Formel beherrschen, sondern auch wissen, wann du welche Formel einsetzen musst. (Nur sehr wenige Lehrer werden neben die Aufgabe schreiben, welcher Fall vorliegt.)

Bei Kombinatorik-Aufgaben stellen sich demnach zwei Fragen:

  1. Welche Formel muss ich in dieser Aufgabe verwenden?
  2. Wie lautet die Formel?

Bei der zweiten Fragestellung hilft nur eins: ÜBEN! (...und auswendiglernen!).

Die wenigsten Schüler und Studenten haben jedoch Probleme beim Auswendiglernen der Formeln. Schwieriger ist es festzustellen, welche Formel bei einer spezifischen Aufgaben angewendet werden muss.

Durch systematisches Vorgehen gelangt man schnell zur richtigen Formel...

Sind alle Elemente der Grundmenge für die Aufgabe relevant?
     (ja) --> Permutation
          Sind alle Elemente voneinander unterscheidbar?
               (ja) --> Permutation ohne Wiederholung
               (nein) --> Permutation mit Wiederholung
     (nein) --> Variation oder Kombination
          Spielt die Reihenfolge eine Rolle?
               (ja) --> Variation
                    Sind alle Elemente voneinander unterscheidbar?
                    (im Urnenmodell: ohne Zurücklegen?)
                         (ja) --> Variation ohne Wiederholung
                         (nein) --> Variation mit Wiederholung
               (nein) --> Kombination
                    Sind alle Elemente voneinander unterscheidbar?
                    (im Urnenmodell: ohne Zurücklegen?)
                         (ja) --> Kombination ohne Wiederholung
                         (nein) --> Kombination mit Wiederholung

Andreas Schneider

Jeden Tag suche ich für dich nach der verständlichsten Erklärung.

Ich hoffe, dass sich meine Arbeit lohnt und ich dir helfen kann.

Weiterhin viel Erfolg beim Lernen!

Dein Andreas

PS: Ich freue mich, wenn du mir mal schreibst!