Kombinatorik 

Die Aufgabe der Kombinatorik ist es, die Anzahl aller Möglichkeiten aus einer angegebenen Menge der Elemente auszurechnen, wobei die Elemente auszuwählen und/oder anzuordnen sind. Im weiteren Verlauf des Textes werden einzelne Bestandteile der Kombinatorik präsentiert, passende Formeln anhand von Beispielen erklärt und ihre Benutzung gezeigt (Bourier, G. 2009). 

Permutationen 

Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge. Sie gibt an, auf wie viele verschiedene Weisen eine gegebene Menge von Elementen geordnet werden kann.  

Eine Permutation ohne Wiederholung liegt vor, wenn alle Elemente der Reihenfolge paarweise verschieden sind.  Als Beispiel nimmt man 5 verschiedene Steine. Wenn man nun berechnen möchte, wie viele verschiedene Anordnungen man aus diesen 5 Steinen bilden kann, schaut man sich zunächst die erste Position an. Für die erste Position gibt es alle 5 Steine zur Auswahl. Danach hat man nur 4 für die zweite, da einer schon auf der ersten Position ist. Analog hat man 3 für die dritte und 2 für die vierte. Auf der fünften Position hat man den letzten Stein übrig. Multipliziert man alle diese Möglichkeiten für jeden Platz, bekommt man eine Antwort: 5! =120 Reihenfolgen. 

Diese Aufgabe kann man verallgemeinern, indem man n Steine anstatt 5 hat. Analog ist die Antwort n!  

Die Anzahl aller Permutationen ohne Wiederholung ist immer n!, wobei n die Anzahl der Elemente in der Reihenfolge ist. 

Im Vergleich zu dem letzten Beispiel hat man bei der Permutation mit Wiederholung Elemente, die gleich sind. Das heißt, dass man aus einem Beispiel mit verschiedenen Elementen alle Reihenfolgen weglassen sollte, die wegen einer Gleichheit der Elemente auch jetzt gleich sind. Man nimmt an, aus dem Beispiel mit den Steinen, man hat rote, schwarze, blaue, und 2 grüne, dann sind die Reihenfolgen: 

R, S, B, G1, G2 und R, S, B, G2, G1 genau gleich. Die Anzahl solcher wiederholten Reihenfolgen ist die Anzahl aller Permutationen der gleichen Elemente. Um dieses Problem zu lösen, berechnen wir erstmal alle Permutationen, und dann teilt man durch alle Permutationen der gleichen Elemente.  

Die Anzahl aller Permutationen mit Wiederholung ist immer $\frac{n!}{k!}$ , wobei n eine Anzahl der Elemente in der Reihenfolge ist und k die Anzahl der gleichen Elemente. 

Kombinationen 

Bei einer Kombination geht es um alle mögliche Auswahlen der k Elemente von n. Die Reihenfolge der ausgewählten Elemente ist dabei nicht wichtig.  

In der Kombination ohne Wiederholung kann man ein Element nur einmal zur Anordnung auswählen. Man nimmt an, man sollte aus 5 verschiedenen Steinen 2 auswählen. Für die Auswahl von dem ersten Stein hat man 5 Möglichkeiten und 4 für den zweiten. Da deren Reihenfolge nicht wichtig ist, sollte man durch die Anzahl aller Permutationen der ausgewählten Steine teilen. Dann ist die Antwort: $\frac{5\cdot 4}{2}=10$ Möglichkeiten 2 Steine aus 5 auszuwählen. 

Nimmt man an, man hat n Steine und sollte k auswählen dann gibt es n Möglichkeiten für den ersten, n-1 für den zweiten und so weiter, bis die Anzahl der Faktoren k erreicht. Das lässt sich wie folgt aufschreiben: $\frac{n!}{\left(n-k\right)!}$ . Aus der Regel der Fakultäten bekommt man somit im Zähler k Faktoren bei der Multiplikation. Am Ende sollte man durch die Anzahl aller k Permutationen teilen, da die Reihenfolge unwichtig ist. Dann gilt: 

Die Anzahl aller Kombinationen ohne Wiederholung ist immer $\frac{n!}{k!\cdot \left(n-k\right)!}$ , wobei n eine Anzahl der Elemente in der Menge ist und k die Anzahl der Elemente die zu auswählen sind. Diese Formel lässt sich kürzer als Binomialkoeffizient aufschreiben. Das wäre dann: $\binom{n}{k}$ (n über k)

Kombinationen mit Wiederholung sind dadurch gekennzeichnet, dass ein vorgegebenes Element in der Auswahl mehrmals auftreten kann. Es liegt eine “Auswahl mit Zurücklegen” vor. In diesem Fall kommen durch das Zurücklegen praktisch k-1 Elemente hinzu. Daher muss an Stelle des Binomialkoeffizienten “n über k” jetzt der Binomialkoeffizient “n+k-1 über k” berechnet werden: 

Die Anzahl aller Kombinationen mit Wiederholung ist immer $\binom{n+k-1}{k}=\frac{\left(n+k-1\right)!}{k!\cdot \left(n-1\right)!}$ , indem n eine Anzahl der Elemente in der Menge ist und k die Anzahl der Elemente die zu auswählen sind. Da die Elemente mehrmals auftreten können, muss man noch k-1 hinzufügen.

Variationen 

Eine Variation ist eine Kombination, bei der die Reihenfolge der ausgewählten Elemente auch wichtig ist. Das heißt, dass hier auch die Permutationen gebildet werden können. 

