Fakultät - Factorial

Ausgewählte Mitglieder der faktoriellen Sequenz (Sequenz - A000142 im OEIS ); in wissenschaftlicher Schreibweise angegebene Werte werden auf die angezeigte Genauigkeit gerundet

n	n !
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
fünfzehn	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
25	1.551 121 004 × 10 25
50	3.041 409 320 × 10 64
70	1.197 857 167 × 10 100
100	9.332 621 544 × 10 157
450	1.733 368 733 × 10 1 000
1 000	4.023 872 601 × 10 2 567
3 249	6.412 337 688 × 10 10 000
10 000	2.846 259 681 × 10 35 659
25 206	1.205 703 438 × 10 100 000
100 000	2.824 229 408 × 10 456 573
205 023	2.503 898 932 × 10 1 000 004
1 000 000	8.263 931 688 × 10 5 565 708
10 100	1010 101,998 109 775 4820

In der Mathematik ist die Fakultät einer nicht-negativen ganzen Zahl n , bezeichnet mit n ! , ist das Produkt aller positiven ganzen Zahlen kleiner oder gleich n :

Zum Beispiel,

Der Wert 0! ist 1, gemäß der Konvention für ein leeres Produkt .

Die faktorielle Operation wird in vielen Bereichen der Mathematik angetroffen, insbesondere in der Kombinatorik , Algebra und mathematischen Analysis . Seine grundlegendste Verwendung zählt die möglichen unterschiedlichen Folgen – die Permutationen – von n unterschiedlichen Objekten: es gibt n ! .

Die faktorielle Funktion kann auch auf nicht-ganzzahligen Argumente erweitert , während seine wichtigsten Eigenschaften beibehalten werden durch die Definition von x ! = Γ( x + 1) , wobei Γ die Gammafunktion ist ; dies ist undefiniert, wenn x eine negative ganze Zahl ist.

Geschichte

Die Verwendung von Fakultäten ist seit der Talmudzeit (200 bis 500 n. Chr.) dokumentiert , eines der frühesten Beispiele ist das hebräische Schöpfungsbuch Sefer Yetzirah, das Fakultäten (bis zu 7!) als Mittel zum Zählen von Permutationen auflistet. Indische Gelehrte verwenden faktorielle Formeln mindestens seit dem 12. Jahrhundert. Siddhānta Shiromani von Bhāskara II ( ca. 1114–1185) erwähnt Fakultäten für Permutationen in Band I, dem Līlāvatī . Fabian Stedman beschrieb später Factorials als angewendet auf Change Ringing , eine musikalische Kunst, die das Läuten mehrerer gestimmter Glocken beinhaltet. Nach der Beschreibung eines rekursiven Ansatzes gibt Stedman eine Aussage über eine Fakultät (in der Sprache des Originals):

Nun ist die Natur dieser Methoden so, dass die Änderungen an einer Zahl die Änderungen an allen kleineren Zahlen umfassen ... insofern, als dass ein vollständiges Glockenspiel von Änderungen an einer Zahl durch Vereinigung der vollständigen Glockenzeichen an allen gebildet zu werden scheint kleinere Zahlen in einen ganzen Körper.

Notation

Factorial von n ist gekennzeichnet durch n ! oder n . Die Schreibweise n ! wurde 1808 von dem französischen Mathematiker Christian Kramp eingeführt .

Definition

Die Fakultätsfunktion ist definiert durch das Produkt

für ganze Zahl n ≥ 1 . Dies kann in Pi-Produktnotation geschrieben werden als

Dies führt zu der Rezidivbeziehung

Zum Beispiel, und so weiter.

Fakultät von Null

Die Fakultät von 0 ist 1 oder in Symbolen 0! = 1 .

Für diese Definition gibt es mehrere Beweggründe:

• Für n = 0 ist die Definition von n ! wie ein Produkt das Produkt von überhaupt keiner Zahl beinhaltet, und so ist ein Beispiel für die breitere Konvention, dass das Produkt von keinen Faktoren gleich der multiplikativen Identität ist (siehe Leeres Produkt ).
• Es gibt genau eine Permutation von Null-Objekten (mit nichts zu permutieren, die einzige Neuanordnung besteht darin, nichts zu tun).
• Es macht viele Identitäten in der Kombinatorik für alle anwendbaren Größen gültig. Die Anzahl der Möglichkeiten, 0 Elemente aus der leeren Menge auszuwählen , wird durch den Binomialkoeffizienten gegeben :
  $${\displaystyle {\binom {0}{0}}={\frac {0!}{0!0!}}=1.}$$

  
  Allgemeiner gesagt, die Anzahl der Möglichkeiten, alle n Elemente aus einer Menge von n auszuwählen, ist:
  $${\displaystyle {\binom {n}{n}}={\frac {n!}{n!0!}}=1.}$$

  
• Sie ermöglicht den kompakten Ausdruck vieler Formeln, wie der Exponentialfunktion , als Potenzreihe:
  $${\displaystyle e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}.}$$

  
• Es erweitert die Wiederholungsbeziehung auf 0.
• Es entspricht der Gamma-Funktion .${\displaystyle 0!=\Gamma (0+1)=1}$

