Permutationen

In der abzählenden Kombinatorik spielen Fakultäten eine wichtige Rolle, weil ${\displaystyle n!}$ die Anzahl der Möglichkeiten ist, ${\displaystyle n}$ unterscheidbare Gegenstände in einer Reihe anzuordnen. Falls ${\displaystyle X}$ eine ${\displaystyle n}$-elementige Menge ist, so ist ${\displaystyle n!}$ auch die Anzahl der bijektiven Abbildungen ${\displaystyle X\to X}$ (die Anzahl der Permutationen). Dies gilt insbesondere auch für den Fall ${\displaystyle n=0}$, da es genau eine Möglichkeit gibt, die leere Menge auf sich selbst abzubilden.

Beispielsweise gibt es bei einem Autorennen mit sechs Fahrern ${\displaystyle 6!}$ verschiedene Möglichkeiten für die Reihenfolge beim Zieleinlauf, wenn alle Fahrer das Ziel erreichen. Für den ersten Platz kommen alle sechs Fahrer in Frage. Ist der erste Fahrer angekommen, können nur noch fünf Fahrer um den zweiten Platz konkurrieren. Für die Belegung des zweiten Platzes ist es maßgeblich, welcher der sechs Fahrer nicht berücksichtigt werden muss (da er bereits auf Rang 1 platziert ist). Daher muss für jede Belegungsmöglichkeit von Platz 1 gesondert gezählt werden, wie viele Belegungsmöglichkeiten für Platz 2 bestehen. Für die Belegung der Plätze 1 und 2 ergeben sich bei sechs Fahrern daher ${\displaystyle 6\cdot 5}$ Möglichkeiten. Ist auch der zweite Platz vergeben, kommen für den dritten Platz nur noch vier Fahrer in Frage, woraus sich für die ersten drei Plätze und sechs Fahrer ${\displaystyle 6\cdot 5\cdot 4}$ Belegungsmöglichkeiten ergeben usw. Letztlich gibt es also

${\displaystyle 6!=6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=720}$

verschiedene Ranglisten für den Zieleinlauf.

Binomialkoeffizienten

Ein Begriff, der in der abzählenden Kombinatorik eine ähnlich zentrale Stellung wie die Fakultät einnimmt, ist der Binomialkoeffizient

${\displaystyle {n \choose k}={\frac {n!}{k!\,(n-k)!}}}$.

Er gibt die Anzahl der Möglichkeiten an, eine ${\displaystyle k}$-elementige Teilmenge aus einer ${\displaystyle n}$-elementigen Menge auszuwählen. Umgekehrt gilt

${\displaystyle n!=\sum _{i=0}^{n-1}(-1)^{i}{\binom {n}{n-i}}(n-i)^{n}}$.

Hier ist das beliebteste Beispiel, das Zahlenlotto 6 aus 49 mit

${\displaystyle {49 \choose 6}={\frac {49!}{6!\,(49-6)!}}=13\,983\,816}$

Möglichkeiten.

Taylorreihen

Eine prominente Stelle, an der Fakultäten vorkommen, sind die Taylorreihen vieler Funktionen wie zum Beispiel der Sinusfunktion und der Exponentialfunktion.

Eulersche Zahl

Die eulersche Zahl ${\displaystyle \mathrm {e} }$ lässt sich als Summe der Kehrwerte der Fakultäten definieren:

${\displaystyle \mathrm {e} =\sum _{k=0}^{\infty }{\frac {1}{k!}}={\frac {1}{0!}}+{\frac {1}{1!}}+{\frac {1}{2!}}+{\frac {1}{3!}}+{\frac {1}{4!}}+\dotsb }$

Rekursive und iterative Berechnung

Der numerische Wert für ${\displaystyle n!}$ kann gut rekursiv oder iterativ berechnet werden, falls ${\displaystyle n}$ nicht zu groß ist.

Die größte Fakultät, die von den meisten handelsüblichen Taschenrechnern berechnet werden kann, ist ${\displaystyle 69!\approx 1{,}7\cdot 10^{98},}$ da ${\displaystyle 70!\approx 1{,}2\cdot 10^{100}}$ außerhalb des üblicherweise verfügbaren Zahlenbereiches liegt. Die größte als Gleitkommazahl im Format double precision des IEEE-754-Standards darstellbare Fakultät ist ${\displaystyle 170!\approx 7{,}3\cdot 10^{306}}$.

Pythonprogramm

Mit Bibliotheken für sehr große Ganzzahlen (keine Limitierung auf 32, 64 oder z. B. 512 Bit) benötigt zum Beispiel ein Intel Pentium 4 für die Berechnung von 10000! nur wenige Sekunden. Die Zahl hat 35660 Stellen in der Dezimaldarstellung, wobei die letzten 2499 Stellen nur aus der Ziffer Null bestehen.

# Syntax: Python 3.7
n = int(input('Fakultät von n = '))
f = 1
for i in range(1, n + 1):
    f *= i
print(f'{n}! = {f}')

