Fakultät (Mathematik)

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
10	3.628.800
20	2,432… · 10¹⁸
50	3,041… · 10⁶⁴
100	9,332… · 10¹⁵⁷

Die Fakultät (manchmal, besonders in Österreich, auch Faktorielle genannt) ist in der Mathematik eine Funktion, die einer natürlichen Zahl das Produkt aller natürlichen Zahlen (ohne Null) kleiner und gleich dieser Zahl zuordnet. Sie wird durch ein dem Argument nachgestelltes Ausrufezeichen („!“) abgekürzt. Diese Notation wurde erstmals 1808 von dem elsässischen Mathematiker Christian Kramp (1760–1826) verwendet, der um 1798 auch die Bezeichnung faculté „Fähigkeit“ dafür einführte.

Inhaltsverzeichnis

DefinitionBearbeiten

Für alle natürlichen Zahlen $n$ ist

n!=1\cdot 2\cdot 3\dotsm n=\prod _{k=1}^{n}k

als das Produkt der natürlichen Zahlen von 1 bis $n$ definiert. Da das leere Produkt stets 1 ist, gilt

0!=1

Die Fakultät lässt sich auch rekursiv definieren:

n!={\begin{cases}1,&n=0\\n\cdot (n-1)!,&n>0\end{cases}}

Fakultäten für negative oder nicht ganze Zahlen sind nicht definiert. Es gibt aber eine Erweiterung der Fakultät auf solche Argumente (siehe Abschnitt Gammafunktion).

BeispieleBearbeiten

Diagramm von 0! bis 4!

{\begin{array}{rll}0!&=1&=1\\1!&=1&=1\\2!&=1\cdot 2&=2\\3!&=1\cdot 2\cdot 3&=6\\4!&=1\cdot 2\cdot 3\cdot 4&=24\\5!&=1\cdot 2\cdot 3\cdot 4\cdot 5&=120\\&\;\vdots \end{array}}

Die Werte der Fakultäten bilden die Folge A000142 in OEIS.

Explizite Fakultätswerte von 0 bis 20
0!	1
1!	1
2!	2
3!	6
4!	24
5!	120
6!	720
7!	5.040
8!	40.320
9!	362.880
10!	3.628.800
11!	39.916.800
12!	479.001.600
13!	6.227.020.800
14!	87.178.291.200
15!	1.307.674.368.000
16!	20.922.789.888.000
17!	355.687.428.096.000
18!	6.402.373.705.728.000
19!	121.645.100.408.832.000
20!	2.432.902.008.176.640.000

AnwendungenBearbeiten

PermutationenBearbeiten

In der abzählenden Kombinatorik spielen Fakultäten eine wichtige Rolle, weil $n!$ die Anzahl der Möglichkeiten ist, $n$ unterscheidbare Gegenstände in einer Reihe anzuordnen. Falls $X$ eine $n$ -elementige Menge ist, so ist $n!$ auch die Anzahl der bijektiven Abbildungen $X\to X$ (die Anzahl der Permutationen). Dies gilt insbesondere auch für den Fall $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 $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 $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 $6\cdot 5\cdot 4$ Belegungsmöglichkeiten ergeben usw. Letztlich gibt es also

6!=6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=720

verschiedene Ranglisten für den Zieleinlauf.

BinomialkoeffizientenBearbeiten

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

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

.

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

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

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

Möglichkeiten.

TaylorreihenBearbeiten

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

Eulersche ZahlBearbeiten

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

\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

Numerische Berechnung und NäherungBearbeiten

Die Fakultät und die Stirlingformel

Rekursive und iterative BerechnungBearbeiten

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

Die größte Fakultät, die von den meisten handelsüblichen Taschenrechnern berechnet werden kann, ist $69!\approx 1{,}7\cdot 10^{98},$ da $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 $170!\approx 7{,}3\cdot 10^{306}$ .

PythonprogrammBearbeiten

Wir setzen hier die Fakultätberechnung in die Programmiersprache Python um. (Man kann mit diesen Programmen je nach Prozessorarchitektur mit Zahlen von bis zu $2^{32-1}-1$ bei 32-bit bzw. $2^{64-1}-1$ bei 64-bit rechnen)