Anwendungen

Obwohl die Fakultätsfunktion ihre Wurzeln in der Kombinatorik hat , kommen Formeln mit Fakultäten in vielen Bereichen der Mathematik vor.

• Es gibt n ! verschiedene Arten, n verschiedene Objekte zu einer Sequenz anzuordnen, die Permutationen dieser Objekte.
• Oftmals erscheinen im Nenner einer Formel Fakultäten, um zu erklären, dass die Reihenfolge ignoriert werden soll. Ein klassisches Beispiel ist das Zählen von k - Kombinationen (Teilmengen von k Elementen) aus einer Menge mit n Elementen. Man kann eine solche Kombination erhalten, indem man eine k -Permutation wählt: sukzessive Auswahl und Entfernung eines Elements der Menge, k- mal, für insgesamt
  $${\displaystyle (n-0)(n-1)(n-2)\cdots \left(n-(k-1)\right)={\frac {n!}{(nk)!}}=n ^{\underline{k}}}$$

  
  Möglichkeiten. Dies erzeugt jedoch die k- Kombinationen in einer bestimmten Reihenfolge, die man ignorieren möchte; da jede k -Kombination in k ! Auf verschiedene Weise ist die richtige Anzahl von k -Kombinationen
  $${\displaystyle {\frac {n(n-1)(n-2)\cdots (n-k+1)}{k(k-1)(k-2)\cdots 1}}={\frac { n^{\underline {k}}}{k!}}={\frac {n!}{(nk)!k!}}={\binom {n}{k}}.}$$

  
  Diese Zahl wird als Binomialkoeffizient bezeichnet , da sie auch der Koeffizient von x ^k in (1 + x ) ^{n ist} . Der Begriff wird oft als fallende Fakultät bezeichnet (ausgesprochen „ n zum fallenden k “).${\displaystyle n^{\underline {k}}}$
• Fakultäten treten in der Algebra aus verschiedenen Gründen auf, etwa durch die bereits erwähnten Koeffizienten der Binomialformel oder durch Mittelung über Permutationen zur Symmetrierung bestimmter Operationen.
• Auch in der Infinitesimalrechnung tauchen Fakultäten auf ; sie kommen beispielsweise in den Nennern der Terme der Taylor-Formel vor , wo sie als Kompensationsterme verwendet werden, da die n- te Ableitung von x ⁿ äquivalent zu n ist ! .
• Fakultäten werden auch in der Wahrscheinlichkeitstheorie und der Zahlentheorie ausgiebig verwendet ( siehe unten ).
• Fakultäten können nützlich sein, um die Expressionsmanipulation zu erleichtern. Zum Beispiel kann die Anzahl der k -Permutationen von n geschrieben werden als
  $${\displaystyle n^{\underline {k}}={\frac {n!}{(nk)!}}\,;}$$

  
  Während dies als Mittel zur Berechnung dieser Zahl ineffizient ist, kann es dazu dienen, eine Symmetrieeigenschaft von Binomialkoeffizienten zu beweisen:
  $${\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(nk)!k!}} ={\frac {n^{\underline {nk}}}{(nk)!}}={\binom {n}{nk}}\,.}$$

  
• Die Fakultätsfunktion kann mit der Potenzregel zu
  $${\displaystyle n!=D^{n}\,x^{n}={\frac {d^{n}}{dx^{n}}}\,x^{n}}$$

  
  wobei D ⁿ x ⁿ die Eulersche Notation für die n- te Ableitung von x ^{n ist} .

Wachstumsrate und Näherungen für große n

Wenn n wächst, wird die Fakultät n ! wächst schneller als alle Polynome und Exponentialfunktionen (aber langsamer als und doppelte Exponentialfunktionen ) in n . ${\displaystyle n^{n}}$

Die meisten Näherungen für n ! basieren auf der Approximation ihres natürlichen Logarithmus

Der Graph der Funktion f ( n ) = ln n ! ist in der Abbildung rechts dargestellt. Es sieht für alle vernünftigen Werte von n ungefähr linear aus , aber diese Intuition ist falsch. Wir erhalten eine der einfachsten Näherungen für ln n ! indem die Summe mit einem Integral von oben und unten wie folgt begrenzt wird:

das gibt uns die Schätzung

Daher ln n ! ∼ n ln n (siehe Big- O- Notation ). Dieses Ergebnis spielt eine Schlüsselrolle bei der Analyse der Rechenkomplexität von Sortieralgorithmen (siehe Vergleich sort ). Von den Grenzen auf ln n ! oben abgeleitet bekommen wir das

Manchmal ist es praktisch, schwächere, aber einfachere Schätzungen zu verwenden. Unter Verwendung der obigen Formel es leicht , dass für alle gezeigten n wir haben ( n/3) ⁿ < n ! , und für alle n ≥ 6 gilt n ! < (n/2) ⁿ .

Für große n erhalten wir eine bessere Schätzung für die Zahl n ! unter Verwendung der Stirling-Approximation :

Dies kommt tatsächlich aus einer asymptotischen Reihe für den Logarithmus, und n Fakultät liegt zwischen dieser und der nächsten Näherung:

