Combinatoire/Factorielles

Début de la boite de navigation du chapitre

Avant de rentrer dans le vif du sujet, nous avons besoin de présenter une notation mathématique que nous devrons utiliser à plusieurs reprises : la factorielle. Elle nous permettra d'écrire succinctement un produit particulier de nombres entiers.

fin de la boite de navigation du chapitre

Définition

Dans ce cours nous aurons souvent besoin de calculer des produits d'entiers décroissants, comme 3×2×1 ou bien encore 14×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×1.

Définition de la factorielle

Soit $n$ un nombre entier naturel. On définit sa factorielle par récurrence en posant :

$0!=1$ ;

si $n>0$,

$n!=(n-1)!\times n$.

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

$5!=4!\times 5$ (par définition de 5!)

$5!=(3!\times 4)\times 5$ (par définition de 4!)

$5!=(2!\times 3)\times 4\times 5$ (par définition de 3!)

$5!=(1!\times 2)\times 3\times 4\times 5$ (par définition de 2!)

$5!=(0!\times 1)\times 2\times 3\times 4\times 5$ (par définition de 1!)

$5!=1\times 1\times 2\times 3\times 4\times 5=5\times 4\times 3\times 2\times 1$ (par définition de 0!)

On obtient donc la bonne égalité.

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. En fait, la valeur donnée à la factorielle de 0 est purement conventionnelle. Cette convention a été choisie pour deux raisons : On aurait pu décider de ne pas donner de sens à 0! tout comme on ne donne pas de sens à ${\frac {1}{0}}$. 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. Si l'on avait choisi 0! = 0 ou bien une toute autre valeur, la définition au-dessus n'aurait pas pu marcher. On aurait eu par exemple 1! = 0!×1 = 0. Si l'on veut donner une valeur à 0!, la seule possible est 1. C'est un peu comme quand on a défini a0 = 1. Mettre n’importe quel nombre à la puissance 0 n'a a priori pas de sens. Mais on a la formule bien connue : $a^{x+y}=a^{x}\times a^{y}$ et l'on aimerait qu'elle soit vraie aussi si x ou y est nul, ce qui force à définir a0 = 1. Il s'agit du même type de choix conventionnel que dans le cas de la factorielle de 0. En résumé : par convention, le produit vide est égal à 1, et cette convention est compatible avec les règles de calcul usuelles.

Calcul avec les factorielles

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

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 petits, les factorielles deviennent incommensurables. Par 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 peuvent plus les calculer.

Dans certains cas, il est possible de simplifier les expressions mathématiques utilisant les factorielles, de manière à pouvoir les calculer plus facilement à la main ou même à la calculette.

Par exemple, ${\frac {200!}{199!}}$ 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 :

${\frac {200!}{199!}}={\frac {199!\times 200}{199!}}=200$.

On a simplement utilisé la définition de la factorielle et simplifié la fraction. On peut faire cela avec n’importe quelle fraction de factorielle. Par exemple :

${\frac {50!}{48!}}={\frac {48!\times 49\times 50}{48!}}=49\times 50=2450$.

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 :

${\begin{aligned}{\frac {n!}{(n-k)!}}&={\frac {(n-k)!\times (n-k+1)\times (n-k+2)\times \cdots \times (n-1)\times n}{(n-k)!}}\\&=(n-k+1)\times (n-k+2)\times \cdots \times (n-1)\times n.\end{aligned}}$