Fakultät – Mathe für Nicht-Freaks

Aus Wikibooks
Wechseln zu: Navigation, Suche

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.

Definition[Bearbeiten]

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

Wie gesagt, ist die Fakultät 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:

Dialog-information.svg
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:

Accessories-calculator.svg

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:

Dialog-information.svg
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).

Blue pen icon.svg

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?

Help-content.svg

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.

Applications-office.svg

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.