Beispiel: Wie viele „Wörter“ kann man aus den Buchstaben M,A,T,H,E bilden, wenn man alle Buchstaben genau einmal verwendet?
Im ersten Zug sind 5 Buchstaben im Topf, im zweiten noch 4, im dritten noch 3 usw. Nach der Produktregel gibt es insgesamt
$$5\cdot 4\cdot 3\cdot 2\cdot 1=120$$
Möglichkeiten. Produkte dieser Art kommen sehr oft vor und sind Grundlage für viele weitere Abzählprobleme, deshalb haben diese Produkte einen eigenen Namen und eine Kurzschreibweise:
Fakultät
Das Produkt der ersten $n$ natürlichen Zahlen bezeichnen wir mit $n!$ (sprich: „$n$ Fakultät“):
$$n!=n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot 1$$
Für das Weitere ist es einfacher, wenn auch $0!$ (das leere Produkt) einen Wert hat. Deshalb legen wir fest: $0!=1$. Wir stellen es uns so vor, dass ein Produkt ohne echte Faktoren der Wert 1 hat. Das ist plausibel und harmoniert auch mit allen weiteren Berechnungen.
Wir wollen einige Fakultäten berechnen:
- $1! = 1 = 1$
- $2! = 1\cdot 2 = 2$
- $3! = 1\cdot 2\cdot 3 = 2!\cdot 3 = 6$
- $4! = 1\cdot 2\cdot 3\cdot 4 = 3!\cdot 4 = 24$
- $5! = 1\cdot 2\cdot 3\cdot 4\cdot 5 = 4!\cdot 5 = 120$
Wie im vorigen Abschnitt dargestellt, beschreibt $n!$ die Anzahl Möglichkeiten, $n$ Dinge anzuordnen. Eine Auswahl findet noch nicht statt, da alle $n$ Elemente angeordnet werden. Aber wir sind auf dem Weg zu unserer ersten Kombinatorik-Formel.
Absteigende Produktfolgen (Teile von Fakultäten)
Die Fakultät $n!$ enthält immer alle Faktoren von $n$ bis 1. Wir können mit Fakultäten aber auch Produktfolgen darstellen, die nicht bis zur 1 gehen. Dazu erweitern wir den Term als Bruch mit den fehlenden Faktoren:
$$7\cdot 6\cdot 5\cdot 4=\frac{7\cdot 6\cdot 5\cdot 4}1=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{3\cdot 2\cdot 1}=\frac{7!}{3!}=\frac{7!}{(7-4)!}$$
Wir formulieren diese Produktfolgen als Regel:
Absteigende Produktfolgen
Wenn wir für natürliche Zahlen $n$ und $k$ das Produkt $n\cdot(n-1)\cdot(n-2)\cdot\ldots$ notieren und insgesamt $k$ Faktoren schreiben, ist der letzte Faktor $(n-k+1)$, und es gilt:
$$\underbrace {n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k+1)}_{k\text{ Faktoren}}=\frac{n!}{(n-k)!}$$
Das klingt kompliziert, ist aber ganz einfach, deshalb schnell noch ein Beispiel dazu: Wir notieren eine absteigende Folge von 5 Faktoren, beginnend bei 17:
$$\underbrace{17}_{n}\cdot 16\cdot 15\cdot 14\cdot\underbrace{13}_{n-k+1}=\frac{17!}{(17-5)!}=\frac{17!}{12!}$$
Diese Formel wird uns auf der nächsten Seite dabei helfen, geordnete Stichproben zu beschreiben, bei der nicht alle $n$ Elemente angeordnet werden.