Factorielle

Factorielle

Présentation

Type	Fonction à valeur entière, suite d'entiers

modifier - modifier le code - modifier Wikidata

En mathématiques, la factorielle d'un entier naturel ${\displaystyle n}$ est le produit des nombres entiers strictement positifs inférieurs ou égaux à ${\displaystyle n}$.

Cette opération est notée avec un point d'exclamation, ${\displaystyle n!}$, ce qui se lit soit « factorielle de ${\displaystyle n}$ », soit « factorielle ${\displaystyle n}$ », soit « ${\displaystyle n}$ factorielle ». Cette notation a été introduite en 1808 par Christian Kramp.

Par exemple, la factorielle de 10 exprime le nombre de combinaisons possibles de placement des 10 convives autour d'une table (on parle de 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 en algèbre combinatoire parce qu'il y a ${\displaystyle n!}$ façons différentes de permuter ${\displaystyle n}$ objets. Elle apparaît dans de nombreuses formules en mathématiques, comme la formule du binôme et la formule de Taylor.

Histoire

Au XIII^e siècle, le mathématicien de Marrakech Ibn Mun’im publie un livre intitulé La science du calcul (Fiqh Al-Hisab) dans lequel il traite pour la première fois de factorielles. Il démontre notamment comment calculer le nombre des permutations d'un ensemble à ${\displaystyle n}$ éléments.

Définition

Soit ${\displaystyle n}$ un entier naturel. Sa factorielle est formellement définie par :