Eine weitere Näherung für ln n ! wird von Srinivasa Ramanujan gegeben ( Ramanujan 1988 )

Sowohl dies als auch die Stirling-Approximation ergeben einen relativen Fehler in der Größenordnung von 1/n ³, aber Ramanujans ist ungefähr viermal genauer. Wenn wir jedoch zwei Korrekturterme in einer Näherung vom Stirling-Typ verwenden, wie bei der Näherung von Ramanujan, ist der relative Fehler von der Ordnung1/n ⁵:

Berechnung

Wenn die Effizienz keine Rolle spielt, ist die Berechnung von Fakultäten aus algorithmischer Sicht trivial: Die sukzessive Multiplikation einer auf 1 initialisierten Variablen mit den ganzen Zahlen bis zu n (falls vorhanden) berechnet n ! , sofern das Ergebnis in die Variable passt. In funktionalen Sprachen wird die rekursive Definition oft direkt implementiert, um rekursive Funktionen zu veranschaulichen.

Die größte praktische Schwierigkeit bei der Berechnung von Fakultäten ist die Größe des Ergebnisses. Um sicherzustellen, dass das genaue Ergebnis für alle zulässigen Werte selbst des kleinsten allgemein verwendeten Integraltyps ( 8-Bit-Ganzzahlen mit Vorzeichen) geeignet ist, wären mehr als 700 Bits erforderlich, sodass keine vernünftige Spezifikation einer Fakultätsfunktion mit Typen fester Größe Fragen vermeiden kann des Überlaufs . Die Werte 12! und 20! sind die größten Fakultäten, die in den 32-Bit- bzw. 64-Bit- Ganzzahlen gespeichert werden können, die üblicherweise in PCs verwendet werden , jedoch unterstützen viele Sprachen ganzzahlige Typen mit variabler Länge, die sehr große Werte berechnen können. Die Gleitkommadarstellung eines angenäherten Ergebnisses erlaubt es, etwas weiter zu gehen, aber auch dies bleibt durch einen möglichen Überlauf ziemlich eingeschränkt. Die meisten Taschenrechner verwenden die wissenschaftliche Schreibweise mit zweistelligen Dezimalexponenten, und die größte passende Fakultät ist dann 69!, denn 69! < 10 ¹⁰⁰ < 70! . Andere Implementierungen (wie Computersoftware wie Tabellenkalkulationsprogramme) können oft größere Werte verarbeiten.

Die meisten Softwareanwendungen berechnen kleine Fakultäten durch direkte Multiplikation oder Tabellensuche. Größere faktorielle Werte können mit der Stirling-Formel angenähert werden . Wolfram Alpha kann exakte Ergebnisse für die Berechnung der Deckenfunktion und Boden Funktion des angelegten binären , natürliche und dekadischen Logarithmus von n ! für Werte von n bis249 999 und bis zu20 000 000 ! für die ganzen Zahlen.

Wenn die genauen Werte großer Fakultäten benötigt werden, können sie mit Arithmetik beliebiger Genauigkeit berechnet werden . Anstelle der aufeinanderfolgenden Multiplikationen tun ((1 × 2) × 3) × 4 ... , ein Programm kann die Sequenz in zwei Teile unterteilen, deren Produkte ungefähr die gleiche Größe und mehrt mit ihnen einen Divide-and-Conquer - Verfahren . Dies ist oft effizienter.

Den asymptotisch besten Wirkungsgrad erhält man durch Berechnung von n ! aus seiner Primfaktorzerlegung. Wie von Peter Borwein dokumentiert , erlaubt die Primfaktorzerlegung n ! in der Zeit O ( n (log n log log n ) ² ) zu berechnen , vorausgesetzt, dass ein schneller Multiplikationsalgorithmus verwendet wird (zum Beispiel der Schönhage-Strassen-Algorithmus ). Peter Luschny präsentiert Quellcode und Benchmarks für mehrere effiziente faktorielle Algorithmen, mit oder ohne Verwendung eines Hauptsiebs .

Zahlentheorie

Fakultäten haben viele Anwendungen in der Zahlentheorie. Insbesondere n ! ist notwendigerweise durch alle Primzahlen bis einschließlich  n teilbar . Folglich ist n > 5 genau dann eine zusammengesetzte Zahl, wenn

Ein stärkeres Ergebnis ist der Satz von Wilson , der besagt, dass

genau dann, wenn p eine Primzahl ist.

Die Formel von Legendre gibt die Multiplizität der Primzahl p an, die bei der Primfaktorzerlegung von n auftritt ! wie

oder gleichwertig, wobei s _p ( n ) die Summe der Standard-Basis- p- Ziffern von n bezeichnet .

Addiere 1 zu einer Fakultät n ! ergibt eine Zahl, die nur durch Primzahlen, die größer als n sind, teilbar ist . Diese Tatsache kann verwendet werden, um den Satz von Euklid zu beweisen, dass die Anzahl der Primzahlen unendlich ist. Primzahlen der Form n ! ± 1 heißen faktorielle Primzahlen .

Reihe von Gegenseitigkeiten

Die Kehrwerte der Fakultäten ergeben eine konvergente Reihe, deren Summe die Exponentialbasis e ist :