Bei einer Variation ohne Wiederholung kann man ein Element nur einmal zur Anordnung auswählen. Man nimmt an, man muss aus 5 verschiedenen Steinen 2 auswählen, von denen der erste verkauft und der andere verschenkt werden. Im Vergleich zum Beispiel mit Kombination, ist hier wichtig, welcher zu verkaufen und welcher zu verschenken ist. Das bedeutet, dass nach der Auswahl von den beiden die Anzahl der Permutationen auszurechnen ist. Das erste macht man mit einem normalen Binomialkoeffizienten $\binom{5}{2}$ , dann multipliziert man den mit der Anzahl der Permutationen 2!. Das kürzt sich dann mit einem Faktor im Nenner. 

Die Anzahl aller Variationen ohne Wiederholung ist immer $\frac{n!}{\left(n-k\right)!}$ , wobei n eine Anzahl der Elemente in der Menge ist und k die Anzahl der Elemente die zu auswählen sind. Die Reihenfolge der k Elemente ist hier berücksichtigt. 

Bei einer Variation mit Wiederholung kann man jedes Element mehrmals zur Anordnung auswählen. Man nimmt an, man hat unendlich viele Steinen der 5 Arten. Man soll 2 von ihnen auszuwählen, um sie zu verschenken und zu verkaufen. Dann hat man 5 Möglichkeiten für ersten Stein, aber auch 5 Möglichkeiten für den zweiten. Insgesamt sind das $5^2=25$ Möglichkeiten. Wenn man n Arten hat und k Steine für verschiedene Ziele braucht, somit gibt es $n^k$ Möglichkeiten.

Die Anzahl aller Variationen mit Wiederholung ist immer $n^k$, wobei n eine Anzahl der möglichen Elemente in der Menge ist und k die Anzahl der Elemente, die auszuwählen sind. Die Reihenfolge der k Elemente ist hier berücksichtigt. Dabei kann man gleiche Elemente auswählen. 

Permutation, Variation oder Kombination 

Die hier stehende Folge von Fragen hilft auf eine einfache Weise feststellen, ob man bei einer Aufgabe Permutation, Variation oder Kombination benutzt. 

1. Geht es um ein Anordnungsproblem einer Menge oder ein Auswahlsproblem 

• Anordnung -> Permutation -> Frage 2 

• Auswahl -> Variation oder Kombination -> Frage 3 

2. Sind alle Elemente der Reihenfolge unterschiedlich? 

• Ja -> Permutation ohne Wiederholung 

• Nein -> Permutation mit Wiederholung 

3. Braucht man nach der Auswahl die Anordnung zu berücksichtigen? 

• Ja -> Variation -> Frage 4 

• Nein -> Kombination -> Frage 5 

4. Kann ein Element mehrmals bei der Auswahl vorkommen? 

• Ja -> Variation mit Wiederholung 

• Nein -> Variation ohne Wiederholung 

5. Kann ein Element mehrmals bei der Auswahl vorkommen? 

• Ja -> Kombination mit Wiederholung 

• Nein -> Kombination ohne Wiederholung

Zusammenfassend wird das nochmal in Abbildung gezeigt:

(Universität Kassel. n.d.)

(Bourier, G. 2009)

(Doucet-Rosenstein, D. 1981)

Binomialkoeffizienten-Vertiefung. Es sei M eine Menge. Ist M endlich, so bezeichnen wir mit |M| die Anzahl der Elemente in M. Hat M die Länge n, so nennen wir M eine n-Menge. Mit P(M) bezeichnen wir die Menge aller Teilmengen von M, einschließlich der leeren Menge ∅ und M selbst. P(M) heißt die Potenzmenge von M. 

Ist M eine n-Menge, so ist |P(M)|=2ⁿ 

Über jedes Element von M kann man entscheiden, ob dieses bei einer Teilmenge dabei ist oder nicht. Solche Entscheidung bei der Auswahl allen Elementen führt zu allen entsprechenden Teilmengen. Daher ist |P(M)|=2ⁿ  

Ist X ∈ P(M) und ist |X| = k, so nennen wir X eine k-Teilmenge von M. Die Menge aller k-Teilmengen von M bezeichnen wir mit P_k(M). Ist M eine n-Menge, so setzen wir |P_k(M)|=$\ \binom{n}{k}$. Die Zahlen$\ \binom{n}{k}$heißen Binomialkoeffizienten. 

n und k seien nicht-negative ganzen Zahlen. Dann gilt: 

a) $\ \binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}$

b) $\binom{n}{k}=\binom{n}{n-k}$

c) $\binom{n}{0}=\binom{n}{n}=1\quad \mathrm{und}\quad \binom{n}{1}=\binom{n}{n-1}=n$

d) $\sum _{i=0}^n\binom{n}{i}=2^n$

e) $\binom{n}{k}\le \binom{n+1}{k}$

f) $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$

Alle Formeln lassen sich aus der Formel mit Fakultäten herausleiten (Lüneburg, H. 1971). 

Literaturverzeichnis 

• Universität Kassel. (n.d.). Dokument / Skript. Fachbereich 07 Wirtschaftswissenschaften. https://www.uni-kassel.de/fb07/index.php?eID=dumpFile&t=f&f=2915&token=5c343b5f2460dc1ce391f7766b0d01e7776bc73b 

• Lüneburg, H. (1971). Kombinatorik (Band 4). Birkhäuser. 

• Bourier, G. (2009). Wahrscheinlichkeitsrechnung und schließende Statistik: Praxisorientierte Einführung; mit Aufgaben und Lösungen (6. Aufl.). Gabler Verlag. 

• Doucet-Rosenstein, D. (1981). Die Kombinatorik als Methode der Wissenschaften bei Raimund Lull und G. W. Leibniz [Dissertation, Ludwig-Maximilians-Universität München].