Mathe für Nicht-Freaks: Fakultät

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

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:

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$:

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:

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:

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:

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

Datei:Die Definition der Fakultät.webm

Diagramm von 0! bis 4!

Die Fakultät $n!$ ist definiert als

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

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

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:

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:

Die Fakultät und die Stirlingformel

Schauen wir uns einige Beispiele an:

Die Fakultät wächst dabei sehr schnell. So ist $10!=3628800$ und $100!=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

Datei:Die rekursive Definition der Fakultät.webm 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:

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:

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:

Anwendungen der Fakultät Vorlage:Anker

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).

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

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}