Obwohl die Summe dieser Reihe eine irrationale Zahl ist , ist es möglich, die Fakultäten mit positiven ganzen Zahlen zu multiplizieren, um eine konvergente Reihe mit einer rationalen Summe zu erhalten: Die Konvergenz dieser Reihe gegen 1 ist daran zu erkennen, dass ihre Teilsummen sind . Daher bilden die Fakultäten keine Irrationalitätsfolge . ${\displaystyle {\frac {k!-1}{k!}}}$

Fakultät von nicht ganzzahligen Werten

Die Gamma- und Pi-Funktionen

Die Gammafunktion interpoliert die Fakultätsfunktion auf nicht ganzzahlige Werte. Der Haupthinweis ist die auf einen stetigen Bereich verallgemeinerte Rekursionsbeziehung .

Hauptartikel: Gamma-Funktion

Neben nichtnegativen ganzen Zahlen kann die Fakultät auch für nicht ganzzahlige Werte definiert werden, dies erfordert jedoch fortgeschrittenere Werkzeuge der mathematischen Analyse .

Eine häufig verwendete Funktion, die die Werte der Fakultät ausfüllt (aber mit einer Verschiebung um 1 im Argument), wird als Gamma-Funktion bezeichnet , die mit Γ( z ) bezeichnet wird . Sie ist für alle komplexen Zahlen z mit Ausnahme der nicht positiven ganzen Zahlen definiert und gegeben, wenn der Realteil von z positiv ist um

$${\displaystyle \Gamma(z)=\int_{0}^{\infty}t^{z-1}e^{-t}\,dt.}$$

Seine Beziehung zur Fakultät ist, dass n ! = Γ( n + 1) für jede nichtnegative ganze Zahl n .

Die ursprüngliche Formel von

Euler für die Gammafunktion war

$${\displaystyle \Gamma(z)=\lim_{n\to \infty }{\frac {n^{z}n!}{\displaystyle \prod_{k=0}^{n}(z+k )}}.}$$

Carl Friedrich Gauß benutzte die Notation Π( z ) , um dieselbe Funktion zu bezeichnen, jedoch mit einem um 1 verschobenen Argument, so dass es mit der Fakultät für nichtnegative ganze Zahlen übereinstimmt. Diese Pi-Funktion ist definiert durch

$${\displaystyle \Pi(z)=\int_{0}^{\infty}t^{z}e^{-t}\,dt.}$$

Die pi-Funktion und die Gamma-Funktion sind durch die Formel Π( z ) = Γ( z +1) verbunden . Ebenso gilt ( n ) = n ! für jede nichtnegative ganze Zahl n .

Die Fakultätsfunktion, verallgemeinert auf alle reellen Zahlen außer negativen ganzen Zahlen. Zum Beispiel 0! = 1! = 1 , (−1/2)! = √ π ,1/2! =√ π/2.

Darüber hinaus erfüllt die pi-Funktion die gleiche Rekursion wie Fakultäten, jedoch bei jedem komplexen Wert z, in dem sie definiert ist

$${\displaystyle \Pi(z)=z\Pi(z-1)\,.}$$

Dies ist keine Rekursionsbeziehung mehr, sondern eine Funktionsgleichung . In Bezug auf die Gammafunktion ist es

$${\displaystyle \Gamma (n+1)=n\Gamma (n)\,.}$$

Die Werte dieser Funktionen bei halbzahligen Werten werden daher durch eine einzige davon bestimmt:

$${\displaystyle \Gamma \left({\frac {1}{2}}\right)=\left(-{\frac {1}{2}}\right)!=\Pi \left(-{\frac {1}{2}}\right)={\sqrt {\pi}}\,,}$$

aus dem es , dass für die folgt  n ∈ N ,

$${\displaystyle {\begin{ausgerichtet}&\Gamma \left({\frac {1}{2}}+n\right)=\left(-{\frac {1}{2}}+n\right) !=\Pi \left(-{\frac {1}{2}}+n\right)\\[5pt]={}&{\sqrt {\pi}}\prod_{k=1}^{ n}{\frac {2k-1}{2}}={\frac {(2n)!}{4^{n}n!}}{\sqrt {\pi}}={\frac {(2n- 1)!}{2^{2n-1}(n-1)!}}{\sqrt {\pi}}\,.\end{ausgerichtet}}}$$

Zum Beispiel,

$${\displaystyle \Gamma \left({\frac {9}{2}}\right)={\frac {7}{2}}!=\Pi \left({\frac {7}{2}}\ rechts)={\frac {1}{2}}\cdot {\frac {3}{2}}\cdot {\frac {5}{2}}\cdot {\frac {7}{2}}{ \sqrt {\pi}}={\frac {8!}{4^{4}4!}}{\sqrt {\pi}}={\frac {7!}{2^{7}3!} }{\sqrt {\pi}}={\frac {105}{16}}{\sqrt {\pi}}\approx 11,631\,728\ldots}$$

Daraus folgt auch , dass für  n ∈ N ,

