Kombinatorik

Grundbegriffe

• Grundmenge: In der Kombinatorik bezeichnet die "Grundmenge" oder "Ausgangsmenge" die Gesamtheit aller Elemente, aus denen man wählen kann. Die Grundmenge ist also die Menge, aus der man Kombinationen oder Permutationen bildet.

• Reihenfolge: Die Reihenfolge ist in der Kombinatorik die Abfolge, in der Elemente gezogen werden. Ob die Reihenfolge wichtig oder unwichtig ist, bedeutet, ob beachtet wird, welches Element zu welchem Zeitpunkt gezogen wird oder ob man nur die gesamte gezogene Menge ohne eine Ordnung betrachtet. Die Relevanz der Reihenfolge unterscheidet unter anderem Kombination und Variation (s.u.).

• Zurücklegen: (mit) Zurücklegen ist die Möglichkeit, ein Element nach seiner Auswahl zurückzulegen und erneut aus der gleichen Menge auszuwählen. Das Gegenteil davon wäre "ohne Zurücklegen", bei dem jedes Element nur einmal ausgewählt werden darf.

Ziehverfahren

Permutation

• Eine Permutation ist eine geordnete Anordnung von Elementen
• Die Anzahl der Permutationen von n Elementen ist $n!$ (n Fakultät), wobei $n!=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot 3\cdot 2\cdot 1$

Kombinationen

• Eine Kombination ist eine ungeordnete Auswahl von Elementen
• Es gibt zwei Haupttypen von Kombinationen:
• Kombination ohne Wiederholung: Die Reihenfolge der Auswahl ist nicht wichtig
• Kombination mit Wiederholung: Die Reihenfolge der Auswahl ist nicht wichtig, und Elemente können mehrfach ausgewählt werden
• Die Anzahl der Kombinationen ohne Wiederholung von n Elementen, die jeweils k Elemente enthalten, ist (n über k), berechnet als ${\frac {n!}{kn!\cdot (n-k)!}}$

Variation

• Eine Variation ist eine geordnete Auswahl von Elementen
• Es gibt Variationen mit und ohne Wiederholung
• Die Anzahl der Variationen ohne Wiederholung von n Elementen, die jeweils k Elemente enthalten, ist $V(n,k)={\frac {n!}{(n-k)!}}$

Binomial- und Multinomialkoeffizient

Der Binomialkoeffizient gibt an auf wie viele Arten man k Objekte aus einer Menge von n Objekten auswählen kann, wobei die Reihenfolge nicht beachtet und ohne Zurücklegen gezogen wird. Er ist auch in der Abbildung enthalten und wird durch folgende Formeld definiert: <math>