Fakultät (Mathematik)

Grundidee und Definition

Die Fakultät ist eine Funktion der Mathematik, die jeder natürlichen Zahl n das Produkt aller positiven natürlichen Zahlen zuordnet, die höchstens so groß wie n sind. Sie wird mit einem nachgestellten Ausrufezeichen geschrieben: n!. Für n gilt

n! := ∏_{k=1}^{n} k = 1 · 2 · 3 · ... · n.

Weil das leere Produkt den Wert 1 hat, gilt auch 0! = 1. Die Fakultät kann außerdem rekursiv definiert werden:

n! = 1 für n = 0, n! = n · (n−1)! für n > 0.

Die ersten Werte zeigen das Prinzip: 0! = 1, 1! = 1, 2! = 1 · 2 = 2, 3! = 1 · 2 · 3 = 6, 4! = 1 · 2 · 3 · 4 = 24. Weitere wichtige Werte sind 5! = 120, 6! = 720, 10! = 3.628.800, 20! = 2.432.902.008.176.640.000. Sehr große Fakultäten wachsen extrem schnell, zum Beispiel ist 50! ungefähr 3,041… · 10^64 und 100! ungefähr 9,332… · 10^157.

Kombinatorische Anwendungen

In der abzählenden Kombinatorik beschreibt n! die Anzahl der Möglichkeiten, n unterscheidbare Gegenstände in einer Reihe anzuordnen. Solche Anordnungen heißen Permutationen. Ist X eine n-elementige Menge, dann ist n! auch die Anzahl der bijektiven Abbildungen X → X, also der Permutationen von X. Das gilt auch für n = 0, weil es genau eine Möglichkeit gibt, die leere Menge auf sich selbst abzubilden.

Ein typisches Beispiel ist ein Autorennen mit sechs Fahrern, bei dem alle das Ziel erreichen. Für den ersten Platz gibt es 6 Möglichkeiten, danach für den zweiten noch 5, dann 4, 3, 2 und 1. Insgesamt gibt es also

6! = 6 · 5 · 4 · 3 · 2 · 1 = 720

verschiedene Ranglisten.

Eng verwandt ist der Binomialkoeffizient. Er gibt an, wie viele Möglichkeiten es gibt, aus einer n-elementigen Menge eine k-elementige Teilmenge auszuwählen:

(n über k) = n! / (k! · (n−k)!).

Beim Zahlenlotto 6 aus 49 gibt es nach dieser Formel

(49 über 6) = 49! / (6! · (49−6)!) = 13.983.816

mögliche Ziehungen. Die Wahrscheinlichkeit, mit einem Tipp bei 6 aus 49 zu gewinnen, beträgt deshalb 1/13.983.816 und ist damit kleiner als ein Zehnmillionstel.

Analysis und Reihen

Fakultäten treten auch in der Analysis auf. Bei höheren Ableitungen von Potenzfunktionen f(x) = x^n mit n ∈ N entstehen Produkte absteigender Faktoren. Durch wiederholtes Anwenden der Potenzregel erhält man

(x^n)' = n x^{n−1}, (x^n)'' = n(n−1)x^{n−2}, (x^n)^{(k)} = n(n−1) · ... · (n−k+1)x^{n−k} für k ≤ n.

Mit Fakultäten lässt sich das als

(x^n)^{(k)} = n! / (n−k)! · x^{n−k}

schreiben. Der Spezialfall für die n-te Ableitung lautet (x^n)^{(n)} = n!.

Eine weitere wichtige Rolle spielen Fakultäten in Taylorreihen. Für eine glatte Funktion f mit Entwicklungspunkt a lautet die Taylorreihe

Tf(x; a) := Σ_{n=0}^{∞} [f^{(n)}(a) / n!] · (x−a)^n.

Besonders einfach ist die Taylorreihe der Exponentialfunktion:

exp(x) = Σ_{k=0}^{∞} x^k / k! = 1/0! + x/1! + x^2/2! + x^3/3! + ... .

Für x = 1 ergibt sich die Eulersche Zahl e als Summe der Kehrwerte der Fakultäten:

e = exp(1) = Σ_{k=0}^{∞} 1/k! = 1/0! + 1/1! + 1/2! + 1/3! + ... .

Der Kehrwert von e entsteht entsprechend als alternierende Summe:

1/e = exp(−1) = Σ_{k=0}^{∞} (−1)^k/k! = 1/0! − 1/1! + 1/2! − 1/3! + ... .

Berechnung und Näherung

Der Wert von n! kann rekursiv oder iterativ berechnet werden, solange n nicht zu groß ist. Die rekursive Definition nutzt n! = n · (n−1)! mit 0! = 1. Eine iterative Berechnung multipliziert nacheinander die Zahlen von 1 bis n.

