# 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

Soit E un multiensemble de n éléments pas forcément tous distincts.
Numérotons x$_1$, x$_2$, … , 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}!}}$.
Pour construire un n-uplet contenant n$_i$ fois x$_i$ pour chaque indice i, il suffit de choisir :
* les n$_1$ emplacements des x$_1$, parmi les n = n$_1$ + n$_2$ + ... + n$_k$ places disponibles ;
* puis, les n$_2$ emplacements des x$_2$, parmi les n$_2$ + ... +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}}$.
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é.
(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}!}}$.
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.)
| Permutations sans répétition | Combinaisons sans répétition |