Kombinatorik [1]

Permutation

Die Anzahl Möglichkeiten \(n\) Objekte zu sortieren.

\[n!\]

Beispiel: Sandro hat eine Farbstiftschachtel mit 10 verschiedenfarbigen Stiften. In wie vielen verschiedenen Reihenfolgen kann er sie ordnen?

\(10! = 3628800\)

Warning

Eine Permutation ist eine Variation ohne Wiederholung mit \(n = k\). Beachte \((n-n)! = 0! = 1\).

Variation mit Wiederholung

Die Anzahl Möglichkeiten \(k\)-mal ein Objekt aus \(n\) Objekten auszuwählen.

\[n^k\]

Beispiel: In einer Urne sind 5 verschiedenfarbige Murmeln. Wie viele Möglichkeiten gibt es, dreimal eine Murmel mit Zurücklegen zu ziehen?

\(5^3 = 125\)

Warning

Beachte, dass {blau-blau-grün} eine andere Variation ist als {blau-grün-blau}!

Variation ohne Wiederholung

Die Anzahl Möglichkeiten \(k\)-mal ein Objekt aus \(n+1-i\) Objekten auszuwählen. Wobei \(i\) jeweils für den \(i\)-ten Zug steht.

\[\displaystyle \prod_{i=1}^k n+1-i = n * (n-1) * (n-2)\ *\ ...\ *\ (n-(k-1)) = \frac{n!}{(n-k)!}\]

Beispiel: In einer Urne sind 5 verschiedenfarbige Murmeln. Wie viele Möglichkeiten gibt es, dreimal eine Murmel ohne Zurücklegen zu ziehen?

\(\displaystyle \frac{5!}{(5-3)!} = 60\)

Warning

Beachte, dass {rot-blau-grün} eine andere Variation ist als {blau-rot-grün}!

Kombination ohne Wiederholung

Die Anzahl Möglichkeiten aus \(n\) Objekten \(k\) verschiedene Objekte auszuwählen.

\[\displaystyle \frac{n!}{(n-k)!k!} = \binom{n}{k}\]

Beispiel: In einer Urne sind 5 verschiedenfarbige Murmeln. Wie viele Möglichkeiten gibt es, drei daraus auszuwählen?

\(\displaystyle \binom{5}{3} = 10\)

Warning

Beachte, dass {rot-blau-grün} die gleiche Kombination ist als {blau-rot-grün}!

Kombination mit Wiederholung

Die Anzahl Möglichkeiten aus \(n\) Objekten \(k\) Objekte auszuwählen. Es können dabei Wiederholungen vorkommen.

\[\displaystyle \binom{n+k-1}{k} = \frac{(n+k-1)!}{(n-1)!k!}\]

Beispiel: Fritz hat 5 Wasserfarben und möchte daraus alle ihm möglichen Farben mischen, wenn er nur einen Teelöffel hat und eine Mischung aus jeweils 3 Löffeln Farbe bestehen muss. Wieviele Mischungen kann er kreieren?

\(\displaystyle \binom{5+3-1}{3} = 840\)

Warning

Auch aus {blau-blau-blau} entsteht eine Farbe (mit Wiederholung)!

{rot-gelb-rot} mischt das gleiche dunkelorange wie {gelb-rot-rot}, ist also dieselbe Kombination!

[1]	Source: Dr. Robert Aehle