Auf einem Intel Pentium 4 benötigt zum Beispiel 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.

#!/usr/bin/env python3
# Syntax: Python 3.3.0
n = int(input('Fakultaet von n = '))
f = 1
for i in range(1, n + 1):
    f = f * i
print(n,'! = ',f)

#!/usr/bin/env python
# Syntax: Python 2.7
n = int(raw_input('Fakultaet von n = '))
f = 1
for i in range(1, n + 1):
    f = f * i
print n,'! = ',f

Rekursive Lösung

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

Java-ProgrammBearbeiten

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

Rekursive Lösung

public int factorial(int n) {
	if(n == 0) 
		return 1;
	return factorial(n - 1) * n;
}

Näherung mit der Stirling-FormelBearbeiten

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

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

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

Fakultät-ähnliche FunktionenBearbeiten

Es gibt eine Reihe weiterer Folgen und Funktionen, die in ihrer Definition oder ihren Eigenschaften ähnlich aussehen wie die Fakultät:

GammafunktionBearbeiten

Die Gammafunktion

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

n!=\Gamma (n+1),\qquad n\in \mathbb {N}

\Gamma (x)=\int \limits _{0}^{\infty }t^{x-1}\mathrm {e} ^{-t}\mathrm {d} t

FaktorielleBearbeiten

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

Primorial (Primfakultät)Bearbeiten

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

n_{\#}=\prod _{p\leq n,\;p{\text{ prim}}}p

SubfakultätBearbeiten

Die vor allem in der Kombinatorik auftretende Subfakultät

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

bezeichnet die Anzahl aller fixpunktfreien Permutationen von $n$ Elementen.

DoppelfakultätBearbeiten

DefinitionBearbeiten

Die seltener verwendete Doppelfakultät oder doppelte Fakultät ist für gerade $n$ das Produkt aller geraden Zahlen kleiner gleich $n$ . Für ungerade $n$ ist es das Produkt aller ungeraden Zahlen kleiner gleich $n$ .

Sie ist definiert als:^[1]

n!!={\begin{cases}n\cdot (n-2)\cdot (n-4)\dotsm 2&{\text{für }}n\ {\text{gerade und }}n>0,\\n\cdot (n-2)\cdot (n-4)\dotsm 1&{\text{für }}n\ {\text{ungerade und }}n>0,\\1&{\text{für }}n\in \{-1,0\}\end{cases}}

Häufig werden anstelle der Doppelfakultät Ausdrücke mit der gewöhnlichen Fakultät verwendet. Es gilt

(2k)!!=2^{k}k!

und

(2k-1)!!={\frac {(2k)!}{2^{k}k!}}

Werden nicht ganzzahlige Funktionswerte zugelassen, dann gibt es genau eine Erweiterung auf negative ungerade Zahlen, so dass $n!!=n\cdot (n-2)!!$ für alle ungeraden ganzen Zahlen $n$ gilt. Man erhält die Formel $n!!={\tfrac {1}{n+2}}\cdot {\tfrac {1}{n+4}}\dotsm {\tfrac {1}{1}}$ für ungerade $n<0$ .

Die Werte der Doppelfakultäten bilden die Folge A006882 in OEIS.

BeispieleBearbeiten

$6!!=6\cdot 4\cdot 2=48$
$7!!=7\cdot 5\cdot 3\cdot 1=105$

AnwendungsbeispieleBearbeiten

Die Anzahl $P_{2n}$ der $n$ -stelligen Kombinationen aus elementfremden Paaren gebildet aus $2n$ Elementen wird gegeben durch die Rekursion $P_{2n}=(2n-1)P_{2n-2}$ mit Rekursionsanfang $P_{2}=1$ (2 Elemente!). Auflösung der Rekursion ergibt $P_{2n}=(2n-1)!!$ . Sollen z. B. $2n$ Mannschaften durch Verlosung paarweise aufeinandertreffen, dann ist die Wahrscheinlichkeit, dass dabei zwei bestimmte gegeneinander spielen, gegeben durch ${\frac {P_{2n-2}}{P_{2n}}}={\frac {1}{2n-1}}$ .
Die Anzahl der Elemente der Hyperoktaedergruppe $B_{n}$ ist $(2n-1)!!$ .
Die Anzahl der fixpunktfreien involutorischen Permutationen von $2n$ Elementen ist $(2n)!!$ .
Das $2n$ -te Moment der Standardnormalverteilung ist $(2n-1)!!$ .
Auch in Integraltafeln und Formeln für spezielle Funktionen tritt die Doppelfakultät auf.
Für natürliche $n$ gilt $(2n-1)!!={\frac {2^{n}}{\sqrt {\pi }}}\Gamma \left(n+{\frac {1}{2}}\right)$ .

MultifakultätBearbeiten

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

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}}

