« Combinatoire/Factorielles » : différence entre les versions

== Les factorielles Définition ==

Dans ce cours nous aurons souvent besoin de calculer des produits d'entiers décroissants, comme par exemple 3✕2✕13×2×1 ou bien encore 14✕13✕12✕11✕10✕9✕8✕7✕6✕5✕4✕3✕2✕114×13×12×11×10×9×8×7×6×5×4×3×2×1.

Un tel produit est appelé une '''factorielle''', et est usuellement noté par un point d'exclamation. On a par exemple 5! = 5✕4✕3✕2✕15×4×3×2×1.

Soit <math>n</math> un nombre entier naturel. On va définirdéfinit sa factorielle par récurrence. en posant :

:<math>0n! =(n-1)!\times 1n</math> ; .

On vérifie que cette définition correspond bien à l’idée intuitive que l’onqu'on en avait donné au-dessus. Ainsi, par exemple,

| contenu = '''Je comprends ce que signifie la factorielle pour un nombre entier positif. En revanche, pourquoi avoir défini 0! = 1 ? Cette expression ne semble pas avoir de sens. Puis, quitte à donner une valeur à 0!, on devrait avoir 0! = 0×1 = 0, non ?'''

C'est vrai qu’a priori c’est une définition qui peut paraître arbitraire. Si l'on voit la factorielle comme le produit des « n premiers entiers positifs », alors 0!, le « produit des 0 premiers entiers positifs », n'a simplement aucun sens.

* On aurait pu décider de ne pas donner de sens à 0! tout comme on ne donne pas de sens à <math>\scriptstyle{\frac{1}{0}}frac10</math>. C'est une position qui aurait été défendable. Seulement, cela aurait empêché la formulation générale de certaines formules qui seront présentées plus loin dans le cours.

C'est un peu comme quand on a défini ''a''a⁰ = 1'''. Mettre n’importe quel nombre à la puissance 0 n'a a priori pas de sens. Mais on a la formule bien connue :

Etet l'on aimerait qu'elle soit vraie aussi si x ou y est nul, ce qui force à définir ''a''a⁰ = 1'''. Il s'agit du même type de choix conventionnel que dans le cas de la factorielle de 0.

=== Calcul avec les factorielles ===

Le tableau ci-contre présente les factorielles pour les 21 premiers nombres entiers. Comme on le voit, les factorielles deviennent rapidement très grandes. Même pour des nombres entiers àrelativement priori faiblespetits, les factorielles deviennent incommensurables. '''60!''', parPar exemple, 60! est proche de '''10⁸²''', ce qui est plus que le nombre estimé d'atomes dans l'univers. À partir d'un certain nombre, les factorielles deviennent si grandes que les calculatrices que l’on utilise habituellement ne saventpeuvent plus les calculer.

Par exemple, <math>\scriptstyle\frac{200!}{199!}</math> n’est pas calculable avec certaines calculatrices, bien que ce ne soit pas un grand nombre. En effet la calculatrice va échouer à calculer le numérateur et le dénominateur (qui sont tous les deux gigantesques) et ne va donc pas pouvoir effectuer la division.

Un calcul simple peut cependant nous donner la réponse :

<math>\frac{200!}{199!} = \frac{199!\times200}{199!} = 200</math>.

Par exemple :

<math>\frac{50!}{48!} = \frac{48!\times49\times50}{48!} = 49\times50 = 2450</math>.

On peut écrire de manière plus générale, avec '''n''' et '''k''' deux entiers positifs tel que '''k''' est le plus petit des deux :

&= (n-k+1)\times(n-k+2)\times\cdots\times(n-1)\times n.