Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Kombinatorik

Die Kombinatorik beschäftigt sich mit der Anzahl der möglichen Anordnungen bei einem Versuch, wobei sie unterscheidet, ob die Reihenfolge von Bedeutung ist oder nicht und ob Wiederholungen (Zurücklegen) zugelassen werden oder nicht. Meist lässt sich die Berechnung der Möglichkeiten mithilfe des Urnenmodells durchführen.

Permutationen

Man stellt sich eine Menge von Objekten vor, zum Beispiel eine rote, gelbe, blaue, grüne, orange und weiße Kugel. Diese Elemente kann man (wie Perlen auf einer Kette) anordnen. Zum Beispiel so:

Bild

Jede solche Anordnung wird Permutation genannt, was so viel bedeutet wie Umordnung oder Vertauschung (eine andere Permutation erhalte ich zum Beispiel, wenn ich Weiß und Grün vertausche).

Nun interessiert man sich dafür, wie viele verschiedene Permutationen man bei einer gegebenen Anzahl von Elementen bilden kann (bzw. wie viele verschiedene Perlenkettenmuster es gibt, wenn die Anzahl unterschiedlicher Perlen vorgegeben ist).

  1. Dazu "fädelt" man zunächst das erste Element auf und überlegt sich, wie viele Möglichkeiten für dieses erste Element zur Verfügung stehen.

  2. Für das erste Element gibt es so viele Möglichkeiten, wie es Elemente gibt. Bei der obigen Perlenmenge sind das 6 Elemente, also 6 Möglichkeiten.

  3. Nun ist das zweite Element an der Reihe: Für das zweite Element steht, ein Element weniger zur Verfügung, weil dieses bereits an erster Stelle steht. Es gibt also dafür 5 Möglichkeiten

  4. ...

  5. Man "fädelt" weiter, bis man das letzte Element erreicht hat.

  6. Da nur noch ein Element übrig ist, gibt es auch nur noch eine Möglichkeit.

Da man für jede der 6 Möglichkeiten bei der Auswahl der ersten Perle genau 5 Möglichkeiten habe, die nächste Perle auszuwählen, ergibt sich die Gesamtzahl der Möglichkeiten als Multiplikation (so gibt es 56=305\cdot 6=30 Möglichkeiten für die ersten beiden Perlen). Insgesamt ergeben sich 6543216\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1 Möglichkeiten für verschiedene Permutationen.

Allgemein ausgedrückt hat eine Menge mit nn Elementen genau n!n! (n-Fakultät) verschiedene Permutationen, wobei n!=123nn!=1 \cdot 2\cdot 3\cdot \ldots \cdot n bedeutet.

Beispiel

Urnenmodell

Die Anzahl der Möglichkeiten kk Kugeln aus einer Urne mit nn Kugeln zu ziehen ist abhängig davon, ob man beachtet, in welcher Reihenfolge die Kugeln gezogen werden und davon, ob man zulässt, dass die Kugeln nach dem Ziehen zurückgelegt werden dürfen oder nicht.

mit Beachtung der Reihenfolge

ohne Beachtung der Reihenfolge

mit Zurücklegen

nkn^k

(n+k1k)\begin{pmatrix}n+k-1\\k\end{pmatrix}

ohne Zurücklegen

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

(nk)\begin{pmatrix}n\\k\end{pmatrix}

Du findest hier einen Artikel zum Urnenmodell mit weiteren Erläuterungen und Beispielen.

Der Binomialkoeffizient ist ein Rechenausdruck, der oft in der Kombinatorik verwendet wird.

Wichtige Begriffe aus der Kombinatorik

kk-Tupel

Ein kk-Tupel ist eine Zusammenfassung von kk Zahlen, die sich wiederholen dürfen, und deren Reihenfolge wichtig ist.

Zum Beispiel: (1,2,3,4)(1{,}2,3{,}4) ist ein 44-Tupel und es gilt (1,2,3,4)(1,2,4,3)(1{,}2,3{,}4)\ne(1{,}2,4{,}3).

In der Tabelle gibt die Zelle "mit Reihenfolge, mit Zurücklegen" die Antwort auf die Frage: Wie viele kk-Tupel gibt es, deren Einträge man aus n verschiedenen Elementen wählen kann?

kk-Permutationen

