Grundlagen der Kombinatorik

Inhaltsverzeichnis zum Thema

• Was ist Kombinatorik?
• Kombinationen
  • Kombinationen ohne Wiederholung
  • Kombinationen mit Wiederholung
• Variationen
  • Variationen ohne Wiederholung
  • Variationen mit Wiederholung

Was ist Kombinatorik?

Die Kombinatorik ist ein Teilgebiet der Mathematik. Es wird dabei untersucht, wie viele verschiedene Anordnungen endlich vieler Elemente möglich sind.

Die Kombinatorik kann sowohl für die Statistik als auch die Wahrscheinlichkeitsrechnung als Grundlage verwendet werden. Zum Beispiel musst du, um die Wahrscheinlichkeiten eines Ereignisses $E$ bei Laplace-Experimenten zu berechnen, folgenden Zusammenhang betrachten:

$P(E)=\dfrac{\text{Anzahl aller für }E \text{ günstigen Ergebnisse} }{\text{Anzahl aller möglichen Ergebnisse}}$

In der Kombinatorik werden die folgenden Aufgabenstellungen behandelt:

• Permutationen: Wie viele Möglichkeiten gibt es, aus $n$ Elemente $k=n$ Elemente unter Berücksichtigung der Reihenfolge anzuordnen?
• Kombinationen: Wie viele Möglichkeiten gibt es, aus $n$ Elemente $k<n$ elemente="" ohne="" berücksichtigung="" der="" reihenfolge="" anzuordnen?="" *="" variationen:="" wie="" viele="" möglichkeiten="" gibt="" es,="" aus="" $n$="" elementen="" $k<n$="" unter="" dabei="" werden="" jeweils="" die="" folgenden="" unterscheidungen="" betrachtet:="" betrachtest="" du="" gesamtheit="" aller="" oder="" nur="" eine="" stichprobe?="" berücksichtigst="" nicht?="" wiederholst="" das="" experiment="" gleichen="" voraussetzungen="" („mit="" zurücklegen“)="" nicht="" („ohne="" zurücklegen“)?="" ##="" permutationen="" betrachte="" permutationen="" einer="" $n$-elementigen="" menge.="" schau="" dir="" hierfür="" folgende="" beispiel="" an.="" anna,="" lisa="" und="" paul="" sind="" gute="" freunde.="" sie="" wollen="" ein="" foto="" von="" sich="" machen.="" überlegen,="" anordnungen="" es="" gibt,="" in="" welchen="" drei="" aufstellen="" können.="" ganz="" links="" könnte="" jeder="" stehen.="" wenn="" diese="" position="" nun="" besetzt="" ist,="" kann="" noch="" den="" beiden="" verbleibenden="" mitte="" schließlich="" letzte="" rechts="" jeweilige="" anzahl="" musst="" multiplizieren.="" dies="" ist="" übrigens="" produktregel="" kombinatorik.="" erhältst="" also:=""

  $N=3\cdot 2\cdot 1=6$

Allgemein erhältst du für eine $n$-elementige Menge unterscheidbarer Elemente folgende Anzahl möglicher Kombinationen:

$N=n\cdot (n-1)\cdot (n-2)\cdot\ ...\ \cdot 1$

Für dieses spezielle Produkt der ersten $n$ natürlichen Zahlen gibt es eine spezielle Schreibweise in der Mathematik, die Fakultät:

$n!=n\cdot (n-1)\cdot (n-2)\cdot\ ...\ \cdot 1$

Für die folgenden beiden Problemstellungen kannst du dir jeweils vorstellen, dass sich in einer Urne $n$ Kugeln befinden. Du entnimmst $k\le n$ dieser Kugeln. In der Kombinatorik werden solche Urnenmodelle verwendet.

Kombinationen

Bei einer Kombination handelt es sich um eine ungeordnete Stichprobe. Die Reihenfolge der Objekte wird nicht berücksichtigt. Man unterscheidet wieder zwischen Kombinationen ohne und mit Wiederholung.

Kombinationen ohne Wiederholung

Du kannst solche Kombinationen ohne Wiederholung betrachten. Schaue dir hierfür folgendes Beispiel an: Du möchtest aus $6$ Elementen $3$ auswählen. Zunächst hast du $6\cdot 5\cdot 3$ Möglichkeiten hierfür. Da die Reihenfolge nicht von Bedeutung ist, dividierst du durch die Anzahl der Permutationen dieser drei Elemente, also $3!$. Schließlich erhältst du:

$ N=\frac{6\cdot 5\cdot 4}{3!}=20 $

Allgemein gibt es für diese Anzahl den Binomialkoeffizienten: $\binom{n}{k}$

Bei obigem Beispiel bedeutet dies:

$N=\binom{6}{3}=20$

Kombinationen mit Wiederholung

Bei Kombinationen mit Wiederholung wird nach jedem Zug wieder zurückgelegt, also die Ausgangssituation hergestellt. So erhältst du mit dem Binomialkoeffizienten:

$ N=\binom{n+k-1}{k} $

Variationen

Eine Variation ist eine geordnete Stichprobe. Die Reihenfolge der Elemente spielt also eine Rolle. Auch bei Variationen unterscheidet man zwischen Variationen mit und ohne Wiederholung.

Variationen ohne Wiederholung

Betrachte zunächst Variationen ohne Wiederholung. Hier kann man wieder das obige Beispiel betrachten: Du möchtest aus $6$ Elementen $3$ auswählen. Hierfür gibt es $6\cdot 5\cdot 3$ Möglichkeiten. Allgemein gilt:

$N=\frac{n!}{(n-k)!}$

Variationen mit Wiederholung

Es bleiben noch die Variationen mit Wiederholung. Du möchtest die Anzahl der Variationen von $k$ Kugeln aus $n$ Kugeln ermitteln. Da die Anzahl der Kugeln sich nicht verändert, erhältst du:

$N=n^{k}$