$${\displaystyle \Gamma \left({\frac {1}{2}}-n\right)=\left(-{\frac {1}{2}}-n\right)!=\Pi \left( -{\frac{1}{2}}-n\right)={\sqrt {\pi}}\prod_{k=1}^{n}{\frac{2}{1-2k}}= {\frac {\left(-4\right)^{n}n!}{(2n)!}}{\sqrt {\pi}}\,.}$$

Zum Beispiel,

$${\displaystyle \Gamma \left(-{\frac {5}{2}}\right)=\left(-{\frac {7}{2}}\right)!=\Pi \left(-{\ frac {7}{2}}\right)={\frac {2}{-1}}\cdot {\frac {2}{-3}}\cdot {\frac {2}{-5}}{ \sqrt {\pi}}={\frac {\left(-4\right)^{3}3!}{6!}}{\sqrt {\pi}}=-{\frac {8}{15 }}{\sqrt {\pi}}\approx -0,945\,308\ldots}$$

Die pi-Funktion ist sicherlich nicht die einzige Möglichkeit, Fakultäten zu einer Funktion zu erweitern, die bei fast allen komplexen Werten definiert ist, und nicht einmal die einzige, die analytisch ist, wo immer sie definiert ist. Trotzdem wird es normalerweise als der natürlichste Weg angesehen, die Werte der Fakultäten zu einer komplexen Funktion zu erweitern. Zum Beispiel besagt das Bohr-Mollerup-Theorem , dass die Gammafunktion die einzige Funktion ist, die den Wert 1 bei 1 annimmt, die Funktionsgleichung Γ( n + 1) = n Γ( n ) erfüllt , auf den komplexen Zahlen meromorph ist und ist log-konvex auf der positiven reellen Achse. Eine ähnliche Aussage gilt auch für die pi-Funktion unter Verwendung der ( n ) = n Π( n − 1) Funktionsgleichung.

Es gibt jedoch komplexe Funktionen, die im Sinne der analytischen Funktionentheorie wahrscheinlich einfacher sind und die Fakultätswerte interpolieren. Zum Beispiel die 'Gamma'-Funktion von Hadamard (

Hadamard 1894 ), die im Gegensatz zur Gamma-Funktion eine vollständige Funktion ist . Harv-Fehler: kein Ziel: CITEREFHadamard1894 ( Hilfe )

Euler entwickelte auch eine konvergente Produktapproximation für die nicht ganzzahligen Fakultäten, die der Formel für die obige Gammafunktion äquivalent ist:

$${\displaystyle {\begin{aligned}n!=\Pi(n)&=\prod_{k=1}^{\infty}\left({\frac {k+1}{k}}\right) ^{n}\!\!{\frac {k}{n+k}}\\&=\left[\left({\frac {2}{1}}\right)^{n}{\frac {1}{n+1}}\right]\left[\left({\frac{3}{2}}\right)^{n}{\frac{2}{n+2}}\right] \left[\left({\frac {4}{3}}\right)^{n}{\frac {3}{n+3}}\right]\cdots \end{aligned}}}$$

Diese Formel bietet jedoch kein praktisches Mittel zur Berechnung der Pi-Funktion oder der Gamma-Funktion, da ihre Konvergenzrate langsam ist.

Anwendungen der Gammafunktion

Das Volumen einer n- dimensionalen Hypersphäre vom Radius R ist

$${\displaystyle V_{n}={\frac {\pi^{n/2}}{\Gamma \left({\frac{n}{2}}+1\right)}}R^{n}\ ,.}$$

Fakultät in der komplexen Ebene

Amplitude und Phase der Fakultät eines komplexen Arguments

Die Darstellung durch die Gamma-Funktion ermöglicht die Auswertung von Fakultäten oder komplexen Argumenten. Amplituden- und Phasengleichgewichte der Fakultät sind in der Abbildung dargestellt. Lassen

$${\displaystyle f=\rho e^{i\varphi}=(x+iy)!=\Gamma (x+iy+1)\,.}$$

Mehrere Ebenen konstanter Modulus (Amplitude) ρ und konstante Phase & phgr; dargestellt sind. Das Gitter deckt den Bereich −3 x ≤ 3 , −2 ≤ y ≤ 2 mit Einheitsschritten ab. Die gestrichelte Linie zeigt den Pegel φ = ±π .

Dünne Linien zeigen Zwischenniveaus von konstantem Modul und konstanter Phase. An den Polen bei jeder negativen ganzen Zahl sind Phase und Amplitude nicht definiert. Äquilinien sind dicht in der Nähe von Singularitäten entlang negativer ganzzahliger Werte des Arguments.

Für | z | < 1 können die Taylor-Entwicklungen verwendet werden:

$${\displaystyle z!=\sum_{n=0}^{\infty}g_{n}z^{n}\,.}$$

Die ersten Koeffizienten dieser Entwicklung sind

n	g nein	Annäherung
0	1	1
1	− γ	−0,577 215 6649
2	π 2/12 + γ 2/2	0,989 055 9955
3	−ζ (3)/3 − π 2/12 − γ 3/6	−0,907 479 0760

wobei γ die Euler-Mascheroni-Konstante und ζ die Riemannsche Zetafunktion ist . Computeralgebrasysteme können viele Terme dieser Erweiterung erzeugen.

