Factorielle

À propos de ce écoles sélection Wikipedia

SOS Enfants, un organisme de bienfaisance de l'éducation , a organisé cette sélection. Mères SOS chaque regard après une une famille d'enfants parrainés .

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
15	1307674368000
20	2432902008176640000
25	15511210043330985984000000
50	3.04140932 ... × 10 ⁶⁴
70	1.19785717 ... × 10 ¹⁰⁰
450	1.73336873 ... × 10 ¹⁰⁰⁰
3249	6.41233768 ... × 10 ^{10 000}
25206	1,205703438 ... × 10 ^{100 000}
47176	8,4485731495 ... × 10 ^{200 001}
100000	2,8242294079 ... × 10 ^{456 573}

Les quelques premiers membres sélectionnés et grands de la séquence des factorielles (séquence A000142 dans OEIS )

En mathématiques , la factorielle d'un non-négative entier n, notée n!, est le produit de l'ensemble des entiers positifs inférieurs ou égaux à n. Par exemple,

$5! = 1 \ 2 fois \ times 3 \ 4 \ fois fois 5 = 120 \$

$6! = 1 \ 2 fois \ times 3 \ 4 \ fois fois 5 fois 6 \ = 720 \$

où n! représente n factorielle. La notation n! a été présenté par Christian Kramp en 1808 .

Définition

La fonction factorielle est formellement défini par

$n! = \ prod_ {k = 1} ^ nk \ qquad \ forall n \ in \ mathbb {N}. \!$

La définition ci-dessus incorpore l'instance

$0! = 1 \$

comme un exemple du fait que le aucun produit de numéros à tous est 1. Ce fait pour factorielles est utile, parce

la relation récursive $(N + 1)! = N! \ Fois (n + 1)$ fonctionne pour $n = 0$ ;
cette définition fait de nombreuses identités combinatoire valables pour zéro tailles.
- En particulier, le nombre de combinaisons ou permutations d'un ensemble vide est, tout simplement, une.

Applications

Factorielles sont utilisés dans la combinatoire . Par exemple, il existe $n!$ différentes manières de disposer n objets distincts dans une séquence. (Les arrangements sont appelés permutations .) Et le nombre de façons on peut choisir k objets parmi un ensemble donné de n objets (le nombre de combinaisons), est donnée par la soi-disant coefficient binomial

${N \ choisir k} = {n! \ Over k! (N-k)!}.$

Dans permutations , si $r$ les objets peuvent être choisis parmi un total de n objets et disposées de différentes façons, où r ≤ n, alors le nombre total de permutations différentes est donnée par:

${} _nP_r = \ Frac {n!} {(N-r)!}.$

Factorielles se tournent également dans le calcul . Par exemple, le théorème de Taylor exprime une fonction f (x) comme une série de puissance en x, essentiellement parce que la ^n-ième dérivée de x ⁿ est n!.

Factorielles sont également largement utilisés dans la théorie des probabilités .

Factorielles sont souvent utilisés comme un exemple simple, avec les nombres de Fibonacci , lors de l'enseignement récursivité en informatique parce qu'ils satisfassent la relation récursive suivante (si n ≥ 1):

$n! = n \ fois (n-1)!. \,$

La théorie des nombres

Factorielles ont de nombreuses applications dans la théorie des nombres . En particulier, n! est nécessairement divisible par tous les nombres premiers jusqu'à et y compris n. En conséquence, les n> 5 est un nombre composé si et seulement si

$(N-1)! \ \ Equiv \ 0 \ ({\ rm mod} \ n).$

Un résultat plus fort est Théorème de Wilson, qui stipule que

$(P-1)! \ \ Equiv \ -1 \ ({\ rm mod} \ p)$

si et seulement si p est premier.

Adrien-Marie Legendre a constaté que la multiplicité du nombre premier p survenant dans la factorisation de n! peut être exprimée exactement comme

$\ Sum_ {i = 1} ^ {\ infty} \ left \ lfloor \ frac {n} {p ^ i} \ right \ rfloor,$

