Théorie > Combinatoire > Dénombrement

Permutations

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 :
  1. On possède $6$ livres que l'on désire ranger sur une étagère. De combien de manières peut-on procéder?
  2. 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) ?

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

Démonstration :
Etant 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$. Ansi de suite, on a finalement $n \cdot (n-1) \cdot \ldots \cdot 1 = n!$ façons de ranger les $n$ objets.

Solutions des exemples :
  1. On a donc $6! = 720$ manières de ranger nos $6$ livres sur une étagère.
  2. 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$). A 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 :
  1. On possède $6$ balles : une balle bleue, deux balles rouges et trois balles vertes. De combien de manière peut-on distribuer ces balles à $6$ enfants?
  2. Combien le mot MAMAN possède-t-il d'anagrammes?

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 :
  1. On a $n = 6$, $r_1 = 1$, $r_2 = 2$ et $r_3 = 3$. Le nombre de façons de donner les $6$ balles à des enfants est donc égal à
    $$\frac{6!}{3! \cdot 2! \cdot 1!} = \frac{720}{6\cdot 2 \cdot 1} = 60.$$
  2. 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.