Fakultät – „Mathe für Nicht-Freaks“

Die Fakultät $n!$ ist nichts anderes als eine Kurzschreibweise für das Produkt $1\cdot 2\cdot 3\cdot \dots \cdot n$. Die Fakultät ist insbesondere für die Kombinatorik wichtig, da sie die Anzahl der verschiedenen Anordnungen einer $n$-elementigen Menge wiedergibt. So stößt man in der Wahrscheinlichkeitsrechnung, der Statistik und auch in anderen Bereichen der Mathematik immer wieder auf die Fakultät. Schauen wir uns aber zunächst ihre Definition an, bevor wir uns ihrer Anwendung zuwenden.

Herleitung

Durch progressives Einfügen der Zahlen $1$, $2$ und $3$ kann man alle Anordnungen dieser Zahlen finden. Insgesamt ergeben sich $6$ Möglichkeiten der Anordnung.

Nehmen wir eine beliebige Menge. Wie viele Möglichkeiten gibt es, diese anzuordnen? Eine solche Fragestellung ergibt sich, wenn uns zum Beispiel bei einer Menge von Läufern die Anzahl der möglichen Startverteilungen oder bei einem Gruppenfoto die Anzahl der Aufstellungen der Personen interessiert. Welche Objekte wir betrachten, hat keinen Einfluss auf ihre Anordnungsmöglichkeiten. Ausschlaggebend ist nur ihre Anzahl. Wir suchen also eine Funktion $f:\mathbb{N}\to \mathbb{N}$, so dass $f(n)$ die Anzahl der unterschiedlichen Möglichkeiten ist, die Elemente einer $n$-elementigen Menge anzuordnen.

Um diese Funktion zu finden, gehen wir induktiv vor. Zunächst beginnen wir bei der kleinsten Menge mit nur einem Element ($n=1$) und versuchen durch sukzessives Einfügen neuer Elemente auf den Ergebnissen der vorherigen Schritte aufzubauen. Der Einfachheit halber betrachten wir nur Mengen der Form $\{1,2,\dots ,n\}$, da nur die Anzahl an Elementen relevant ist.

Beginnen wir mit der einelementigen Menge $\{1\}$. Diese kann man nur auf eine Art anordnen, da sie nur ein Element besitzt:

$1$

Fügen wir der Menge ein Element hinzu und betrachten nun die Menge $\{1,2\}$. Die neue Zahl $2$ kann ich an zwei Orten platzieren – vor und nach der $1$:

$2112$

Beim Hinzufügen des dritten Elements gehen wir auf dieselbe Weise vor: Die neuen Anordnungsmöglichkeiten erzeugen wir durch Einfügen des neu hinzukommenden Elements (der $3$) an allen möglichen Stellen in den bereits bestehenden Anordnungen von zwei Elementen. Zunächst sieht man, dass man die Zahl $3$ an drei Stellen einfügen kann: links, mittig, rechts. Außerdem gibt es bereits zwei mögliche Anordnungen der Zahlen $\{1,2\}$. Damit erhalten wir ingesamt $3\cdot 2=6$ neue Anordnungsmöglichkeiten:

$312132123321231213$

Für eine $n+1$-elementige Menge lautet das Verfahren also: „Erzeuge alle Anordnungen der Menge, indem du das neue Element, $n+1$, an allen möglichen Stellen in alle möglichen Permutationen der Menge ohne $n+1$ einfügst.“ Wir haben so induktiv alle Permutationen einer $n$-elementigen Menge erzeugt. Wir wollen unserer Funktion nun einen Namen geben: Die von uns gesuchte Funktion wird Fakultät genannt und wird üblicherweise in der Postfix-Notation $n!$ geschrieben.

Kehren wir zurück zur Erzeugungsvorschrift: Es gibt $n+1$ Möglichkeiten die neue Zahl zu platzieren, wobei es bereits $n!$ Anordnungsmöglichkeiten der restlichen Zahlen gibt. So ergibt sich die Rekursionsformel:

$(n+1)!=(n+1)\cdot n!$