Näherungen der Fakultät

Für die großen Werte des Arguments kann die faktorielle durch den Logarithmus der Gamma - Funktion angenähert werden, indem eine Kettenbruch Darstellung. Dieser Ansatz geht auf TJ Stieltjes (1894) zurück. Schreiben

$${\displaystyle \ln \Gamma(z)=p(z)+{\frac {\ln 2\pi}{2}}-z+\left(z+{\frac{1}{2}}\right)\ ln(z)\,,}$$

Stieltjes gab eine Kettenfraktion für : ${\displaystyle p(z)}$

$${\displaystyle p(z)={\cfrac {a_{0}}{z+{\cfrac {a_{1}}{z+{\cfrac {a_{2}}{z+{\cfrac {a_{3}} {z+\ddots}}}}}}}}}}$$

Die ersten Koeffizienten sind ${\displaystyle a_{n}}$

n	ein nein
0	1/12
1	1/30
2	53/210
3	195/371
4	22 999/22 737
5	29 944 523/19 733 142
6	109 535 241 009/48 264 275 462

Der Kettenbruch konvergiert iff . Die Konvergenz ist in der Nähe der imaginären Achse schlecht. Wenn die sechs Koeffizienten oben ausreichend sind, um die Fakultät mit komplexer doppelter Genauigkeit zu bewerten. Für eine höhere Genauigkeit können mehr Koeffizienten durch ein rationales QD-Schema (Rutishausers QD-Algorithmus) berechnet werden. ${\displaystyle \Re(z)>0}$${\displaystyle \Re(z)>2}$

Nicht-Erweiterbarkeit auf negative ganze Zahlen

Die Beziehung n ! = n × ( n  − 1)! ermöglicht es einem, die Fakultät für eine ganze Zahl zu berechnen, wenn die Fakultät für eine kleinere ganze Zahl gegeben ist. Die Beziehung kann invertiert werden, so dass man die Fakultät für eine ganze Zahl berechnen kann, wenn die Fakultät für eine größere ganze Zahl gegeben ist:

$${\displaystyle (n-1)!={\frac {n!}{n}}.}$$

Diese Rekursion erlaubt uns jedoch nicht, die Fakultät einer negativen ganzen Zahl zu berechnen; Verwendung der Formel zur Berechnung von (−1)! würde eine Division eines Wertes ungleich null durch null erfordern und uns somit daran hindern, einen Fakultätswert für jede negative ganze Zahl zu berechnen. Ebenso ist die Gammafunktion nicht für null oder negative ganze Zahlen definiert, obwohl sie für alle anderen komplexen Zahlen definiert ist.

Fakultätsähnliche Produkte und Funktionen

Es gibt mehrere andere ganzzahlige Folgen ähnlich der Fakultät, die in der Mathematik verwendet werden:

Rückwärtsfakultät

Die Notation wird manchmal verwendet, um das Produkt der

n ganzen Zahlen darzustellen, die bis einschließlich x zählen (dh ). ${\displaystyle x^{(n)}}$${\textstyle {\frac {x!}{(x-(n-1))!}}}$

Dies wird auch als fallende Fakultät bezeichnet .

Doppelfakultät

Hauptartikel: Doppelfakultät

Das Produkt aller ungeraden ganzen Zahlen bis zu einer ungeraden positiven ganzen Zahl n wird die Doppelfakultät von n genannt und mit n !! . Das ist,

${\displaystyle (2k-1)!!=\prod_{i=1}^{k}(2i-1)={\frac {(2k)!}{2^{k}k!}}={ \frac {_{2k}P_{k}}{2^{k}}}={\frac {\left(2k\right)^{\underline {k}}}{2^{k}}}\ ,.}$

Zum Beispiel 9!! = 1 × 3 × 5 × 7 × 9 = 945 .

Die Folge der Doppelfakultäten für n = 1, 3, 5, 7,... beginnt als

1, 3, 15, 105, 945, 10 395 ,135 135 ,... (Sequenz A001147 im OEIS )

Die doppelfaktorielle Notation kann verwendet werden, um den Ausdruck bestimmter trigonometrischer Integrale zu vereinfachen , einen Ausdruck für die Werte der Gammafunktion bei halbzahligen Argumenten und das Volumen von Hypersphären bereitzustellen und viele Zählprobleme in der Kombinatorik zu lösen, einschließlich des Zählens von Binärbäumen mit beschriftete Blätter und perfekte Übereinstimmungen in vollständigen Graphen .

Multifaktorielle Faktoren

Eine übliche verwandte Notation ist die Verwendung mehrerer Ausrufezeichen, um eine multifaktorielle , das Produkt von ganzen Zahlen in Schritten von zwei ( n !! ), drei ( n !!! ) oder mehr zu bezeichnen (siehe Verallgemeinerungen der doppelten Fakultät ). Die doppelte Fakultät ist die am häufigsten verwendete Variante, aber man kann auch die dreifache Fakultät ( n !!! ) und so weiter definieren. Man kann die k- Tupel-Fakultät definieren, die mit n bezeichnet wird

! ^{( k )} , rekursiv für positive ganze Zahlen als

