Combinatoire/Permutations avec répétition

Dans le cas où il existerait une ou des répétitions dans le groupe à réordonner, nous devons limiter ce nombre. En effet, les éléments de ces répétitions sont indiscernables entre eux et dès lors une inversion de tels éléments ne crée pas une nouvelle permutation.

Exemple

Les « anagrammes » (avec ou sans signification quelle que soit la langue) du mot « CELLULE », c'est-à-dire les permutations des 7 lettres {C,E,E,L,L,L,U}.

Si toutes les lettres avaient été distinctes, nous aurions eu le cas d'une « Permutation sans répétition », donc nous aurions pu déduire du chapitre précédent le nombre $P_7=7!=5040$.

Cependant il y a deux groupes de répétitions : 2×E et 3×L. Dans l’ensemble des anagrammes on ne peut donc pas distinguer les « mots » dont la seule différence est d'inverser les deux E entre eux, par exemple. Les deux anagrammes obtenus par la méthode « sans répétition » mais qui ne diffèrent que par l'inversion de ces deux E sont donc identiques à présent et il faut décompter tous les cas semblables. Dans cet exemple, nous devons supprimer tous les cas dus aux deux E (2! cas) et ceux dus aux trois L (3! cas, c'est-à-dire 6 cas).

On obtient donc le résultat $\frac{7!}{3!\times 2!}$.

Cas général

Modèle:Wikipédia Soit E un multiensemble de n éléments pas forcément tous distincts.

Numérotons x₁, x₂, … , x_k les éléments distincts de E et pour chaque indice i, notons n_i le nombre de fois que l'élément x_i apparaît dans E.

Le nombre de permutations de E est alors :

$\frac{n!}{n_1!n_2!\dots n_k!}$.

Remarquez que quand un élément x_i n'apparaît qu'une fois, on peut négliger le n_i correspondant car 1! = 1.

Formule du multinôme

Modèle:Wikipédia Les nombres de permutations avec répétition apparaissent tout naturellement dans la preuve combinatoire de la formule suivante (dont le cas particulier $m=2$ est la formule du binôme) :

${(X_1+X_2+\dots +X_m)}^n=\sum _{k_1+k_2+\dots +k_m=n}(\genfrac{}{}{0ex}{}{n}{k_1,k_2,\dots ,k_m})X_1^{k_1}{X}_2^{k_2}\dots X_m^{k_m}$.