Combinatoire/Factorielles
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.
Définition
[modifier | modifier le wikicode]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.
Soit un nombre entier naturel. On définit sa factorielle par récurrence en posant :
- ;
si ,
- .
On vérifie que cette définition correspond bien à l’idée intuitive qu'on en avait donné au-dessus. Ainsi, par exemple,
(par définition de 5!)
(par définition de 4!)
(par définition de 3!)
(par définition de 2!)
(par définition de 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 :
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 :
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
[modifier | modifier le wikicode]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 1082, 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, 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 :
.
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 :
.
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 :