Factorielle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

Cette opération est notée avec un point d'exclamation :

n !

ce qui se lit soit « factorielle de n », soit « factorielle n » soit « n factorielle ». Cette notation a été introduite en 1808 par Christian Kramp.

La factorielle joue un rôle important en algèbre combinatoire parce qu'il y a n! façons différentes de permuter n objets. Elle apparaît dans de nombreuses formules en mathématiques, comme la formule du binôme et la formule de Taylor.

Historique[modifier | modifier le code]


Définition[modifier | modifier le code]

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 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
25 1,551 121 004 333 098 598 4·1025
Notes :
  • Voir suite A000142 de l'OEIS pour davantage d'exemples.
  • La partie décimale de la valeur de 25!, indiquée en notation scientifique, est exacte.

Soit n un 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

Cette définition donne aussi

0! = 1

puisque par convention, le produit vide est égal à l'élément neutre de la multiplication. Cette convention est pratique ici car elle permet à des formules de dénombrement obtenues en analyse combinatoire d'être encore valides pour des tailles nulles. En particulier, le nombre d'arrangements ou de permutations de l'ensemble vide est égal à 1.

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

  1. 0! = 1.
  2. Pour tout entier n > 0, n! = (n – 1)! × n.

Propriétés[modifier | modifier le code]

Les inverses des factorielles sont les coefficients du développement en série entière de la fonction exponentielle :

\mathrm e^x=\sum_{n=0}^{+\infty}\frac{x^n}{n!},

le cas x = 1 donnant la valeur de la constante e :

\sum_{n=0}^{+\infty}\frac1{n!}=\mathrm e = 2,718\,281\,8\ldots

La formule de Stirling donne un équivalent de n! quand n est grand :

\lim_{n\to+\infty} \frac{n!}{\sqrt{2\pi n} (n/\mathrm e)^n}=1 d'où n\,! \sim \sqrt{2\pi n}\, {\left(\frac n\mathrm e\right)}^n.

Généralisation[modifier | modifier le code]

Article détaillé : Fonction gamma.
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 pour prolongement, à l'ensemble des nombres complexes autres que les entiers strictement négatifs, l'application z ↦ Γ(z + 1) où Γ désigne la fonction gamma d'Euler. En effet, pour tout entier naturel n, on a :

n!=\int_0^{\infty}t^n{\rm e}^{-t}{\rm d}t=\Gamma(n+1).

Par ailleurs, la fonction z ↦ Γ(z + 1) vérifie la même relation de récurrence que la factorielle :

\forall z\in\C\setminus(-\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).

Exemples d'applications[modifier | modifier le code]

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

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

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

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

\mathrm{V}_n = {\pi^{n/2} \mathrm{R}^n\over (n/2)!}.

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[modifier | modifier le code]

Les factorielles ont de nombreuses applications en théorie des nombres. Les nombres factoriels sont des nombres hautement composés. En particulier, n! est divisible par tous les nombres premiers qui lui sont égaux ou inférieurs. Par conséquent, tout nombre n > 4 est un nombre composé si et seulement si :

(n-1)!\ \equiv\ 0 \ ({\rm mod}\ n).

Un résultat plus fort est le théorème de Wilson. n est premier si et seulement si :

(n-1)!\ \equiv\ -1 \ ({\rm mod}\ n)

Adrien-Marie Legendre a montré que la multiplicité du nombre premier p dans la décomposition en produit de facteurs premiers de n! peut être exprimé par :

\sum_{i=1}^{\infty} \lfloor n/p^i \rfloor,

(qui est définie, car la fonction partie entière élimine tous les p^i > n).

La seule factorielle qui soit également un nombre premier est 2, mais il existe des nombres premiers de la forme n! \pm 1, appelés nombres premiers factoriels.

Variantes[modifier | modifier le code]

Article détaillé : Analogues de la factorielle.

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[1] 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[modifier | modifier le code]

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 > 1
     Retourner n * factorielle(n - 1)
   Sinon
     Retourner 1
Fin si
Fin 

Lambda-calcul[modifier | modifier le code]

En lambda-calcul, la factorielle s'écrit comme suit :

  fact = λn.second (n (λc.pair (succ (second c)) (times (premier c) (second c))) (pair 1 1))

si on n'utilise pas le combinateur de point fixe Y, sinon :

  factrec = Y (λfn.(ifthenelse (iszero n) 1 (times n (f (pred n)))))

Notes et références[modifier | modifier le code]

  1. En particulier dans l'OEIS

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]