Mit $1!=1$ haben wir den Rekursionsanfang gefunden (es gibt eine Anordnungsmöglichkeit für eine einelementige Menge). Diese rekursive Berechnungsvorschrift können wir als Produkt auch explizit aufschreiben:

$\begin{array}{cc}n!& =n\cdot (n-1)!=n\cdot (n-1)\cdot (n-2)!=\dots \\ & =n\cdot (n-1)\cdot (n-2)\cdot \dots \cdot 1\\ & =\prod _{i=1}^{n}i\end{array}$

Unsere Baumdarstellung zeigt, dass die Fakultät schneller als jede Potenz wächst. Exponentieller Wachstum der Form $k^n$ entspricht der Anzahl der Blätter auf der $n$-ten Ebene eines Baumes mit konstantem Verzweigungsgrad $k$. Der Fakultätsbaum jedoch hat einen Verzweigungsgrad, der mit jeder neuen Ebene um $1$ zunimmt. Die Fakultät wächst also in der Großenordnung wie die Funktion $n^n$.

Definition

Die Definition der Fakultät (Video vom Podcast The Wicked Mu)

Diagramm von 0! bis 4!

Die Fakultät $n!$ ist definiert als

$n!=1\cdot 2\cdot 3\cdot \dots \cdot n$

Das auftretende Produkt mit der Pünktchen-Schreibweise können wir exakter als endliches Produkt notieren:

$n!=1\cdot 2\cdot 3\cdot \dots \cdot n=\prod _{k=1}^{n}k$

Es fehlt noch der Ausdruck $0!$. Was soll hier das Ergebnis sein? In der Schreibweise mit dem endlichen Produkt ergibt sich ein leeres Produkt:

$0!=\prod _{k=1}^{0}k$

Dieses Produkt ist leer, weil der Startwert des Laufindex größer als dessen Endwert ist. Wir hatten bereits festgelegt, dass das leere Produkt immer $1$ ist. Wir können also definieren:

$0!=\underset{\text{leeres Produkt}}{\underbrace{\prod _{k=1}^{0}k}}=1$

Die letzte Gleichung können wir auch so interpretieren: Es gibt genau eine Möglichkeit eine leere Menge anzuordnen, nämlich mit der leeren Anordnung. Fassen wir das Gesagte zusammen:

Definition (Fakultät)

Für eine natürliche Zahl $n\ge 0$ ist ihre Fakultät $n!$ definiert durch:

$n!:=1\cdot 2\cdot 3\cdot \dots \cdot n=\prod _{k=1}^{n}k$

Es ist $0!=1$.

Die Fakultät und die Stirlingformel

Schauen wir uns einige Beispiele an:

Beispiel (Beispiele zur Fakultät)

Es ist

$\begin{array}{ccc}0!& =1& =1\\ 1!& =1& =1\\ 2!& =1\cdot 2& =2\\ 3!& =1\cdot 2\cdot 3& =6\\ 4!& =1\cdot 2\cdot 3\cdot 4& =24\\ 5!& =1\cdot 2\cdot 3\cdot 4\cdot 5& =120\\ & ⋮\end{array}$

Die Fakultät wächst dabei sehr schnell. So ist $10!=3628800$ und $100!=\mathrm{9,3326}\dots \cdot 10^{157}$, also eine Zahl mit 157 Ziffern im Dezimalsystem. Die Stirlingformel ist eine Möglichkeit, die Fakultät zu approximieren. Diese Approximation zeigt, dass die Fakultät schneller als exponentielle Funktionen wächst.

Rekursive Definition der Fakultät

Rekursive Definition der Fakultät (Video vom Podcast The Wicked Mu)

Die Fakultät kann auch rekursiv definiert werden. Hierfür benötigen wir einen Rekursionsschritt und -anfang. Beim Rekursionsschritt wird angegeben, wie $n!$ mit Hilfe von $(n-1)!$ berechnet werden kann:

Frage: Wie kann $n!$ mit Hilfe von $(n-1)!$ berechnet werden?

Es ist

$\begin{array}{cc}n!& =1\cdot 2\cdot 3\cdot \dots \cdot n\\ & =\underset{=(n-1)!}{\underbrace{1\cdot 2\cdot 3\cdot \dots \cdot (n-1)}}\cdot n\\ & =(n-1)!\cdot n\end{array}$

