Différentes permutations

Les permutations permettent de dénombrer les classements de différents éléments dans un certain ordre. Ces éléments peuvent être tous distincts ou non. Le chapitre suivant sera dévolu au premier cas et le dernier au dénombrement d’éléments en partie différents. 

Le premier cas est assez simple, quant au second il ne demande qu’un peu de réflexion pour être acquis.

Définition mathématique : les permutations de n éléments est le calcul du nombre de possibilités d’ordonner ces n éléments ! C’est donc un nombre entier non nul (nous verrons le cas où n vaut zéro). 

Définition des factorielles : la notion de factorielle est essentielle quand on fait du dénombrement. Nous nous intéresserons seulement aux factorielles de nombres entiers. La factorielle de n pour $n \in \mathbb{N}$ se note $n!$ et se calcule de la manière suivante :

Quand on parle de permutations sans répétition c’est qu’on a affaire à des objets tous différentiables. On s’intéresse au nombre de façons de les ordonner. 

Si on a n objets et qu'on souhaite les ordonner, il faut commencer par choisir le premier objet. On a alors n possibilités. Une fois qu'il a été choisi, il reste seulement (n-1) possibilités pour le suivant. Ensuite on a (n-2) possibilités et ainsi de suite jusqu'au dernier qui reste seul et n'offre plus d'autre possibilité que d'être choisi !

Ce qui donne $n!=n\cdot(n-1)\cdot(n-2)\cdot(n-3)\cdot\ldots\cdot\ 2 \cdot 1$

La formule est donc extraordinairement simple, la permutation de n objets distincts est le nombre $n!$.

Ici, l’on considère un certain nombre d’objets parmi lesquels certains sont identiques. 

L'opération est ici plus compliquée. Il faut dans un premier temps faire abstraction du fait que certains objets ne puissent pas être distingués. On fait comme si on parvenaient à les différencier, puis on divise par le nombre d'arrangements de ces objets qui sont identiques du fait que les différents objets ne se distinguent pas les uns des autres.

Première approche :

Pour donner une idée, commençons par imaginer qu'on a 5 objets dont deux ne sont pas  différentiables.

Si on distingue les deux qui ne sont pas différentiables, on a donc 5!=120 possibilités. Mais pour chacune d'entre elles, on peut échanger les deux objets. On en a donc calculé deux fois trop. En fait, on aura donc 120/2=60 dispositions différentes.

Seconde approche :

Imaginons que sur les 5 objets, on en a cette fois trois qui ne peuvent pas être distingués. Sur les 120 possibilités, il y en a cette fois six fois trop, car on peut intervertir les trois objets similaires sans changer l'ordre de ces ordonnances. Le nombre de possibilités d'ordonner ces trois objets est lui-même de 3!=6. Par exemple, si on a trois "a", un "b" et un "c", peut écrire 120 "mots" si on distingue les "a" (disons $a_1, a_2$ et $a_3$). Mais les différents mots $ba_1ca_2a_3, ba_2ca_1a_3, ba_3ca_1a_2$... sont tous identiques si on ne tient pas compte des indices qui ont été rajoutés. 

Première approche générale :

Si on a n objets dont m ne sont pas distinguables, la formule est donc $\frac{n!}{m!}$, puisqu'on obtiendra n! solutions parmi lesquelles à chaque fois m! ne pourront pas être distinguées.

Deuxième approche générale :

Si on a n objets parmi lesquels on a k collections de termes semblables : $n_1$ sont identiques et $n_2$ autres sont semblables et ainsi de suite jusqu'aux $n_k$ qui sont également semblables.

Alors la formule générale devient $\frac{n!}{n_1!\cdot n_2!\cdot\ldots\cdot n_k!}$