Kombinatorik

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:

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\cdot 6=305\backslash cdot\; 6=30$ Möglichkeiten für die ersten beiden Perlen). Insgesamt ergeben sich $6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 16\backslash cdot\; 5\backslash cdot\; 4\backslash cdot\; 3\backslash cdot\; 2\backslash 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\cdot 2\cdot 3\cdot \dots \cdot nn!=1\; \backslash cdot\; 2\backslash cdot\; 3\backslash cdot\; \backslash ldots\; \backslash 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.

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: $(\mathrm{1,2},\mathrm{3,4})(1\{,\}2,3\{,\}4)$ ist ein $44$-Tupel und es gilt $(\mathrm{1,2},\mathrm{3,4})\mathrm{\ne }(\mathrm{1,2},\mathrm{4,3})(1\{,\}2,3\{,\}4)\backslash 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: $(\mathrm{1,2},\mathrm{3,4})(1\{,\}2,3\{,\}4)$ ist eine $44$-Permutation, aber ($\mathrm{1,2},\mathrm{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\}=\{\mathrm{6,5}\}\backslash \{6,\; 6,\; 5\backslash \}\; =\; \backslash \{6\{,\}5\backslash \}$ und $\{7,3,1\}=\{1,3,7\}\backslash \{7,\; 3,\; 1\backslash \}\; =\; \backslash \{1,\; 3,\; 7\backslash \}$

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\}\mathrm{\ne }\{\mathrm{6,5}\}\backslash \{6,\; 6,\; 5\backslash \}\; \backslash ne\; \backslash \{6\{,\}5\backslash \}$ und $\{7,3,1\}=\{1,3,7\}\backslash \{7,\; 3,\; 1\backslash \}\; =\; \backslash \{1,\; 3,\; 7\backslash \}$

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 $\left(\genfrac{}{}{0px}{}{49}{6}\right)\backslash binom\{49\}\{6\}$ Möglichkeiten, aus den Zahlen $\mathrm{1,2},\dots ,491\{,\}2,\dots ,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 $\frac{20!}{(20-15)!}=\frac{20!}{5!}\backslash frac\{20!\}\{(20-15)!\}=\backslash 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 $\left(\genfrac{}{}{0px}{}{5+3-1}{3}\right)=\left(\genfrac{}{}{0px}{}{7}{3}\right)\backslash binom\{5+3-1\}\{3\}=\backslash 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 ${10}^{5}10^5$ Möglichkeiten für die Zahlenkombination.(Man zieht $55$ Mal aus einer Urne mit $1010$ unterscheidbaren Kugeln (Ziffern $\mathrm{0,1},\dots ,90\{,\}1,\dots ,9$) wobei man nach jedem Ziehen die Kugel wieder zurücklegt und später die Reihenfolge beachtet, in der die Ziffern stehen.)