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

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Die Fakultät ist nichts anderes als eine Kurzschreibweise für das Produkt . Die Fakultät ist insbesondere für die Kombinatorik wichtig, da sie die Anzahl der verschiedenen Anordnungen einer -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[Bearbeiten]

Durch progressives Einfügen der Zahlen , und kann man alle Anordnungen dieser Zahlen finden. Insgesamt ergeben sich 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 , so dass die Anzahl der unterschiedlichen Möglichkeiten ist, die Elemente einer -elementigen Menge anzuordnen.

Um diese Funktion zu finden, gehen wir induktiv vor. Zunächst beginnen wir der kleinsten Menge mit nur einem Element () und versuchen durch sukzessiven Einfügen neuer Elemente auf den Ergebnissen der vorherigen Schritte aufzubauen. Der Einfachheit halber betrachten wir nur Mengen der Form , da nur die Anzahl an Elemente relevant ist.

Beginnen wir mit der einelementigen Menge . 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 . Die neue Zahl kann ich an zwei Orten platzieren – vor und nach der :

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 ) an allen möglichen Stellen in den bereits bestehenden Anordnungen von zwei Elementen. Zunächst sieht man, dass man die Zahl an drei Stellen einfügen kann: links, mittig, rechts. Außerdem gibt es bereits zwei mögliche Anordnungen der Zahlen . Damit erhalten wir ingesamt neue Anordnungsmöglichkeiten:

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

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

Mit 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 entspricht der Anzahl der Blätter auf der -ten Ebene eines Baumes mit konstantem Verzweigungsgrad . Der Fakultätsbaum jedoch hat einen Verzweigungsgrad, der mit jeder neuen Ebene um zunimmt. Die Fakultät wächst also in der Großenordnung wie die Funktion .

Definition[Bearbeiten]

Die Definition der Fakultät (Video vom Podcast The Wicked Mu)
Diagramm von 0! bis 4!

Die Fakultät ist definiert als

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

Es fehlt noch der Ausdruck . Was soll hier das Ergebnis sein? In der Schreibweise mit dem endlichem 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 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:

Definition (Fakultät)

Für eine natürliche Zahl ist ihre Fakultät definiert durch:

Es ist .

Die Fakultät und die Stirlingformel

Schauen wir uns einige Beispiele an:

Beispiel (Beispiele zur Fakultät)

Es ist

Die Fakultät wächst dabei sehr schnell. So ist und , 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[Bearbeiten]

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 mit Hilfe von berechnet werden kann:

Frage: Wie kann mit Hilfe von berechnet werden?

Es ist

Der Rekursionsschritt lautet also

Mit Hilfe des obigen Rekursionsschritts kann auf zurückgeführt werden. Dieses wiederum kann durch berechnet werden, weil 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 , für die die Fakultät sinnvoll definiert werden kann, den Ausdruck angeben. Diese kleinste Zahl ist . Nun wissen wir aber bereits aus dem obigen Abschnitt, dass ist. Damit ergibt sich folgende rekursive Definition der Fakultät:

Definition (Rekursive Definition der Fakultät)

Die Fakultät ist rekursiv definiert durch:

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:

Animation zur rekursiven Definition der Fakultät

Verständnisfrage: Warum ist ?

Dies ergibt sich direkt aus dem Rekursionsschritt . In dieser Gleichung setzt man anstelle von einfach ein. Dies ergibt

Verständnisfrage: Vereinfache folgende Ausdrücke:

Es ist

Verständnisaufgabe: Beweise .

Aus der dritten binomischen Formel wissen wir . Damit ist

Dabei haben wir ausgenutzt, dass nach der Definition der Fakultät ist.

Anwendungen der Fakultät [Bearbeiten]

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 Elementen ist .

Dies bedeutet, dass die Anzahl der Permutationen einer Menge mit Elementen gleich ist. Mit Hilfe dieses Satzes können nun folgende Fragen beantwortet werden: Wie viele mögliche Anordnungen von  Spielkarten gibt es? Wenn ich  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 und .

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 an. Die Menge besitzt folgende mögliche Anordnungen:

Wir haben sechs mögliche Anordnungen gefunden (was entspricht). Analog können wir alle möglichen Anordnungen der 4-elementigen Menge finden:

Wir haben verschiedene Möglichkeiten der Anordnung gefunden (was 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 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 bestimmt), kommen wir auf insgesamt Möglichkeiten. Diese Argumentation entspricht einem Beweis mit vollständiger Induktion.

Beweis (Anordnungen einer endlichen Menge)

Aussageform, deren Allgemeingültigkeit für bewiesen werden soll:

Es gibt Möglichkeiten eine -elementige Menge anzuordnen.

1. Induktionsanfang:

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

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

Es gibt Möglichkeiten eine -elementige Menge anzuordnen.

2b. Induktionsbehauptung:

Es gibt Möglichkeiten eine -elementige Menge anzuordnen.

2c. Beweis des Induktionsschritts:

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

Jetzt können wir auch unsere obigen Fragen beantworten: Es gibt verschiedene Anordnungen von  Spielkarten, verschiedene Reihenfolgen,  Bierflaschen zu trinken und verschiedene Routen, um Sehenswürdigkeiten zu besuchen.