🎓 Ui, schon PrĂŒfungszeit? Hier geht's zur Mathe-PrĂŒfungsvorbereitung.
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 5⋅6=305\cdot 6=30 Möglichkeiten fĂŒr die ersten beiden Perlen). Insgesamt ergeben sich 6⋅5⋅4⋅3⋅2⋅16\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!=1⋅2⋅3⋅
⋅nn!=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+k−1k)\begin{pmatrix}n+k-1\\k\end{pmatrix}

ohne ZurĂŒcklegen

n!(n−k)!\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!(20−15)!=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+3−13)=(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

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.0 → Was bedeutet das?