Factorielle

Enmathématiques,lafactorielled'unentier naturelnest leproduitdes nombres entiers strictement positifs inférieurs ou égaux àn.

Cette opération est notée avec unpoint d'exclamation,n!, ce qui se lit soit « factorielle den», soit « factoriellen», soit«nfactorielle ». Cette notation a été introduite en1808parChristian Kramp.

Par exemple, la factorielle 10 exprime le nombre de combinaisons possibles de placement des 10 convives autour d'une table (on dit la permutation des convives). Le premier convive s'installe sur l'une des 10 places à sa disposition. Chacun de ses 10 placements ouvre 9 nouvelles possibilités pour le deuxième convive, celles-ci 8 pour le troisième, et ainsi de suite.

La factorielle joue un rôle important enalgèbre combinatoireparce qu'il y an!façons différentes depermuternobjets. Elle apparaît dans de nombreuses formules en mathématiques, comme laformule du binômeet laformule de Taylor.

Définition

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
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
…	…
25	1,551 121 004 333 098 598 4 × 1025
Notes: Voir suiteA000142de l'OEISpour davantage d'exemples. La partie décimale de la valeur de 25!, indiquée en notation scientifique, est exacte.

Soitnun entier naturel. Sa factorielle est formellement définie par:

$n!=\prod _{1\leqslant i\leqslant n}i=1\times 2\times 3\times \ldots \times (n-1)\times n.$

Le tableau de droite donne les premières factorielles; par exemple, on a:

1! = 1

2! = 1 × 2 = 2

3! = 1 × 2 × 3 = 6

4! = 1 × 2 × 3 × 4 = 24

10! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 = 3 628 800

Valeur de 0!

Cette définition donne aussi:

0! = 1

puisque par convention, leproduit videest égal à l'élément neutrede la multiplication. Cette convention est pratique ici car elle permet à des formules de dénombrement obtenues enanalyse combinatoired'être encore valides pour des tailles nulles. En particulier, le nombre d'arrangementsou depermutationsde l'ensemble videest égal à 1.

Il existe aussi unedéfinition par récurrence(équivalente) de la factorielle:

1. 0! = 1.
2. Pour tout entier$n>0$,$n!=(n-1)!\times n$.

Enfin, lafonction Gamma,qui prolonge analytiquement la factorielle, donne un résultat cohérent:

$\Gamma (n)=(n-1)!\qquad n\in \mathbb {N} _{0},$

$\Gamma (1)=1=0!$

Propriétés

• Les inverses des factorielles sont lescoefficients du développementensérie entièrede lafonction exponentielle:$\mathrm {e} ^{x}=\sum _{n=0}^{+\infty }{\frac {x^{n}}{n!}}$,le casx= 1 donnant la valeur de laconstantee:$\sum _{n=0}^{+\infty }{\frac {1}{n!}}=\mathrm {e} =2,718\,281\,828\,459\ldots$.
• Lesn– 1 entiers consécutifsn!+ 2,n!+ 3,…,n!+nsontcomposés.Donc il y a dans la suite des entiers des« trous » aussi grands que l'on veut où il n'y a aucun nombre premier.

Généralisation

La fonction gamma, tracée ici le long de l'axe des réels, prolonge la factorielle sur les valeurs qui ne sont pas entières.

La fonction factorielle admet pourprolongement,à l'ensemble desnombres complexesautres que les entiers strictement négatifs, l'application$z\mapsto \Gamma (z+1)$où$\Gamma$désigne lafonction gammad'Euler.En effet, pour tout entier natureln,on a:

$n!=\int _{0}^{\infty }t^{n}{\rm {e}}^{-t}{\rm {d}}t=\Gamma (n+1).$

Par ailleurs, la fonction$z\mapsto \Gamma (z+1)$vérifie la même relation de récurrence que la factorielle:

$\forall z\in \mathbb {C} \setminus (-\mathbb {N} ),\quad \Gamma (z+1)=z\Gamma (z).$

Cette vision de la fonction gamma (translatée) comme prolongement privilégié de la factorielle est justifiée par les raisons suivantes:

