Permutations et arrangements

Ranger sans répéter

Dans la leçon précédente, les répétitions étaient autorisées. On s'intéresse maintenant aux situations où chaque élément ne peut être choisi qu'une seule fois.

### La factorielle

> Définition : pour tout entier $n \geqslant 1$, on appelle factorielle de $n$, notée $n!$, le nombre :
>

> Par convention, $0! = 1$.

Exemples : $3! = 3\times 2\times 1 = 6$ ; $\quad 5! = 5\times4\times3\times2\times1=120$.

On remarque que $n! = n\times(n-1)!$, ce qui permet de calculer une factorielle de proche en proche.

### Permutations

Une permutation d'un ensemble $E$ à $n$ éléments est un classement ordonné de tous les éléments de $E$ (chaque élément apparaît une fois et une seule).

> Nombre de permutations : le nombre de permutations d'un ensemble à $n$ éléments est :
>

Justification : pour la 1ère position, il y a $n$ choix ; pour la 2e position, il ne reste que $n-1$ choix (un élément a déjà été placé) ; et ainsi de suite jusqu'à la dernière position où il ne reste qu'1 choix. Par le principe multiplicatif :

Exemple : le nombre de façons de classer 5 coureurs à l'arrivée d'une course (sans ex-aequo) est $5! = 120$.

### Arrangements

Un arrangement de $p$ éléments parmi $n$ (avec $p\leqslant n$) est une $p$-liste sans répétition d'éléments de l'ensemble $E$ à $n$ éléments : on choisit $p$ éléments distincts de $E$ et on les ordonne.

> Nombre d'arrangements, noté $A_n^p$ :
>

Justification : pour la 1ère position, $n$ choix ; pour la 2e, $n-1$ choix (un élément déjà utilisé) ; ... ; pour la $p$-ième position, $n-p+1$ choix. On multiplie ces $p$ facteurs, ce qui donne bien $\dfrac{n!}{(n-p)!}$ après simplification.

On remarque que lorsque $p=n$, on retrouve $A_n^n = \dfrac{n!}{0!} = n!$, c'est-à-dire le nombre de permutations.

### Exemple complet

Énoncé : dans une course de 8 chevaux, on souhaite prévoir le tiercé (les 3 premiers chevaux, dans l'ordre exact). Combien de tiercés différents sont possibles ?

Résolution : on choisit 3 chevaux parmi 8, en tenant compte de l'ordre, sans répétition (un même cheval ne peut pas arriver 1er ET 2e). Il s'agit donc d'un arrangement avec $n=8$ et $p=3$ :

Il existe donc $336$ tiercés possibles.

### Méthode

1. Si on range tous les éléments de l'ensemble : c'est une permutation, le résultat est $n!$.
2. Si on choisit $p$ éléments parmi $n$, dans un ordre précis, sans répétition : c'est un arrangement, le résultat est $A_n^p = \dfrac{n!}{(n-p)!}$.
3. Bien vérifier qu'aucune répétition n'est permise (sinon on retombe sur une $p$-liste $n^p$ de la leçon précédente).