Eine kk-Permutation ist eine Zusammenfassung von kk Zahlen, die sich nicht wiederholen dürfen, und deren Reihenfolge wichtig ist. kk-Permutationen sind damit ein Spezialfall von kk-Tupeln.

Zum Beispiel: (1,2,3,4)(1{,}2,3{,}4) ist eine 44-Permutation, aber (1,2,3,3)1{,}2,3{,}3) nicht, da die 33 doppelt vorkommt.

In der Tabelle gibt die Zelle "mit Reihenfolge, ohne Zurücklegen" die Antwort auf die Frage: Wie viele kk-Permutationen gibt es, deren Einträge man aus nn verschiedenen Elementen wählen kann?

kk-Mengen

Eine kk-Menge ist eine Zusammenfassung von kk Zahlen, wobei weder Wiederholungen noch die Reihenfolge beachtet werden.

Zum Beispiel: {6,6,5}={6,5}\{6, 6, 5\} = \{6{,}5\} und {7,3,1}={1,3,7}\{7, 3, 1\} = \{1, 3, 7\}

In der Tabelle gibt die Zelle "ohne Reihenfolge, ohne Zurücklegen" die Antwort auf die Frage: Wie viele kk-Mengen gibt es, deren Einträge man aus nn verschiedenen Elementen wählen kann?

kk-Kombinationen

Eine kk-Kombination ist eine Zusammenfassung von kk Zahlen, wobei die Reihenfolge nicht beachtet wird, es aber Wiederholungen gibt. kk-Kombinationen sind damit ein Spezialfall von kk-Mengen.

Zum Beispiel: {6,6,5}{6,5}\{6, 6, 5\} \ne \{6{,}5\} und {7,3,1}={1,3,7}\{7, 3, 1\} = \{1, 3, 7\}

In der Tabelle gibt die Zelle "ohne Beachtung der Reihenfolge, mit Zurücklegen" die Antwort auf die Frage: Wie viele kk-Kombinationen gibt es, deren Einträge man aus nn verschiedenen Elementen wählen kann?

Beispiele

  1. Lotto-Spiel: Es gibt (496)\binom{49}{6} Möglichkeiten, aus den Zahlen 1,2,,491{,}2,…,49 (n=49n=49) sechs Zahlen (k=6k=6) anzukreuzen. (Ohne Zurücklegen, denn nach jedem Kreuz ist die Zahl weg. Ohne Reihenfolge, denn es ist egal, welche Zahl wann angekreuzt wird.)

  2. Es gibt 20!(2015)!=20!5!\frac{20!}{(20-15)!}=\frac{20!}{5!} Möglichkeiten, 1515 Schüler auf 2020 Sitzplätze zu verteilen. (Ohne Zurücklegen, denn ein Schüler kann nicht auf 22 Plätzen sitzen. Mit Reihenfolge, da es wichtig ist, wer auf welchem Platz sitzt.)

  3. Es gibt (5+313)=(73)\binom{5+3-1}{3}=\binom{7}{3} Möglichkeiten, drei Bärchen (k=3k=3) aus einer Tüte mit Gummibärchen auszuwählen, wenn es fünf verschiedene Gummibärchenfarben gibt. (Mit Zurücklegen, denn man wählt zuerst aus 55 verschiedenen Farben eine aus. Für das zweite Bärchen darf diese Farbe aber auch wieder gewählt werden. Ohne Beachtung der Reihenfolge, denn es ist egal, welches Gummibärchen welche Farbe erhält.)

  4. Bei einem Zahlenschloss mit 55 Stellen (k=5k=5) gibt es 10510^5 Möglichkeiten für die Zahlenkombination.(Man zieht 55 Mal aus einer Urne mit 1010 unterscheidbaren Kugeln (Ziffern 0,1,,90{,}1,…,9) wobei man nach jedem Ziehen die Kugel wieder zurücklegt und später die Reihenfolge beachtet, in der die Ziffern stehen.)

Übungsaufgaben: Kombinatorik

Weitere Aufgaben zum Thema findest du im folgenden Aufgabenordner:
Aufgaben zur Kombinatorik im typischen Sinn

Du hast noch nicht genug vom Thema?

Hier findest du noch weitere passende Inhalte zum Thema:

Artikel


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?