Sans répétition
Le nombre de permutations d'un ensemble $\{a_1, \ldots, a_n\}$ de $n$ objets distincts est simplement le nombre de façons de ranger ces $n$ objets, c'est-à-dire de les ordonner.
Exemples concrets :
- On possède $6$ livres que l'on désire ranger sur une étagère. De combien de manières peut-on procéder ?
- Combien le mot MATHS possède-t-il d'anagrammes (ceux-ci ne doivent pas forcément être des mots de la langue française) ?
Formule (permutations sans répétition)
Le nombre de permutations de $n$ objets distincts est donné par
$$P_n = n!$$
Note : la notation $n!$ désigne le produit $n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1$, il s'agit de la factorielle de $n$. En particulier, on définit $0! = 1$ (car il s'agit du produit d'aucun terme).
Démonstration
Étant donnés $n$ objets $\{a_1, \ldots, a_n\}$, on a $n$ choix de placement pour le premier objet $a_1$. Une fois celui-ci placé, il reste $(n-1)$ positions possibles pour le deuxième objet $a_2$. Ainsi de suite, jusqu'au dernier objet pour lequel il reste une seule position. En multipliant ces nombres, on a finalement $n \cdot (n-1) \cdot \ldots \cdot 1 = n!$ façons de ranger les $n$ objets.
Solutions des exemples :
- On a donc $6! = 720$ manières de ranger nos $6$ livres sur une étagère.
- On a $5$ lettres différentes, qui sont les $5$ objets, et on se demande de combien de façons on peut les permuter. Il y a $5! = 120$ permutations, dont celle redonnant le mot MATHS, donc ce mot possède $119$ anagrammes.
Avec répétitions
Le même problème se pose lorsque certains objets sont identiques. On a cette fois $n$ objets, dont $r_1$ sont de type $1$, $r_2$ sont de type $2$, ..., et $r_k$ sont de type $k$ (avec $r_1 + \ldots + r_k = n$). À nouveau, on se demande de combien de manières on peut ranger ces $n$ objets, mais on considère cette fois que deux objets du même type sont identiques (ainsi, inverser deux objets du même type ne change pas le rangement).
Exemples concrets :
- Jacques a $6$ enfants et $6$ balles : une balle bleue, deux balles rouges et trois balles vertes. De combien de manières peut-il donner une balle à chaque enfant ?
- Combien le mot MAMAN possède-t-il d'anagrammes ?
Formule (permutations avec répétitions)
Le nombre de permutations de $n$ objets dont $r_1$ sont de type $1$, ..., $r_k$ sont de type $k$, est donné par
$$P(n; r_1, \ldots, r_k) = \frac{n!}{r_1! \cdot \ldots \cdot r_k!}.$$
Démonstration
On considère d'abord les $n$ objets comme étant distincts. Il y a alors, comme vu précédemment, $n!$ façons de les ranger. Si maintenant nous désirons ne plus distinguer des objets du même type, alors il y a parmi les $n!$ rangements certains rangements équivalents (c'est-à-dire qui sont identiques du point de vue des types). Plus précisément, étant donné un rangement des $n$ objets, on peut permuter les $r_1$ objets de type $1$, les $r_2$ objets de type $2$, ... et les $r_k$ objets de type $k$ et on retombera toujours sur un rangement équivalent. Il y a $r_1!\cdot \ldots \cdot r_k!$ façons d'effectuer ces permutations, ce qui signifie que l'on a des groupes de $r_1!\cdot \ldots \cdot r_k!$ rangements équivalents. Lorsqu'on ne distingue plus les objets du même type, on n'a donc plus $n!$ rangements mais bien
$$\frac{n!}{r_1! \cdot \ldots \cdot r_k!}.$$
Solutions des exemples :
- Jacques a $n = 6$ balles, $r_1 = 1$ de type "bleue", $r_2 = 2$ de type "rouge" et $r_3 = 3$ de type "verte". On souhaite ranger ces $6$ balles (pour les donner aux $6$ enfants), sans distinguer celles ayant le même type. Le nombre de façons de procéder est donc égal à
$$\frac{6!}{3! \cdot 2! \cdot 1!} = \frac{720}{6\cdot 2 \cdot 1} = 60.$$
- Les objets sont à nouveau les lettres, mais on a deux lettres du type M, deux lettres du type A et une lettre du type N, et il y a donc
$$\frac{5!}{2! \cdot 2! \cdot 1!} = \frac{120}{2 \cdot 2 \cdot 1} = 30$$ permutations. Le mot MAMAN possède donc $29$ anagrammes.
Conséquence
Il existe un corollaire immédiat au dernier résultat. En effet, par définition nous savons que le nombre de permutations de $n$ objets (distincts ou non) est toujours un nombre entier. On en déduit donc que le nombre
$$\frac{n!}{r_1!\cdot \ldots \cdot r_k!}$$ est toujours un nombre entier lorsque $r_1 + \ldots + r_k = n$. Cela n'est en fait a priori pas évident ! Certes, on sait que chaque $r_i !$ divise $n!$ puisque $r_i \leq n$, mais il semble beaucoup moins aisé de démontrer que le produit $r_1! \cdot \ldots \cdot r_k!$ divise toujours $n!$. Cela n'est en fait pas facile sans utiliser le fait que cette expression représente un nombre combinatoire entier.