qui est finie depuis la fonction floor supprime tous $p ^ i> n.$

La seule factorielle qui est aussi un nombre premier est 2, mais il ya beaucoup de nombres premiers de la forme $\ Scriptstyle n! \, \ H \, 1$ , Appelée nombres premiers factoriels.

Tous factorielles supérieur à 0! et une! sont même, car ils sont tous les multiples de deux.

Taux de croissance

Terrain du logarithme naturel de la factorielle

Comme n croît, la factorielle n! devient plus grand que tous les polynômes et fonctions exponentielles en n.

Lorsque n est grand, n! peut être estimé assez précisément à l'aide De Stirling le rapprochement:

$n! \ approx \ sqrt {2 \ pi n} \ left (\ frac {n} {e} \ right) ^ n.$

Une version faible qui peut être facilement prouvé avec induction mathématique est

$\ Gauche ({n \ plus de 3} \ right) ^ n <n! <\ Gauche ({n \ over 2} \ right) ^ n \ \ mbox {if} \ n \ geq 6. \,$

Le logarithme de la factorielle peut être utilisé pour calculer le nombre de chiffres dans une base donnée la factorielle d'un nombre donné prendra. Il répond à l'identité:

$\ Log n! = \ Sum_ {k = 1} ^ n {\ log k}.$

Notez que cette fonction, si graphiquement, est d'environ linéaire, pour de petites valeurs; mais le facteur ${\ Log n!} \ Over n$ Et de ce fait la pente de la courbe, ne pousse arbitrairement grand, bien que très lentement. Le graphique de la $log (n!)$ pour $n$ entre 0 et 20 000 est montré dans la figure sur la droite.

Un simple approximation pour

basé sur Formule de Stirling est

$\ Log n! \ Approx n \ log n - n + \ frac {\ log n} {2} + \ frac {\ log (2 \ pi)} {2}.$

Une bien meilleure approximation pour

a été donnée par Srinivasa Ramanujan:

$\ Log n! \ Approx n \ log n - n + \ frac {\ log (n (1 + 4n (1 + 2n)))} {6} + \ frac {\ log (\ pi)} {2}.$

On peut voir à partir de ce que

est Ο (n log n). Ce résultat joue un rôle essentiel dans l'analyse de la complexité de calcul algorithmes de tri (voir comparaison tri).

Calcul