$${\displaystyle n!^{(k)}={\begin{cases}n&{\text{if}}0<n\leq k,\\n\left({(nk)!}^{(k) }\right)&{\text{if }}n>k.\end{cases}}}$$

Außerdem ähnlich 0! =1!/1= 1 , kann man definieren:

$${\displaystyle {n!}^{(k)}=1\quad {\text{if}}\ {-k}<n\leq 0.}$$

Für hinreichend großes n ≥ 1 wird die gewöhnliche einfaktorielle Funktion wie folgt durch die multifaktoriellen Funktionen entwickelt:

$${\displaystyle {\begin{aligned}n!&=n!!\cdot (n-1)!!\,,&n&\geq 1\\[5px]&=n!!!\cdot (n-1) !!!\cdot (n-2)!!!\,,&n&\geq 2\\[5px]&=\prod _{i=0}^{k-1}(ni)!^{(k) },\quad {\text{ für }}k\in\mathbb{Z}^{+}\,,&n&\geq k-1.\end{ausgerichtet}}}$$

Genauso wie n ! ist nicht für negative ganze Zahlen definiert und n !! ist für negative gerade ganze Zahlen nicht definiert, n ! ^{( k )} ist nicht für negative ganze Zahlen definiert, die durch k teilbar sind .

Primorial

Hauptartikel: Primorial

Die Primoriale einer natürlichen Zahl n (Sequenz A002110 im OEIS ), bezeichnet mit n # , ähnelt der Fakultät, aber das Produkt wird nur über die Primzahlen kleiner oder gleich n genommen . Das ist,

