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 auf das Urnenmodell zurückführen.

 

Permutationen

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

Jede solche Anordnung wird Permutation genannt, was so viel bedeutet wie 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 bilden kann bei einer gegebenen Anzahl von Elementen (bzw. wie viele verschiedene Perlenkettenmuster es gibt, bei gegebener Anzahl Perlen).

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.

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.

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.

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

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

Da ich von vorne begonnen, für jede der 6 Möglichkeiten genau 5 Möglichkeiten habe, das nächste Element anzuknüpfen, ergibt sich die Gesamtzahl der Möglichkeiten als Multiplikation (so gibt es %%5\cdot 6=30%% Möglichkeiten für die ersten beiden Perlen). Insgesamt ergeben sich %%6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1%% Möglichkeiten für verschiedene Vertauschungen oder Permutationen.

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

Beispiel

Urnenmodell

Die Anzahl der Möglichkeiten %%k%% Kugeln aus einer Urne mit %%n%% 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

%%n^k%%

%%\begin{pmatrix}n+k-1\\k\end{pmatrix}%%

ohne Zurücklegen

%%\frac{n!}{\left(n-k\right)!}%%

%%\begin{pmatrix}n\\k\end{pmatrix}%%

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

Der Binomialkoeffizient ist eine Formel, die oft in der Kombinatorik verwendet wird.

Wichtige Begriffe aus der Kombinatorik

%%k%%-Tupel

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

Zum Beispiel:
(1,2,3,4) ist ein 4-Tupel und es gilt %%(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 %%k%%-Tupel gibt es, deren Einträge man aus n verschiedenen Elementen wählen kann?

 

%%k%%-Permutationen

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

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

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

%%k%%-Mengen

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

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

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

%%k%%-Kombinationen

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

Zum Beispiel:
%%\{6, 6, 5\} \ne \{6,5\}%% und %%\{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 %%k%%-Permutationen gibt es, deren Einträge man aus %%n%% verschiedenen Elementen wählen kann?

Beispiele

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

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

  3. Es gibt %%\binom{5+3-1}{3}=\binom{7}{3}%% Möglichkeiten, drei Bärchen (%%k=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 5 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 5 Stellen (%%k=5%%) gibt es %%10^5%% Möglichkeiten für die Zahlenkombination.(Man zieht 5 Mal aus einer Urne mit 10 unterscheidbaren Kugeln (Ziffern 0,1,…,9) wobei man nach jedem Ziehen die Kugel wieder zurücklegt und später die Reihenfolge beachtet, in der die Ziffern stehen.)

 

Beispielaufgaben

Kommentieren Kommentare

Zu article Kombinatorik: Formulierung in der Eisaufgabe unsauber
SirChristian 2016-02-17 08:09:51
3.1. "Jedes Kind darf sich drei Klugeln unterschiedlicher Sorten aussuchen. Wie viele Kombinationen sind möglich?"

Erst aus Aufgabenteil 2 bzw. der Lösung geht hervor, dass die Kinder eben nicht bloß verschiedene Eissorten wählen -->dürfen<--, sondern offenbar -->müssen--<.
Zwischen "dürfen" und "müssen" besteht ein himmelweiter Unterschied: "ich darf" heißt "mir ist erlaubt, aber ich muss nicht". Gerade in der Mathematik sollte man auf begriffliche Schärfe großen Wert legen. Die bestehende Formulierung ist daher etwas pfuschig.

(Weitere Anmerkung: Es befindet sich ein kleiner Tippfehler im Text: Kugeln stat "Klugeln")
Drinc 2016-02-17 11:42:43
Vielen Dank SirChristian für die scharfe Beobachtung und deine Rückmeldung!
Ich habe eine Alternativlösung angegeben, weil man die Aufgabenstellung genau so verstehen kann, wie du es dargestellt hast.

Viele Grüße,
Dennis
Antwort abschicken