La valeur de $n!$ peut être calculé par la multiplication répétée si $n$ ne est pas trop grand. Le plus grand factorielle que la plupart des calculatrices peuvent gérer est de 69 !, parce que 70! > 10 ¹⁰⁰ (sauf pour la plupart des calculatrices HP qui peut traiter 253! Comme leur exposant peut être jusqu'à 499). La calculatrice vu dans Mac OS X, Microsoft Excel et Google Calculator peut gérer jusqu'à 170 factorielles !, qui est le plus grand factoriel moins de 2 ¹⁰²⁴ (10 ¹⁰⁰ en hexadécimal ) et correspond à un nombre entier de 1 024 bits. Les valeurs 12! et 20! sont les plus grands factorielles qui peuvent être stockés dans, respectivement, les 32 bits et 64 bits entiers couramment utilisés dans les ordinateurs personnels. Dans la pratique, la plupart des applications logicielles seront calculer ces petits factorielles par multiplication directe ou consultation de table. Des valeurs plus élevées sont souvent estimés en termes de estimations à virgule flottante de la Fonction Gamma, généralement avec La formule de Stirling.

Pour nombre théorique et combinatoires calculs, très grandes factorielles exactes sont souvent nécessaires. Factorielles Bignum peuvent être calculées par multiplication directe, mais multipliant la séquence 1 × 2 × ... × n de bas en haut (ou top-down) est inefficace; il est préférable de diviser la séquence de manière récursive de telle sorte que la taille de chaque sous-produit est minimisée.

Le asymptotiquement-meilleur rendement est obtenu par le calcul de n! de sa décomposition en facteurs premiers. Tel que documenté par Peter Borwein, factorisation permet $n!$ être calculé en temps O (n (log n log log n) ^2), à condition que le jeûne algorithme de multiplication est utilisé (par exemple, la Algorithme Schönhage-Strassen). Peter Luschny présente le code source et des repères pour plusieurs algorithmes factoriels efficaces, avec ou sans l'utilisation d'un Premier tamis.

La fonction de gamma

La fonction Gamma, comme ici tracée le long de la axe réel , se étend la factorielle d'une fonction lisse définie pour toutes les valeurs non entières.

La fonction factorielle peut également être défini pour des valeurs non entières, mais cela nécessite plus d'outils avancés de l'analyse mathématique . La fonction "remplit" les valeurs de la factorielle entre les entiers est appelé le Fonction Gamma, notée $\ Gamma (z)$ z des nombres entiers pour au moins une, définie par

$\ Gamma (z) = \ int_ {0} ^ {\ infty} t ^ {z-1} e ^ {- t} \, \ mathrm {d} t. \!$

D'Euler formule originale pour la fonction Gamma était

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

La fonction Gamma est liée à factorielles en ce qu'il satisfait une relation récursive similaires:

$n! = n (n-1)! \,$

$\ Gamma (n + 1) = n \ Gamma (n) \,$

Avec $\ Gamma (1) = 1$ cela donne l'équation pour tout entier naturel $n$ :

$\ Gamma (n + 1) = n! \, \!$

$\ Left (\ frac {1} {2} \ right)! = \ Frac {\ sqrt {\ pi}} {2}$

Sur la base de la valeur de la fonction Gamma pour moitié, l'exemple spécifique de factorielles demi-entier est résolu à

$\ Left (n + \ frac {1} {2} \ right)! = \ Sqrt {\ pi} \ times \ prod_ {k = 0} ^ {n 2k + 1 \ over 2}.$

Par exemple

$3,5! = \ Sqrt {\ pi} \ cdot {1 \ over 2} \ cdot {3 \ over2} \ cdot {5 \ over2} \ cdot {7 \ over2} \ environ 11,63.$

La fonction Gamma, est définie pour tous les nombres complexes $z$ sauf pour les entiers non positive $\ Scriptstyle (z \ = \, 0, \, -1, \, -2, \, \ dots)$ . Il est souvent considéré comme une généralisation de la fonction factorielle au domaine complexe, qui est justifiée pour les raisons suivantes:

Sens commun. La définition canonique de la fonction factorielle partage la même relation récursive avec la fonction Gamma.
Contexte. La fonction Gamma est généralement utilisé dans un contexte similaire à celui des factorielles (mais, bien sûr, où un domaine plus général est d'intérêt).
Unicité ( Théorème de Bohr-Mollerup). La fonction Gamma est la seule fonction qui satisfait à la relation récursive précitée pour le domaine des nombres complexes, est méromorphe, et est log-convexe sur l'axe réel positif. Ce est, ce est la seule fonction lisse, connectez-convexe qui pourrait être une généralisation de la fonction factorielle à tous les nombres complexes.

Euler a également développé une approximation de produits convergente pour les factorielles non entiers, qui peuvent être vus comme équivalente à la formule de la fonction Gamma ci-dessus:

$n! \ Approx \ 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] \ dots$

Il peut aussi se écrire comme suit:

$n! = \ Prod_ {k = 1} ^ \ infty {\ frac {{(k + 1)}} {{(k - 1)! (N + k)}}}.$

Le produit converge rapidement pour les petites valeurs de n.

Les applications de la fonction gamma

Les volumes d'un n - dimensions hypersphère est

$V_n = {\ pi ^ {n / 2} R ^ n \ over \ Gamma ((n / 2) 1)}.$

Produits-factorielle comme

Il existe plusieurs autres séquences entières semblables à la factorielle qui sont utilisés dans les mathématiques:

Primorial

Le primorial (séquence A002110 dans OEIS ) est similaire à la factorielle, mais avec le produit prise seulement sur les nombres premiers .

Double factorielle

$n !!$ désigne la double factorielle de $n$ et est définie de manière récursive

$n !! = \ begin {} 1 cas, et \ mbox {if} n = -1 \ mbox {ou} n = 0 \ mbox {ou} n = 1; \\ N (n-2) !! & \ Mbox {if} n \ ge2. \ Qquad \ qquad \ end {} cas$

Par exemple, 8 !! = 2 · 4 · 6 · 8 = 384 et neuf !! = 1 · 3 · 5 · 7 · 9 = 945. La séquence des factorielles doubles (séquence A006882 dans OEIS ) pour $n = 0, 1, 2, \ dots$ commence comme

1, 1, 2, 3, 8, 15, 48, 105, 384, 945, 3840, ...

La définition ci-dessus peut être utilisé pour définir doubles factorielles de nombres négatifs:

$(N-2) !! = \ frac {n !!} {n}$

La séquence des factorielles doubles pour $n = -1, -3, -5, -7, \ dots \,$ commence comme

$1, -1, 1/3, -1/15 \ dots$

tandis que la factorielle double d'négatives entiers pairs est infini.

Certaines identités impliquant factorielles sont doubles:

$n! = n !! (n-1) !! \,$

$(2n) !! = 2 ^ nn! \,$

$(2n + 1) !! = {(2n + 1)! \ Over (2n) !!} = {(2n + 1)! \ ^ Nn over2!}$

$(2n-1) !! = {(2n-1)! \ Over (2n-2) !!} = {(2n)! \ Over2 ^ nn!}$

$\ Gamma \ left (n + 1 {\ over2} \ right) = \ sqrt {\ pi} \, \, {(2n-1) !! \ over2 ^ n}$

$\ Gamma \ left ({n \ over2} 1 \ right) = \ sqrt {\ pi} \, \, {n !! \ over2 ^ {(n + 1) / 2}}$

où $\ Gamma$ est le Fonction Gamma. La dernière équation ci-dessus peut être utilisé pour définir la factorielle double en fonction d'un nombre complexe $n \ neq 0$ , Tout comme la fonction Gamma généralise la fonction factorielle. Il faut être prudent de ne pas interpréter $n !!$ comme la factorielle de $n!$ , Ce qui serait écrit $(N!)!$ et est un nombre beaucoup plus grand (pour $n> 2$ ).

Multifactorials

Une notation connexes courante consiste à utiliser plusieurs points d'exclamation pour désigner un multifactorielle, le produit des entiers dans les étapes de deux ( $n !!$ ), Trois ( $n !!!$ ), Ou plus. Le double factorielle est la variante la plus couramment utilisée, mais on peut de même définir le triple factorielle ( $n !!!$ ) Et ainsi de suite. En général, le k ^ième factoriel, dénotée par $n! ^ {(k)}$ , Est définie par récurrence, comme

$! n ^ {(k)} = \ \ left {\ begin {matrix} 1, \ qquad \ qquad \ && \ mbox {if} 0 \ le n <k; \\ N (nk)! ^ {(K)}, && \ mbox {if} n \ ge k. \ Quad \ \ \, \ end {matrix} \ right.$

Certains mathématiciens ont suggéré une alternative de notation $n! _2$ pour la double factorielle et de même $n! _k$ pour d'autres multifactorials, mais cela ne est pas venu dans l'usage général.

Factorielle Quadruple

Le factorielle quadruple, cependant, ne est pas un multifactoriel; Ce est un nombre beaucoup plus important donné par $\ Frac {(2n)!} {N!}$ .

Superfactorials

Neil Sloane et Simon Plouffe a défini le superfactorial en 1995 comme le produit de la première $n$ factorielles. Ainsi, le superfactorial de 4 est

$\ Mathrm {sf} (4) = 1! \ 2 fois! \ 3 fois! \ times 4! = 288 \,$

En général

$\ Mathrm {sf} (n) = \ prod_ {k = 1} ^ n k! = \ Prod_ {k = 1} ^ nk ^ {n-k + 1 = 1} ^ n \ cdot2 ^ {n-1} \ cdot3 ^ {n-2} \ cdots (n-1) ^ 2 \ n cdot ^ 1.$

La séquence de superfactorials commence (à partir $n = 0$ ) Comme

1, 1, 2, 12, 288, 34 560, 24883200, ... (séquence A000178 dans OEIS )

Cette idée a été étendu en 2000 par Henry Bottomley au superduperfactorial comme le produit de la première $n$ superfactorials, au départ (à partir de $n = 0$ ) Comme

1, 1, 2, 24, 6912, 238 878 720, 5944066965504000, ... (séquence A055462 dans OEIS )

et ainsi récursive à toute factorielle à plusieurs niveaux où le m ^e factorielle -niveau de $n$ est le produit de la première $n$ $(M - 1)$ factorielles -Level ^e, c.-à-

$\ Mathrm {mf} (n, m) = \ mathrm {mf} (n-1, m) \ mathrm {mf} (n, m-1) = \ prod_ {k = 1} ^ nk ^ {n-k + m-1 \ choisir nk}$

où $\ Mathrm {mf} (n, 0) = n$ pour $n> 0$ et $\ Mathrm {} mf (0, m) = 1$ .

Superfactorials (définition alternative)

Clifford Pickover dans ses 1995 livres Keys to Infinity défini le superfactorial de $n$ comme

$n \ mathrm {S} \ \ \ \ \ \;!!!!! {!}! \, \ equiv \ begin {matrix} \ underbrace {n ^ {{n} ^ {{\ cdot} ^ {{ \ cdot} ^ {{\ cdot} ^ {n!}}}}}} \\ n! \ End {matrix}, \,$

ou que,

$n \ mathrm {S} \ \ \ \ \ \;!!!!! \, = n ^ {(4)} {n!}! \,$

où le ⁽⁴⁾ représente la notation hyper4 opérateur, ou à l'aide Notation des flèches de Knuth,

$n \ mathrm {S} \ \ \ \ \ \;!!!!! {!} \, = (! n) \ uparrow \ uparrow (! n) \,$

Cette séquence d'superfactorials commence:

$1 \ mathrm {S} \ \ \ \ \ \;!!!!! {!} \, = 1 \,$

$2 \ mathrm {S} \ \ \ \ \ \;!!!!! {!} \, = 2 ^ 2 = 4 \,$

$3 \ mathrm {S} \ \ \ \ \ \;!!!!! {!} \, = 6 \ uparrow \ uparrow6 = {6} ^ 6 = 6 ^ {6 ^ {6 ^ {6 ^ {6 ^ 6}}}}$

Hyperfactorials

Parfois, le hyperfactorial de $n$ est considéré. Il est écrit que $H (n)$ et définie par

$H (n) = \ prod_ {k = 1} ^ ^ nk k = 1 ^ 1 \ cdot2 ^ 2 \ cdot3 ^ 3 \ cdots (n-1) ^ {n-1} \ cdot n ^ n.$

Pour n = 1, 2, 3, 4, ... les valeurs H (n) sont 1, 4, 108, 27648, ... (séquence A002109 dans OEIS ).

La fonction hyperfactorial est similaire à la factorielle, mais produit un plus grand nombre. Le taux de croissance de cette fonction, cependant, ne est pas beaucoup plus grand qu'un factorielle régulière. Cependant, H (14) = 1,85 × 10 ... ⁹⁹ est déjà presque égale à un googol, et H (15) = 8,09 × 10 ... ¹¹⁶ est à peu près de la même grandeur que la Nombre de Shannon, le nombre théorique de jeux d'échecs possibles.

La fonction hyperfactorial peut être généralisée à nombres complexes d'une manière similaire à celle de la fonction factorielle. La fonction résulte est appelé K-fonction.

Récupéré à partir de " http://en.wikipedia.org/w/index.php?title=Factorial&oldid=203072717 "

We provide Linux to the World