11
Reprenons l’exemple de la course de chevaux, mais posons nous la question suivante « Quels sont les ordres d’arrivée possibles pour les 18 chevaux ? ». Dans cette question, il ne s’agit pas de chercher les podiums, mais bien de connaitre les places possibles des 18 chevaux sur la ligne d’arrivée.
Le problème peut se résoudre à l’aide d’un arbre. Pour la première place, il existe 18 possibilités. Pour la deuxième place, il n’existe plus que 17 possibilités. Pour la troisième place, il n’en existe plus que 16 et ainsi de suite jusqu’à la dernière place pour laquelle il n’y a plus qu’une seule possibilité. Cet arbre serait extrêmement lourd à dessiner et nous pouvons aller directement au calcul vu au chapitre précédent : [latex]18 \times 17 \times 16 \times \ldots \times 1[/latex]
Ce type de multiplication peut s’écrire, de façon contractée, sous la forme d’une factorielle : [latex]18![/latex]
De façon plus générale et plus mathématique, ceci revient à chercher le nombre de permutations sans répétition des [latex]n[/latex] éléments de [latex]X[/latex] ou formulé différemment, le cardinal de l’ensemble des [latex]n-uplets[/latex], avec [latex]X[/latex] un ensemble constitué de [latex]n[/latex] éléments et dont les éléments des [latex]n-uplets[/latex] sont distincts.
[latex]X = \left\{x_{1}, x_{2}, \ldots, x_{n}\right\}[/latex]
[latex]Card(X) = n[/latex]
[latex]Card(\left\{(a_{1}, a_{2}, \ldots, a_{n}) \mid a_{i} \in X, a_{i} ~distinct \right\})[/latex]
[latex]= n \times (n - 1) \times (n - 2) \times \ldots \times 2 \times 1 = n! = P_n[/latex]
La permutation de [latex]n[/latex] éléments sans répétition constitue un cas particulier d’arrangement sans répétition de [latex]p[/latex] éléments pris parmi [latex]n[/latex] lorsque [latex]p = n[/latex].
[latex]A_n^n = \frac {n!} {(n - n)!} = \frac {n!} {0!} = \frac {n!} {1} = n![/latex]
Appliqué à la question précédente, le nombre de permutations des 18 chevaux sur la ligne d’arrivée est donc [latex]18! = 640.237.370.5728.000[/latex]
Dans le cas des chevaux, on comprend aisément que chaque animal est différent, mais si nous cherchons le nombre de permutations à partir d’un mot qui est constitué de certaines lettres semblables, il faut retirer les permutations de lettres identiques.
Prenons le cas du mot AUTORADIO. Le nombre de mots, avec ou sans signification, qu’il est possible d’écrire en permutant ces 9 lettres, sachant que le A et le O sont répétés deux fois chacun est : [latex]\frac{9!} {2! \times 2!} = 90.720[/latex]
De façon plus générale, soit [latex]X[/latex] un ensemble de [latex]n[/latex] éléments pas forcément tous distincts. Notons [latex]F[/latex] l’ensemble des éléments distincts de [latex]X[/latex] et pour chaque [latex]k[/latex] de [latex]F[/latex], notons [latex]val(k)[/latex] le nombre de fois que cet élément [latex]k[/latex] apparaît dans [latex]X[/latex]. Le nombre de permutations avec répétition s’écrit sous la forme [latex]\frac {n!} {\prod\limits_{i=1}^F val(k_i)!}[/latex]
En écriture contractée, on ne fait pas apparaître les éléments uniques car [latex]1! = 1[/latex]. Par application stricte de la théorie, la formulation complète pour le calcul du nombre de permutations du mot AUTORADIO aurait été : [latex]\frac {9!} {2! \times 1! \times 1! \times 2! \times 1! \times 1! \times 1!}[/latex]