Der Rekursionsschritt lautet also $n!=(n-1)!\cdot n=n\cdot (n-1)!$

Mit Hilfe des obigen Rekursionsschritts kann $n!$ auf $(n-1)!$ zurückgeführt werden. Dieses wiederum kann durch $(n-2)!$ berechnet werden, weil $(n-1)!=(n-2)!\cdot (n-1)$ ist und so weiter. Es entsteht so eine Kette von Berechnungen, wobei in jedem Schritt die Fakultät einer Zahl mit Hilfe der Fakultät des Vorgängers berechnet wird.

Diese Berechnungskette muss aber irgendwann einmal abbrechen. Hierfür benötigen wir den Rekursionsanfang. Dabei müssen wir für die kleinste Zahl $m$, für die die Fakultät sinnvoll definiert werden kann, den Ausdruck $m!$ angeben. Diese kleinste Zahl ist $m=0$. Nun wissen wir aber bereits aus dem obigen Abschnitt, dass $0!=1$ ist. Damit ergibt sich folgende rekursive Definition der Fakultät:

Definition (Rekursive Definition der Fakultät)

Die Fakultät $n!$ ist rekursiv definiert durch:

$n!=\{\begin{array}{cc}1& \text{falls }n=0\text{ (Rekursionsanfang)}\\ n\cdot (n-1)!& \text{falls }n>0\text{ (Rekursionsschritt)}\end{array}$

Die Wirkungsweise der rekursiven Definition lässt sich gut an einem Beispiel nachvollziehen. Hier wird solange der Rekursionsschritt angewendet, bis der Rekursionsanfang benutzt werden kann:

Verständnisfrage: Warum ist $(n+1)!=n!\cdot (n+1)$?

Dies ergibt sich direkt aus dem Rekursionsschritt $n!=(n-1)!\cdot n$. In dieser Gleichung setzt man anstelle von $n$ einfach $n+1$ ein. Dies ergibt

$(n+1)!=(n+1-1)!\cdot (n+1)=n!\cdot (n+1)$

Verständnisfrage: Vereinfache folgende Ausdrücke:

• $\frac{(n+1)!}{n!}$
• $\frac{n!}{(n-2)!}$
• $\frac{k!(n-k)!}{(k+1)!(n-k-1)!}$

Es ist

• $\frac{(n+1)!}{n!}=\frac{n!\cdot (n+1)}{n!}=n+1$
• $\frac{n!}{(n-2)!}=\frac{(n-2)!\cdot (n-1)\cdot n}{(n-2)!}=(n-1)\cdot n$
• $\frac{k!\cdot (n-k)!}{(k+1)!\cdot (n-k-1)!}=\frac{k!\cdot (n-k-1)!\cdot (n-k)}{k!\cdot (k+1)\cdot (n-k-1)!}=\frac{n-k}{k+1}$

Verständnisaufgabe: Beweise $n!\cdot (n^2-1)=(n+1)!\cdot (n-1)$.

Aus der dritten binomischen Formel wissen wir $(n^2-1)=(n+1)\cdot (n-1)$. Damit ist

$\begin{array}{cc}n!\cdot (n^2-1)& =n!\cdot (n+1)\cdot (n-1)\\ & =(n+1)!\cdot (n-1)\end{array}$

Dabei haben wir ausgenutzt, dass nach der Definition der Fakultät $(n+1)!=n!\cdot (n+1)$ ist.

Anwendungen der Fakultät

Wie bereits erwähnt, tritt die Fakultät häufig bei Wahrscheinlichkeitsrechnungen und in der Statistik auf. Die Ursache dafür liegt an folgendem Satz aus der Kombinatorik (die Kombinatorik beschäftigt sich mit der Frage nach der Anzahl möglicher Anordnungen und bildet damit die Grundlage der Wahrscheinlichkeitsrechnung).

Satz (Anordnungen einer endlichen Menge)

Die Anzahl aller Anordnungen einer endlichen Menge mit $n$ Elementen ist $n!$.

Dies bedeutet, dass die Anzahl der Permutationen einer Menge mit $n$ Elementen gleich $n!$ ist. Mit Hilfe dieses Satzes können nun folgende Fragen beantwortet werden: Wie viele mögliche Anordnungen von $52$ Spielkarten gibt es? Wenn ich $20$ Bierflaschen habe, wie viele Reihenfolgen gibt es, diese Bierflaschen zu trinken? Auf wie viele unterschiedliche Routen kann man elf Sehenswürdigkeiten besichtigen?

Wie kommt man auf den Beweis? (Anordnungen einer endlichen Menge)

Schauen wir uns zunächst einige Beispiele an. Betrachte dazu die Menge $A=\{1,2,3\}$ und $B=\{1,2,3,4\}$.

Frage: Wie viele Anordnungen dieser beiden Mengen gibt es und welche sind das?

Die Anzahl der verschiedenen Anordnungen dieser beiden Mengen lässt sich am besten dadurch bestimmen, indem wir alle möglichen Anordnungen systematisch aufschreiben. Fangen wir mit der Menge $A$ an. Die Menge $\{1,2,3\}$ besitzt folgende mögliche Anordnungen:

$\begin{array}{cc}123& 213312\\ 132& 231321\end{array}$

Wir haben sechs mögliche Anordnungen gefunden (was $3!$ entspricht). Analog können wir alle möglichen Anordnungen der 4-elementigen Menge $\{1,2,3,4\}$ finden:

$\begin{array}{c}1234213431244123\\ 1243214331424132\\ 1324231432144213\\ 1342234132414231\\ 1423241334124312\\ 1432243134214321\\ \end{array}$

Wir haben $24$ verschiedene Möglichkeiten der Anordnung gefunden (was $4!$ entspricht). Wenn man sich nun die gefundene Systematik zum Notieren aller Anordnungen anschaut, kann man ein induktives Prinzip erkennen.

Schauen wir uns die Anordnungen der zweiten Menge $\{1,2,3,4\}$ an. Zunächst haben wir vier Möglichkeiten die erste Zahl zu bestimmen (jede Spalte). Danach haben wir in den Zeilen jeder Spalte alle Kombinationsmöglichkeiten der restlichen drei Zahlen systematisch aufgeschrieben. Da es für drei Zahlen genau sechs Möglichkeiten gibt (wie bei Menge $A$ bestimmt), kommen wir auf insgesamt $4\cdot 6=24$ Möglichkeiten. Diese Argumentation entspricht einem Beweis mit vollständiger Induktion.

Beweis (Anordnungen einer endlichen Menge)

Aussageform, deren Allgemeingültigkeit für $n\in \mathbb{N}$ bewiesen werden soll:

Es gibt $n!$ Möglichkeiten eine $n$-elementige Menge anzuordnen.

1. Induktionsanfang:

Für eine einelementige Menge gibt es nur eine Anordnungsmöglichkeit. Da außerdem $1!=1$ ist, ist die Aussageform für $n=1$ wahr.

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

Es gibt $n!$ Möglichkeiten eine $n$-elementige Menge anzuordnen.

2b. Induktionsbehauptung:

Es gibt $(n+1)!$ Möglichkeiten eine $n+1$-elementige Menge anzuordnen.

2c. Beweis des Induktionsschritts:

Für eine $(n+1)$-elementige Menge gibt es $n+1$ Möglichkeiten die erste Position zu besetzen. Für jede dieser Möglichkeiten müssen die restlichen $n$ Positionen besetzt werden, wobei es nach Induktionsvoraussetzung dafür genau $n!$ Möglichkeiten gibt. Damit ist die Gesamtzahl aller möglichen Anordnungen einer $(n+1)$-elementigen Menge genau $(n+1)\cdot n!=(n+1)!$.

Jetzt können wir auch unsere obigen Fragen beantworten: Es gibt $52!\approx \mathrm{8,07}\cdot 10^{67}$ verschiedene Anordnungen von $52$ Spielkarten, $20!\approx \mathrm{2,43}\cdot 10^{18}$ verschiedene Reihenfolgen, $20$ Bierflaschen zu trinken und $11!=39916800$ verschiedene Routen, um $11$ Sehenswürdigkeiten zu besuchen.