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

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.

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é.

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{array}{cc}\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{array}$