Listes d'éléments distincts, permutations

3.1 Un exemple : le podium

Huit nageuses disputent la finale d'un $100$ mètres. Combien de podiums (or, argent, bronze) sont possibles ?

• $8$ choix pour la médaille d'or ;
• puis $7$ pour l'argent (toutes sauf la gagnante) ;
• puis $6$ pour le bronze.

Le nombre de choix à chaque étape ne dépend pas des choix déjà faits. Par le principe multiplicatif, il y a $8 \times 7 \times 6 = 336$ podiums. Un podium est un triplet de nageuses distinctes.

3.2 Nombre de $k$-uplets d'éléments distincts

Propriété (programme). Soit $E$ un ensemble à $n$ éléments et $k$ un entier tel que $1 \leq k \leq n$. Le nombre de $k$-uplets d'éléments distincts de $E$ est $n(n-1)(n-2)\cdots(n-k+1) \qquad (k \text{ facteurs}).$

Pourquoi. On choisit les éléments un par un : $n$ choix pour le premier, $n - 1$ pour le deuxième (tous sauf le premier), …, $n - k + 1$ pour le $k$-ième. Si $k > n$, il n'existe aucun $k$-uplet d'éléments distincts.

Exemple 9. Un code de $4$ chiffres dont les chiffres sont tous différents est un $4$-uplet d'éléments distincts de $\{0\,;1\,;\ldots\,;9\}$ : il y en a $10 \times 9 \times 8 \times 7 = 5\,040$. Par complémentaire, $10\,000 - 5\,040 = 4\,960$ codes ont au moins deux chiffres égaux.

3.3 La factorielle

Définition (programme). Pour tout entier $n \geq 1$, la factorielle de $n$ est $n! = 1 \times 2 \times 3 \times \cdots \times n.$ Par convention, $0! = 1$. On lit « factorielle $n$ ».

Pour tout entier $n \geq 0$, $(n + 1)! = (n + 1) \times n!$. La factorielle grandit très vite : $20! \approx 2{,}43 \times 10^{18}$.

3.4 Permutations

Définition. Une permutation d'un ensemble fini $E$ à $n$ éléments est un $n$-uplet d'éléments distincts de $E$ : c'est une façon de ranger tous les éléments de $E$ dans un ordre.

Propriété (programme). Le nombre de permutations d'un ensemble à $n$ éléments est $n!$.

C'est le cas $k = n$ de la propriété 3.2 : $n(n - 1) \cdots 2 \times 1 = n!$.

Exemple 10. Les permutations de $\{a\,;b\,;c\}$ sont $(a\,;b\,;c)$, $(a\,;c\,;b)$, $(b\,;a\,;c)$, $(b\,;c\,;a)$, $(c\,;a\,;b)$ et $(c\,;b\,;a)$ : il y en a $3! = 6$.

Exemple 11. On range $5$ livres différents sur une étagère : il y a $5! = 120$ rangements. De même, en mélangeant les cinq lettres, toutes différentes, du mot PLAGE, on écrit $120$ mots (qui ont un sens ou non).

3.5 Écriture avec des factorielles

Pour $1 \leq k \leq n$ : $n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!},$ car les facteurs de $1$ à $n - k$ de $n!$ se simplifient avec ceux de $(n - k)!$. Par exemple, $8 \times 7 \times 6 = \dfrac{8!}{5!} = \dfrac{40\,320}{120} = 336$.