• les deux fonctions partagent une même définition récurrente;
• la fonction gamma est généralement utilisée dans un contexte similaire (même si plus général) à la factorielle;
• la fonction gamma est la seule fonction qui satisfasse cette définition de récurrence sur les nombres complexes, qui estholomorpheet dont lelogarithmede la restriction aux réels positifs estconvexe(théorème de Bohr-Mollerup).

Il existe cependant d'autres prolongements ayant de « bonnes propriétés », comme lafonction gamma d'Hadamard,qui estentière.

Approximation

Laformule de Stirlingdonne unéquivalentden!quandnest grand:

$\lim _{n\to +\infty }{\frac {n!}{{\sqrt {2\pi n}}\left({\frac {n}{\mathrm {e} }}\right)^{n}}}=1$

d'où

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

où lenombreedésigne la base de l'exponentielle.

On en déduit une approximation dulogarithmede$n!$:

$\ln \left(n!\right)\simeq (n+{\tfrac {1}{2}})\ln \left(n\right)-n+\ln({\sqrt {2\pi }})$.

Exemples d'applications

Encombinatoire,il existen!façons différentes d'arrangernobjets distincts (c’est-à-diren!permutations). Et le nombre de façons de choisirkéléments parmi un ensemble denest donné par lecoefficient binomial:

${n \choose k}={n! \over k!(n-k)!}.$

Les factorielles apparaissent également enanalyse.Par exemple, lethéorème de Taylor,qui exprime la valeur enxd'une fonction ƒ sous forme desérie entière,fait intervenir la factoriellen!pour le terme correspondant à la n^edérivéede ƒ enx.

Levolume d'une hypersphèreen dimensionnpaire peut être exprimé par:

$\mathrm {V} _{n}={\frac {\pi ^{\frac {n}{2}}\mathrm {R} ^{n}}{\left({\frac {n}{2}}\right)!}}.$

Les factorielles sont utilisées de façon intensive enthéorie des probabilités.

Les factorielles sont souvent utilisées comme exemple — avec lasuite de Fibonacci— pour l'apprentissage de larécursivitéeninformatiquedu fait de leur définition récurrente simple.

Théorie des nombres

Les factorielles ont de nombreuses applications enthéorie des nombres.

Par exemple, lethéorème de Wilsonmontre qu'un entiern> 1 estpremiersi et seulement si$(n-1)!\equiv -1{\pmod {n}}$.

En particulier, sinest premier alors il ne divise pas (n– 1)!, ce qui peut d'ailleurs se déduire directement dulemme d'Euclide;laréciproqueest presque vraie: sinest unnombre composédifférent de 4, alors (n– 1)! ≡ 0 (modn).

Une preuve de ce dernier énoncéutilise qu'un produitPdekentiers consécutifs est toujours divisible park(puisquel'un deskfacteurs l'est). En fait,Pest même divisible park!on peut le démontrer en exprimantP/k!comme uncoefficient binomial,ou bienen comparant, pour tout nombre premierp,lamultiplicité depdans lesdécompositions en facteurs premiersdePet dek!, grâce à laformule de Legendre.

La seule factorielle qui soit également un nombre premier est 2, mais il existe des nombres premiers de la formen!± 1, appelésnombres premiers factoriels.

Variantes

De nombreux auteurs ont défini des fonctions analogues, croissant plus rapidement encore, ainsi que des produits restreints à certains entiers seulement. On rencontre ainsi dans la littératureles fonctionsprimorielles,multifactorielles, superfactorielles, hyperfactorielles, etc. Mais il ne semble pas que, contrairement à la factorielle, omniprésente dans la plupart des branches des mathématiques, ces autres fonctions aient eu beaucoup d'applications autres querécréatives,sauf les primorielles; quant à leur utilisation pour désigner de trèsgrands nombres,lesnotations de Knuthetcelles de Conways'avèrent à la fois plus maniables et beaucoup plus efficaces.

Algorithme

Le calcul de la factorielle peut se traduire par l'algorithme récursifsuivant, écrit enpseudo-code:

Fonctionfactorielle (n: entier): entier
Début
Sin > 0
Retournern * factorielle(n - 1)
Sinon
Retourner1
Fin si
Fin