$${\displaystyle n\#=\prod_{p\leq n}p,}$$

wobei p über die Primzahlen kleiner oder gleich n reicht . Zum Beispiel ist das Primorial von 11

$${\displaystyle 11\#=11\times 7\times 5\times 3\times 2=2310.}$$

kompositorisch

Das Kompositorium einer natürlichen Zahl n (Sequenz A036691 im OEIS ) ähnelt der Fakultät, aber das Produkt wird nur über die zusammengesetzten Zahlen kleiner oder gleich n genommen . Zum Beispiel ist das Compositorial von 11

$${\displaystyle 10\times 9\times 8\times 6\times 4=17280.}$$

Fibonorial

Hauptartikel: Fibonorial

Das Fibonorial ist das Produkt der ersten n positiven Fibonacci-Zahlen.

Die Folge der Fibonorials beginnt als

1, 1, 1, 2, 6, 30, 240, 3120 ,65 520 ,... (Sequenz A003266 im OEIS )

Subfaktoriell

Die Subfaktorielle ergibt die Anzahl der Störungen einer Menge von Objekten. Sein Wert ist: ${\displaystyle n}$

${\displaystyle !n=\operatorname {nint} \left({\frac {n!}{e}}\right)}$

wobei und "nint" die Funktion bezeichnet, die ihre Eingabe auf die nächste ganze Zahl rundet (in diesem Fall wird es keine Mehrdeutigkeit/Bindungen geben, da es immer eine ganze Zahl und eine algebraisch unabhängige Transzendenz ist, nämlich die natürliche Basis / Eulersche Zahl). ${\displaystyle n\in\mathbb{Z}^{+}\cup\{0\}}$${\displaystyle n!}$${\displaystyle e}$

Superfaktoriell

Siehe auch: Große Zahlen

"N$" leitet hier weiter. Für die Währung siehe Namibischer Dollar .

Neil Sloane und Simon Plouffe definierten eine Superfaktorielle in The Encyclopedia of Integer Sequences (Academic Press, 1995) als das Produkt der ersten n Fakultäten. Die Superfaktorielle von 4 ist also

$${\displaystyle \operatorname {sf} (4)=1!\times 2!\times 3!\times 4!=288\,.}$$

Im Allgemeinen

$${\displaystyle {\begin{aligned}\operatorname {sf} (n)=\prod_{k=1}^{n}k!&=\prod_{k=1}^{n}k^{n -k+1}\\&=1^{n}\cdot 2^{n-1}\cdot 3^{n-2}\cdots (n-1)^{2}\cdot n^{1} \,.\end{ausgerichtet}}}$$

Äquivalent ist die Superfaktorielle durch die Formel

$${\displaystyle \operatorname {sf} (n)=\prod_{0\leq i<j\leq n}(ji)}$$

das ist die Determinante einer Vandermonde-Matrix .

Die Superfaktoren können mit der Barnes-G-Funktion auf alle komplexen Zahlen erweitert

werden , so dass für alle positiven ganzen Zahlen n . Die Folge der Superfaktoriellen beginnt (ab n = 0 ) als ${\displaystyle G(n)=\operatorname {sf} (n)}$

1, 1, 2, 12, 288, 34 560 ,24 883 200 ,125 411 328 000 ,... (Sequenz A000178 im OEIS )

Mit dieser Definition können wir die k- Superfaktorielle von n (bezeichnet als sf _k ( n ) ) definieren als:

$${\displaystyle \operatorname {sf} _{k}(n)={\begin{cases}n&{\text{if }}k=0\\\prod_{r=1}^{n}\operatorname { sf} _{k-1}(r)&{\text{if}}k\geq 1\end{cases}}}$$

Die 3-Superfaktoriellen von n sind

1, 1, 2, 24, 6 912 ,238 878 720 ,5 944 066 965 504 000 ,745 453 331 864 786 829 312 000 000 ,... (Sequenz A055462 im OEIS )

Das 0-superfaktorielle von n ist n .

Pickovers superfaktoriell

In seinem 1995 erschienenen Buch Keys to Infinity , Clifford Pickover definiert eine andere Funktion n $ , dass er die superfactorial genannt. Es ist definiert durch

$${\displaystyle n\$\equiv {\begin{matrix}\underbrace {n!^{{n!}^{{\cdot }^{{\cdot }^{{\cdot }^{n!}}} }}} \\n!{\mbox{ Kopien von }}n!\end{matrix}}.}$$

Diese Sequenz von Superfaktoren beginnt

$${\displaystyle {\begin{aligned}1\$&=1\,,\\2\$&=2^{2}=4\,,\\3\$&=6^{6^{6^ {6^{6^{6}}}}}\,.\end{ausgerichtet}}}$$

(Hier wird, wie bei zusammengesetzten Exponentiationen üblich , die Gruppierung von rechts nach links verstanden: a ^{b c} = a ^{( b c )} .)

Diese Operation kann auch als die tetration . ausgedrückt werden

$${\displaystyle n\$={}^{n!}(n!)\,,}$$

oder mit Knuths Aufwärtspfeil-Notation als

$${\displaystyle n\$=(n!)\uparrow\uparrow(n!)=(n!)\uparrow\uparrow\uparrow 2\,.}$$

Hyperfaktoriell

Gelegentlich wird die hyperfaktorielle von n betrachtet. Es wird als H ( n ) geschrieben und definiert durch

$${\displaystyle {\begin{aligned}H(n)&=\prod_{k=1}^{n}k^{k}\\&=1^{1}\cdot 2^{2}\cdot 3^{3}\cdots (n-1)^{n-1}\cdot n^{n}.\end{ausgerichtet}}}$$

Für n = 1, 2, 3, 4,... sind die Werte von H ( n ) 1, 4, 108,27 648 ,... (Sequenz A002109 im OEIS ).

Die asymptotische Wachstumsrate beträgt

$${\displaystyle H(n)\sim An^{(6n^{2}+6n+1)/12}e^{-n^{2}/4}}$$

wobei A = 1,2824... die Glaisher-Kinkelin-Konstante ist . H (14) ≈ 1.8474 × 10 ⁹⁹ ist schon fast gleich einem Googol und H (15) ≈ 8,0896 × 10 ¹¹⁶ ist fast so groß wie die Shannon-Zahl , die theoretische Anzahl möglicher Schachpartien. Im Vergleich zur Pickover-Definition des Superfaktoriellen wächst der Hyperfaktoriell relativ langsam.

Die hyperfaktorielle Funktion kann auf ähnliche Weise wie die Fakultätsfunktion auf komplexe Zahlen verallgemeinert werden. Die resultierende Funktion wird die genannte K -Funktion .

Siehe auch

• Abwechselnde Fakultät
• Bhargava-Fakultät
• Digamma-Funktion
• Exponentielle Fakultät
• Fakultätszahlensystem
• Fabrikation
• Liste der faktoriellen und binomialen Themen
• Pochhammer-Symbol , das die fallende oder steigende Fakultät angibt
• Nachgestellte Nullen der Fakultät
• Dreieckszahl , das additive Analogon von factorial

Verweise

Zitate

Quellen

• Bostock, Linda; Krämer, Suzanne ; Rourke, C. (2014-11-01), Weitere reine Mathematik , Nelson Thornes, ISBN 9780859501033
• Graham, Ronald L. ; Knuth, Donald E. ; Patashnik, Oren (1988), Konkrete Mathematik , Lesen, MA: Addison-Wesley, ISBN 0-201-14236-8
• Guy, Richard K. (2004), "E24 Irrationalitätsfolgen", Ungelöste Probleme der Zahlentheorie (3. Aufl.), Springer-Verlag , ISBN 0-387-20860-7, Zbl  1058.11001
• Higgins, Peter (2008), Zahlengeschichte: Vom Zählen zur Kryptographie , New York: Copernicus, ISBN 978-1-84800-000-1
• Stedman, Fabian (1677), Campanalogia , London Der Herausgeber wird als "WS" angegeben, der möglicherweise William Smith war, möglicherweise als Vertreter der Society of College Youths , an die sich die "Widmungsgruppe" richtet.

Weiterlesen

• Hadamard, MJ (1968) [1894], "Sur L'Expression Du Produit 1·2·3· · · · ·( n −1) Par Une Fonction Entière" (PDF) , uvres de Jacques Hadamard (auf Französisch), Paris: Centre National de la Recherche Scientifiques
• Ramanujan, Srinivasa (1988), The Lost Notebook and Other Unpublished Papers , Springer Berlin, S. 339, ISBN 3-540-18726-X

Externe Links

• "Factorial" , Enzyklopädie der Mathematik , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Factorial" . MathWorld .
• Factorial bei PlanetMath .