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

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.

HerleitungBearbeiten

 
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 bei der kleinsten Menge mit nur einem Element ( ) und versuchen durch sukzessives 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 Elementen 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 unserer 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  .

DefinitionBearbeiten

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 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   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ätBearbeiten

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:

 

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.