Combinatoire/Permutations avec répétition

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

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

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}!\ldots n_{k}!}}$.

Démonstration

Pour construire un n-uplet contenant n_i fois x_i pour chaque indice i, il suffit de choisir :

• les n₁ emplacements des x₁, parmi les n = n₁ + n₂ + ... + n_k places disponibles ;
• puis, les n₂ emplacements des x₂, parmi les n₂ + ... +n_k places restantes ;
• etc.
• enfin, les n_k emplacements des x_k, parmi les n_k places restantes.

Au total, il y a donc

${\binom {n_{1}+n_{2}+\ldots +n_{k}}{n_{1}}}{\binom {n_{2}+\ldots +n_{k}}{n_{2}}}\dots {\binom {n_{k}}{n_{k}}}={\frac {n!}{n_{1}!n_{2}!\dots n_{k}!}}$ permutations.

 

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

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) :

$\left(X_{1}+X_{2}+\dots +X_{m}\right)^{n}=\sum _{k_{1}+k_{2}+\dots +k_{m}=n}{n \choose k_{1},k_{2},\dots ,k_{m}}X_{1}^{k_{1}}X_{2}^{k_{2}}\dots X_{m}^{k_{m}}$.

Preuve combinatoire

Lorsqu'on développe par distributivité l'expression

$\left(X_{1}+X_{2}+\dots +X_{m}\right)^{n}=\left(X_{1}+X_{2}+\dots +X_{m}\right)\left(X_{1}+X_{2}+\dots +X_{m}\right)\dots \left(X_{1}+X_{2}+\dots +X_{m}\right)\qquad (n{\text{ fois}})$,

et qu'on réordonne les indéterminées dans chaque monôme, on obtient une somme de monômes de la forme $X_{1}^{k_{1}}X_{2}^{k_{2}}\dots X_{m}^{k_{m}}$ où $k_{i}$ représente le nombre de parenthèses dans lesquelles on a sélectionné $X_{i}$ en développant. Pour chacun de ces monômes, la somme des $k_{i}$ est égale à $n$ (le nombre total de parenthèses), et ce monôme apparaît ${n \choose k_{1},k_{2},\dots ,k_{m}}$ fois dans le développement puisque c'est le nombre de façons de choisir lesquelles, parmi les $n$ parenthèses, seront pour chaque $i$ les $k_{i}$ parenthèses dans lesquelles c'est $X_{i}$ qui est sélectionné.

 

Preuve par récurrence sur $m$

(i) Pour $m=1$, les deux membres valent $X_{1}^{n}$.

(ii) Supposons le théorème vrai au rang $m$. Alors,

${\begin{aligned}\left(X_{1}+X_{2}+\dots +X_{m}+X_{m+1}\right)^{n}&=\left(X_{1}+X_{2}+\dots +\left(X_{m}+X_{m+1}\right)\right)^{n}\\&=\sum _{k_{1}+k_{2}+\dots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\dots ,k_{m-1},K}X_{1}^{k_{1}}X_{2}^{k_{2}}\dots X_{m-1}^{k_{m-1}}\left(X_{m}+X_{m+1}\right)^{K}\end{aligned}}$

par hypothèse de récurrence. Puis, en appliquant la formule du binôme au dernier facteur :

${\begin{aligned}\left(X_{1}+X_{2}+\dots +X_{m}+X_{m+1}\right)^{n}&=\sum _{k_{1}+k_{2}+\dots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\dots ,k_{m-1},K}X_{1}^{k_{1}}X_{2}^{k_{2}}\dots X_{m-1}^{k_{m-1}}\sum _{k_{m}+k_{m+1}=K}{K \choose k_{m},k_{m+1}}X_{m}^{k_{m}}X_{m+1}^{k_{m+1}}\\&=\sum _{k_{1}+k_{2}+\dots +k_{m-1}+k_{m}+k_{m+1}=n}{n \choose k_{1},k_{2},\dots ,k_{m-1},k_{m},k_{m+1}}X_{1}^{k_{1}}X_{2}^{k_{2}}\dots X_{m-1}^{k_{m-1}}X_{m}^{k_{m}}X_{m+1}^{k_{m+1}},\end{aligned}}$

ce qui termine la récurrence. Pour la dernière étape, on a utilisé le fait que

${n \choose k_{1},k_{2},\dots ,k_{m-1},K}{K \choose k_{m},k_{m+1}}={n \choose k_{1},k_{2},\dots ,k_{m-1},k_{m},k_{m+1}}$,

car

${\frac {n!}{k_{1}!k_{2}!\dots k_{m-1}!K!}}{\frac {K!}{k_{m}!k_{m+1}!}}={\frac {n!}{k_{1}!k_{2}!\dots k_{m+1}!}}$.

 

Preuve analytique

Pour tous nombres $x_{1},\dots ,x_{m},t$ complexes (ou même simplement réels),

$\exp \left(t\left(x_{1}+\dots +x_{m}\right)\right)=\exp \left(tx_{1}\right)\dots \exp \left(tx_{m}\right)$

d'où, par identification du coefficient de $t^{n}$ dans le développement en série entière des deux membres :

${\frac {\left(x_{1}+\dots +x_{m}\right)^{n}}{n!}}=\sum _{k_{1}+k_{2}+\dots +k_{m}=n}{\frac {x_{1}^{k_{1}}x_{2}^{k_{2}}\dots x_{m}^{k_{m}}}{k_{1}!k_{2}!\dots k_{m}!}}$.

(On peut rendre purement algébrique cette preuve « analytique », en raisonnant sur des séries formelles plutôt que des séries entières.)