Nombre de zéros finaux de n!

On admet la notation suivante:$\forall x\in \mathbb {R},\lfloor x\rfloor$est lapartie entièrede$x$définie par${\begin{cases}\lfloor x\rfloor \in \mathbb {Z} \\\lfloor x\rfloor \leqslant x<\lfloor x\rfloor +1\end{cases}}$.

Cette propriété ne présente pas de grand intérêt en apparence mais permet d'obtenir le nombre de zéros finaux de n!. Mais qu'est ce qu'un zéro final? Prenons comme exemple${\textstyle 10!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10=3628800}$,il y a deux zéros finaux. Nommons$\mu (n)$une telle fonction.$$\mu (n)=\sum _{k=1}^{\lfloor \log _{5}(n)\rfloor }\left\lfloor {\frac {n}{5^{k}}}\right\rfloor$$

Démonstration

On a$10!=10^{2}\times 36288.$

On cherche donc le nombre de facteurs 10 dans 10!, il y en a deux. Pour trouver le deuxième, on décompose$10!$en produit de facteurs premiers, on obtient:$10!=2\times 3\times (2\times 2)\times 5\times (2\times 3)\times 7\times (2\times 2\times 2)\times (3\times 3)\times (2\times 5)$Pour obtenir$10^{2}$;on peut réarranger ainsi: ${\textstyle 10!=1\times 3\times 4\times 6\times 7\times 8\times 9\times (5\times 2\times 5\times 2)}$

On remarque que$10$se décompose en$2\times 5$,donc chercher des facteurs$10$est équivalent à chercher des facteurs$5$multiplié par$2$.En généralisant, il y a$\left\lfloor {\frac {n}{2}}\right\rfloor$multiples de$2$et$\lfloor {\frac {n}{5}}\rfloor$multiples de$5$inférieurs ou égales à$n$.De plus dans un multiple de$2$,il y a au moins un facteur$2$,de même pour un multiple de$5$.Comme$\lfloor {\frac {n}{5}}\rfloor \leq \lfloor {\frac {n}{2}}\rfloor$,on pourra toujours combiner un facteur$2$avec un facteur$5$et donc obtenir un facteur$10$.Ainsi le nombre de zéros finaux de$n!$sera le nombre de facteurs$5$de$n!$.Pour trouver le nombre de facteurs$5$,on a le nombre de multiples de$5$mais ce n'est pas suffisant, dans$25$il y a deux facteurs$5$($5^{2}$), comme$50$et$75$,dans$125$il y a trois facteurs$5$($5^{3}$). Plus simplement on doit compter$k$fois chaque multiple$5^{k}$.Donc le nombre de facteurs$5$de$n!$est la somme du nombres de multiples de chaque puissance de$5$inférieures ou égales à$n$.C'est-à-dire: $$\sum _{k=1}^{\alpha }\left\lfloor {\frac {n}{5^{k}}}\right\rfloor$$Avec$5^{\alpha }$la plus grande puissance de$5$inférieure ou égale à$n$.On a donc:

${\textstyle 5^{\alpha }\leq n\Leftrightarrow \ln(5^{\alpha })\leq \ln(n)\Leftrightarrow \alpha \ln(5)\leq \ln(n)\Leftrightarrow \alpha \leq \log _{5}(n).}$

On veut$\alpha$l'entier inférieur le plus proche de$\log _{5}(n)$,d'où$\alpha =\lfloor \log _{5}(n)\rfloor$.

Et ainsi le nombre de zéros finaux de$n!$vaut:$\sum _{k=1}^{\lfloor \log _{5}(n)\rfloor }\left\lfloor {\frac {n}{5^{k}}}\right\rfloor$

Ce résultat est un cas particulier de laformule de Legendre.

Notes et références

(en)Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé«Factorial»(voir la liste des auteurs).

Voir aussi

Articles connexes

• Factorielle exponentielle
• Formule de Stirling
• Fonction digamma
• Nombre premier factoriel
• Primorielle
• Série alternée des factorielles
• Analogues de la factorielle

Liens externes

• factorielle n!sur le site factorielle.free.fr
• (en)Peter Luschny, «Fast Factorial Functions»