^[2]

SuperfakultätBearbeiten

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

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

^[3]

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

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

HyperfakultätBearbeiten

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

H(n)=\prod _{i=1}^{n}i^{i}=1^{1}\cdot 2^{2}\cdot 3^{3}\cdot 4^{4}\dotsm n^{n}

^[4]

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

PrimzahlexponentenBearbeiten

Falls nicht die vollständige Zahl $n!$ gesucht ist, sondern nur der Exponent einer ihrer Primfaktoren, so lässt sich dieser direkt und effizient ermitteln.

v_{p}(n!)={\begin{cases}0&{\text{falls }}n<p\\\lfloor n/p\rfloor +v_{p}(\lfloor n/p\rfloor !)&{\text{sonst}}\end{cases}}

Hier steht $v_{p}(k)$ für den Exponenten von $p$ in der Primfaktorzerlegung von $k$ .

Im obigen Beispiel wäre für die Anzahl der Nullen am Ende von 10.000! der Exponent der 5 zu bestimmen, der Exponent der 2 ist auf jeden Fall größer.

{\begin{aligned}v_{5}(10{.}000!)&=2{.}000+v_{5}(2{.}000!)=2{.}000+400+v_{5}(400!)\\&=2{.}400+80+v_{5}(80!)=2{.}480+16+v_{5}(16!)\\&=2{.}496+3+v_{5}(3!)=2{.}499\end{aligned}}

WeblinksBearbeiten

Wikibooks: Mathe für Nicht-Freaks: Fakultät – Lern- und Lehrmaterialien

Peter Luschny: The Homepage of Factorial Algorithms. effiziente Algorithmen und weitere Informationen (englisch)
Eric W. Weisstein: Factorial. In: MathWorld (englisch).

EinzelnachweiseBearbeiten

↑ Eric W. Weisstein: Double Factorial. In: MathWorld (englisch).
↑ Eric W. Weisstein: Multifactorial. In: MathWorld (englisch).
↑ ^a ^b Eric W. Weisstein: Superfactorial. In: MathWorld (englisch).
↑ Eric W. Weisstein: Hyperfactorial. In: MathWorld (englisch).

[1] Eric W. Weisstein: Double Factorial. In: MathWorld (englisch).

[2] Eric W. Weisstein: Multifactorial. In: MathWorld (englisch).

[super-3] Eric W. Weisstein: Superfactorial. In: MathWorld (englisch).

[4] Eric W. Weisstein: Hyperfactorial. In: MathWorld (englisch).

[1]

[2]

[3]

[4]

Fakultät (Mathematik)

Inhaltsverzeichnis

DefinitionBearbeiten

BeispieleBearbeiten

AnwendungenBearbeiten

PermutationenBearbeiten

BinomialkoeffizientenBearbeiten

TaylorreihenBearbeiten

Eulersche ZahlBearbeiten

Numerische Berechnung und NäherungBearbeiten

Rekursive und iterative BerechnungBearbeiten

PythonprogrammBearbeiten

Java-ProgrammBearbeiten

Näherung mit der Stirling-FormelBearbeiten

Fakultät-ähnliche FunktionenBearbeiten

GammafunktionBearbeiten

FaktorielleBearbeiten

Primorial (Primfakultät)Bearbeiten

SubfakultätBearbeiten

DoppelfakultätBearbeiten

DefinitionBearbeiten

BeispieleBearbeiten

AnwendungsbeispieleBearbeiten

MultifakultätBearbeiten

SuperfakultätBearbeiten

HyperfakultätBearbeiten

Verwandte FunktionenBearbeiten

PrimzahlexponentenBearbeiten

WeblinksBearbeiten

EinzelnachweiseBearbeiten