Rekursive Lösung

def fak(n: int) -> int:
    return 1 if n <= 1 else n * fak(n - 1)

Java-Programm

public static int factorial(int n) {
    assert n >= 0;

    int val = 1;
    for(int i = 2; i <= n; ++i) {
        val *= i;
    }
    return val;
}

Rekursive Lösung

public static int factorial(int n) {
	if(n <= 1)
		return 1;
	// else
		return factorial(n - 1) * n;
	// end if
}

Näherung mit der Stirling-Formel

Wenn ${\displaystyle n}$ groß ist, bekommt man eine gute Näherung für ${\displaystyle n!}$ mit Hilfe der Stirling-Formel:

${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{\mathrm {e} }}\right)^{n}}$

Dabei bedeutet ${\displaystyle \sim }$, dass der Quotient aus linker und rechter Seite für ${\displaystyle n\to \infty }$ gegen ${\displaystyle 1}$ konvergiert.

Durch Approximation (statt Abschneiden) der Stirling-Reihe gelang Bill Gosper^[1] eine noch bessere Näherung:

${\displaystyle n!\sim {\sqrt {(2n+1/3)\pi }}\left({\frac {n}{\mathrm {e} }}\right)^{n}}$.

Gammafunktion

Die Gammafunktion ${\displaystyle \Gamma (z)}$ verallgemeinert die Fakultät um ihren Definitionsbereich von den natürlichen bis hin zu den komplexen Zahlen:

${\displaystyle z!=\Gamma (z+1),\qquad z\in \mathbb {C} }$, ${\displaystyle \Re {(z)}>0}$ ^[2]

${\displaystyle \Gamma (z)=\int \limits _{0}^{\infty }t^{z-1}\mathrm {e} ^{-t}\mathrm {d} t=\int _{0}^{1}{(-\log {t})^{z-1}\mathrm {d} t}}$

Für ${\displaystyle z\in \mathbb {C} \setminus \mathbb {Z_{\leq 0}} }$ kann die Gammafunktion folgendermaßen erweitert werden ^[3]:

${\displaystyle \Gamma (z)=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{n!(n+z)}}+\int _{1}^{\infty }t^{z-1}e^{-t}\mathrm {d} t}$

Faktorielle

Eine kombinatorische Verallgemeinerung stellen die steigenden und fallenden Faktoriellen ${\displaystyle (n)_{k}}$ und ${\displaystyle (n)^{k}}$ dar, denn ${\displaystyle (n)_{n}=(1)^{n}=n!}$.

Primorial (Primfakultät)

Die Primfakultät einer Zahl ist das Produkt der Primzahlen kleiner oder gleich der Zahl:

${\displaystyle n_{\#}=\prod _{\scriptstyle p\,=\,2 \atop \scriptstyle p\,\in \,\mathbb {P} }^{n}p\quad }$

Subfakultät

Die vor allem in der Kombinatorik auftretende Subfakultät

${\displaystyle !n=n!\cdot \sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

bezeichnet die Anzahl aller fixpunktfreien Permutationen von ${\displaystyle n}$ Elementen.

Doppelfakultät

Multifakultät

Analog zur doppelten Fakultät wird eine dreifache ( ${\displaystyle n!!!}$), vierfache ( ${\displaystyle n!!!!}$), …, ${\displaystyle k}$-fache Fakultät ( ${\displaystyle n!^{(k)}}$) rekursiv definiert als

${\displaystyle n!^{(k)}:={\begin{cases}1&{\text{falls }}n=0\\n&{\text{falls }}0<n\leq k\\n(n-k)!^{(k)}&{\text{falls }}n>k\end{cases}}}$ ^[5]

Superfakultät

Der Begriff Superfakultät ${\displaystyle \operatorname {sf} (n)}$ wird für (wenigstens) zwei unterschiedliche Funktionen verwendet;^[6] die eine ist definiert als das Produkt der ersten ${\displaystyle n}$ Fakultäten:

${\displaystyle \operatorname {sf} (n)=\prod _{i=1}^{n}i!=1!\cdot 2!\cdot 3!\cdot 4!\ \dotsm \ n!=G(n+2)}$ ^[6]

mit der Barnes’schen Funktion ${\displaystyle G(n)}$, die andere als mehrfache Potenz einer Fakultät:

${\displaystyle n\$=\underbrace {n!^{{n!}^{{\,\cdot }^{{\cdot }^{{\cdot \,}^{n!}}}}}} _{n!}.}$

Hyperfakultät

Die Hyperfakultät ${\displaystyle H_{n}}$ ist für natürliche ${\displaystyle n}$ folgendermaßen definiert:

${\displaystyle H(n)=\prod _{i=1}^{n}i^{i}=1^{1}\cdot 2^{2}\cdot 3^{3}\cdot 4^{4}\dotsm n^{n}}$ ^[7]

Sie kann durch die K-Funktion auf komplexe Zahlen verallgemeinert werden.

Verwandte Funktionen

• Smarandache-Funktion