${\displaystyle 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

Propriétés

• Les inverses des factorielles sont les coefficients du développement en série entière de la fonction exponentielle :${\displaystyle \mathrm {e} ^{x}=\sum _{n=0}^{+\infty }{\frac {x^{n}}{n!}}}$,le cas x = 1 donnant la valeur de la constante e :${\displaystyle \sum _{n=0}^{+\infty }{\frac {1}{n!}}=\mathrm {e} =2,718\,281\,828\,459\ldots }$.
• Les ${\displaystyle n-1}$ entiers consécutifs ${\displaystyle n!+2,n!+3,\dots ,n!+n}$ sont composé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 factorielle admet pour prolongement, à l'ensemble des nombres complexes autres que les entiers strictement négatifs, l'application ${\displaystyle z\mapsto \Gamma (z+1)}$ où ${\displaystyle \Gamma }$ désigne la fonction gamma d'Euler. En effet, pour tout entier naturel n, on a :

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

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

${\displaystyle \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 est holomorphe et dont le logarithme de la restriction aux réels positifs est convexe (théorème de Bohr-Mollerup).

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

Approximation

La formule de Stirling donne un équivalent de ${\displaystyle n!}$ quand ${\displaystyle n}$ tend vers l'infini:

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

d'où

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

où le nombre e désigne la base de l'exponentielle.

On en déduit une approximation du logarithme de ${\displaystyle n!}$ :

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

Exemples d'applications

En combinatoire, il existe ${\displaystyle n!}$ façons différentes d'arranger ${\displaystyle n}$ objets distincts (c’est-à-dire ${\displaystyle n!}$ permutations). Et le nombre de façons de choisir ${\displaystyle k}$ éléments parmi un ensemble de ${\displaystyle n}$ est donné par le coefficient binomial :

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

(Puisque le produit de k nombres naturels consécutifs est de la forme ${\displaystyle {n! \over (n-k)!}}$ pour un certain nombre naturel n et que ${\displaystyle {n \choose k}}$ est un nombre naturel, cette formule montre que le produit de k nombres naturels consécutifs est toujours divisible par ${\displaystyle k!}$.)

Les factorielles apparaissent également en analyse. Par exemple, le théorème de Taylor, qui exprime la valeur en ${\displaystyle x}$ d'une fonction ${\displaystyle f}$ sous forme de série entière, fait intervenir la factorielle ${\displaystyle n!}$ pour le terme correspondant à la ${\displaystyle n}$^e dérivée de ${\displaystyle f}$ en ${\displaystyle x}$.

Le volume d'une hypersphère en dimension n paire peut être exprimé par :

${\displaystyle \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 en théorie des probabilités.

Les factorielles sont souvent utilisées comme exemple — avec la suite de Fibonacci — pour l'apprentissage de la récursivité en informatique du fait de leur définition récurrente simple.

Théorie des nombres

Les factorielles ont de nombreuses applications en théorie des nombres.

Par exemple, le théorème de Wilson montre qu'un entier ${\displaystyle n>1}$ est premier si et seulement si ${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$.

En particulier, si ${\displaystyle n}$ est premier alors il ne divise pas ${\displaystyle (n-1)!}$, ce qui peut d'ailleurs se déduire directement du lemme d'Euclide ; la réciproque est presque vraie : si ${\displaystyle n}$ est un nombre composé différent de 4, alors ${\displaystyle (n-1)!\equiv 0\mod n}$.

Une preuve de ce dernier énoncé utilise qu'un produit ${\displaystyle P}$ de ${\displaystyle k}$ entiers consécutifs est toujours divisible par ${\displaystyle k}$ (puisque l'un des k facteurs l'est). En fait, ${\displaystyle P}$ est même divisible par ${\displaystyle k!}$ ; on peut le démontrer en exprimant ${\displaystyle P/k!}$ sous forme de coefficient binomial, ou bien en comparant, pour tout nombre premier ${\displaystyle p}$, la multiplicité de ${\displaystyle p}$ dans les décompositions en facteurs premiers de ${\displaystyle P}$ et de ${\displaystyle k!}$, grâce à la formule de Legendre.

La seule factorielle qui soit également un nombre premier est 2, mais il existe des nombres premiers de la forme ${\displaystyle n!\pm 1}$, appelés nombres 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érature les fonctions primorielles, 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 que récréatives, sauf les primorielles ; quant à leur utilisation pour désigner de très grands nombres, les notations de Knuth et celles de Conway s'avèrent à la fois plus maniables et beaucoup plus efficaces.

Algorithme

Le calcul de la factorielle peut se traduire par l'algorithme récursif suivant, écrit en pseudo-code :

Fonction factorielle (n: entier): entier
Début
   Si n > 0
     Retourner n * factorielle(n - 1)
   Sinon
     Retourner 1
   Fin si
Fin

Nombre de zéros finaux de n!

On admet la notation suivante : ${\displaystyle \forall x\in \mathbb {R} ,\lfloor x\rfloor }$ est la partie entière de ${\displaystyle x}$ définie par ${\displaystyle {\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 ${\displaystyle \mu (n)}$ une telle fonction.$${\displaystyle \mu (n)=\sum _{k=1}^{\lfloor \log _{5}(n)\rfloor }\left\lfloor {\frac {n}{5^{k}}}\right\rfloor }$$

Ce résultat est un cas particulier de la formule de Legendre.

Notes et références

Voir aussi

Liens externes

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

v · m Grands nombres entiers
Séquences de 1 000 à 9 999	Nombres 1 000 à 1 999 Nombres 2 000 à 2 999 Nombres 3 000 à 3 999 Nombres 4 000 à 4 999 Nombres 5 000 à 5 999 Nombres 6 000 à 6 999 Nombres 7 000 à 7 999 Nombres 8 000 à 8 999 Nombres 9 000 à 9 999
Séquences de 10 000 à 9 999 999 999	Nombres 10 000 à 99 999 Nombres 100 000 à 999 999 Nombres 1 000 000 à 9 999 999 Nombres 10 000 000 à 99 999 999 Nombres 100 000 000 à 999 999 999 Nombres 1 000 000 000 à 9 999 999 999
Grands nombres remarquables	142 857 (nombre cyclique et nombre de Kaprekar) 144 000 (1 baktun du compte long maya) 1 048 576 (20e puissance de deux) 4 294 967 296 (32e puissance de deux) 4 294 967 297 (nombre de Fermat) 107 928 278 317 (cf. triplet pythagoricien et théorème de Green-Tao)
Notions générales sur les grands nombres	Hiérarchie de croissance rapide Infini Nom des grands nombres Notation des flèches chaînées de Conway Notation des puissances itérées de Knuth Ordre de grandeur Paradoxe des nombres intéressants Numération indienne
Liste de grands nombres

v · m Notion de nombre
Ensembles usuels	Entier naturel (${\displaystyle \scriptstyle \mathbb {N} }$) Entier relatif (${\displaystyle \scriptstyle \mathbb {Z} }$) Nombre décimal (${\displaystyle \scriptstyle \mathbb {D} }$) Nombre rationnel (${\displaystyle \scriptstyle \mathbb {Q} }$) Nombre réel (${\displaystyle \scriptstyle \mathbb {R} }$) Nombre complexe (${\displaystyle \scriptstyle \mathbb {C} }$)
Extensions	Quaternion (${\displaystyle \scriptstyle \mathbb {H} }$) Octonion (${\displaystyle \scriptstyle \mathbb {O} }$) Sédénion (${\displaystyle \scriptstyle \mathbb {S} }$) Nombre complexe déployé Tessarine Nombre bicomplexe (${\displaystyle \scriptstyle \mathbb {C} _{2}}$) Nombre multicomplexe (${\displaystyle \scriptstyle \mathbb {C} _{n}}$ ${\displaystyle \scriptstyle {\mathcal {M}}\mathbb {C} _{n}}$) Biquaternion Coquaternion Quaternion hyperbolique Octonion déployé Nombre hypercomplexe Nombre p-adique (${\displaystyle \scriptstyle \mathbb {Q} _{p}}$) Nombre hyperréel Nombre superréel Entier surnaturel Entier profini Nombre dual Droite réelle achevée Nombre cardinal Nombre ordinal Nombre surréel Nombre pseudo-réel
Propriétés particulières	Parité Nombre premier Nombre composé Nombre figuré Nombre parfait Nombre positif Nombre négatif Fraction dyadique Nombre irrationnel Nombre algébrique Nombre transcendant Nombre imaginaire pur Nombre de Liouville Période Nombre normal Nombre univers Nombre constructible Nombre réel calculable Nombre transfini Infiniment petit
Exemples	Pi (π) Racine carrée de deux (${\displaystyle \scriptstyle {\sqrt {2}}}$) Nombre d’or (φ) Zéro (0) Unité imaginaire (i) Constante d’Euler (e) Aleph-zéro (ℵ0) Table de constantes mathématiques
Articles liés	Chiffre Numération Fraction Opération Calcul Algèbre Arithmétique Suite d'entiers Infini (∞) Chiffre significatif

• Portail des mathématiques