In der Praxis gibt es Grenzen durch den verfügbaren Zahlenbereich. Die größte Fakultät, die von den meisten handelsüblichen Taschenrechnern berechnet werden kann, ist 69! ≈ 1,7 · 10^98, denn 70! ≈ 1,2 · 10^100 liegt außerhalb des üblichen Zahlenbereichs. Im Gleitkommaformat double precision des IEEE-754-Standards ist 170! ≈ 7,3 · 10^306 die größte darstellbare Fakultät.

Mit Bibliotheken für sehr große Ganzzahlen lassen sich viel größere Fakultäten exakt berechnen. Als Beispiel nennt der Artikel 10.000!: Ein AMD Ryzen 3900X @4GHz benötigt dafür mit 64-bit-Code 2,22 ms und mit 32-bit-Code 9,26 ms. Die Dezimaldarstellung beginnt mit 284625968, hat insgesamt 35660 Stellen, und die letzten 2499 Stellen bestehen nur aus der Ziffer 0.

Für große n liefert die Stirling-Formel eine gute Näherung:

n! ~ √(2πn) · (n/e)^n.

Das Zeichen ~ bedeutet, dass der Quotient aus linker und rechter Seite für n → ∞ gegen 1 konvergiert. Für sehr große Zahlen kann man außerdem mit Funktionen wie lgamma, gammaln, loggamma, LogGamma oder Gamma.logGamma arbeiten, die ln|Γ(n)| berechnen. So erhält man beispielsweise

lg 10^9! ≈ lgamma(10^9 + 1) / ln 10 ≈ 8.565.705.522,995837

und damit

10^9! ≈ 9,9046 · 10^8.565.705.522.

Ähnliche Funktionen

Es gibt mehrere Funktionen, die der Fakultät ähneln oder sie verallgemeinern. Die Gammafunktion Γ(z) ist eine wichtige Verallgemeinerung der Fakultät auf komplexe Zahlen. Für z ∈ C mit Re(z) > 0 gilt

z! = Γ(z+1).

Eine Integraldarstellung ist

Γ(z) = ∫_0^∞ t^{z−1} e^{−t} dt = ∫_0^1 (−log t)^{z−1} dt.

Für z ∈ C \ Z_{≤0} kann sie weiter durch eine Summe und ein Integral beschrieben werden:

Γ(z) = Σ_{n=0}^{∞} [(-1)^n / (n!(n+z))] + ∫_1^∞ t^{z−1}e^{−t} dt.

Steigende und fallende Faktoriellen sind kombinatorische Verallgemeinerungen. Für sie gilt unter anderem (n)_n = (1)^n = n!.

Die Primfakultät oder das Primorial n# ist das Produkt aller Primzahlen kleiner oder gleich n:

n# = ∏_{p=2, p∈P}^{n} p.

Die Subfakultät !n kommt vor allem in der Kombinatorik vor und zählt alle fixpunktfreien Permutationen von n Elementen:

!n = n! · Σ_{k=0}^{n} (-1)^k/k!.

Die Doppelfakultät n!! multipliziert bei geradem n alle positiven geraden Zahlen bis n und bei ungeradem n alle positiven ungeraden Zahlen bis n. Es gilt

n!! = n · (n−2) · (n−4) · ...,

mit n!! = 1 für n ∈ {−1, 0}. Beispiele sind 6!! = 6 · 4 · 2 = 48 und 7!! = 7 · 5 · 3 · 1 = 105. Nützliche Beziehungen zur gewöhnlichen Fakultät sind

(2k)!! = 2^k k!, (2k−1)!! = (2k)! / (2^k k!).

Die Multifakultät verallgemeinert dieses Prinzip: Eine k-fache Fakultät n!^{(k)} wird rekursiv mit Schritten der Größe k definiert. Weitere verwandte Funktionen sind die Smarandache-Funktion, die Superfakultät und die Hyperfakultät.

Primzahlexponenten

Manchmal ist nicht die ganze Zahl n! gefragt, sondern nur der Exponent eines bestimmten Primfaktors in der Primfaktorzerlegung. Dafür verwendet man v_p(k), den Exponenten der Primzahl p in k. Für Fakultäten gilt die rekursive Formel

v_p(n!) = 0, falls n < p, v_p(n!) = ⌊n/p⌋ + v_p(⌊n/p⌋!) sonst.

Damit lässt sich zum Beispiel bestimmen, wie viele Nullen am Ende von 10.000! stehen. Endnullen entstehen durch Faktoren 10 = 2 · 5. Da in einer Fakultät mehr Faktoren 2 als Faktoren 5 vorkommen, reicht es, den Exponenten der 5 zu berechnen:

v_5(10.000!) = 2000 + v_5(2000!) = 2000 + 400 + v_5(400!) = 2000 + 400 + 80 + v_5(80!) = 2000 + 400 + 80 + 16 + v_5(16!) = 2000 + 400 + 80 + 16 + 3 + v_5(3!) = 2000 + 400 + 80 + 16 + 3 + 0 = 2499.

Also besitzt 10.000! am Ende 2499 Nullen.