Permutation avec répétition

En mathématiques, les permutations avec répétition d'objets dont certains sont indifférenciés sont les divers groupements ordonnés de tous ces objets. Par exemple, 112, 121 et 211, pour deux chiffres 1, et un chiffre 2.

Lorsqu'on permute $n$ objets partiellement discernables et rangés dans un certain ordre, on retrouve dans certains cas la même disposition. On considère $n$ objets dont $k$ seulement sont distincts ($k\leqslant n$) placés dans un n-uplet, et on suppose que chacun d'entre eux apparaisse respectivement $n_{1}$ fois, $n_{2}$ fois, … , $n_{k}$ fois avec $n_{1}+n_{2}+\cdots +n_{k}=n$. Quand des éléments identiques de ce n-uplet sont permutés, on obtient le même n-uplet.

Par exemple, si on veut déterminer toutes les anagrammes du mot MATHÉMATIQUE, on peut voir qu'en échangeant les deux lettres A, le mot reste identique, tandis qu'en transposant les lettres É et E, on obtient un mot différent.

Définition

Soit $E=\{x_{1},x_{2},\dots ,x_{k}\}$ un ensemble fini de cardinal $k$. Soient $n_{1},n_{2},\dots ,n_{k}$ des entiers naturels et $n$ leur somme.

Une permutation à $n$ éléments de $E$ avec $n_{1},n_{2},\dots ,n_{k}$ répétitions est un n-uplet d'éléments de E dans lequel chacun des éléments $x_{1},x_{2},\dots ,x_{k}$ de $E$ apparaît respectivement $n_{1},n_{2},\dots ,n_{k}$ fois.

Exemple

Le n-uplet

${\begin{matrix}(\underbrace {x_{1},\ldots ,x_{1}} ,&\underbrace {x_{2},\ldots ,x_{2}} ,&\ldots ,&\underbrace {x_{k},\ldots ,x_{k}} )\\{}_{n_{1}{\rm {\,fois}}}&{}_{n_{2}{\rm {\,fois}}}&&{}_{n_{k}{\rm {\,fois}}}\end{matrix}}$

est une permutation avec répétition particulière.

Théorème

Le nombre de permutations à $n$ éléments avec $n_{1},n_{2},\dots ,n_{k}$ répétitions est égal à ${\frac {n!}{n_{1}!\,n_{2}!\ldots n_{k}!}}$.

Ce nombre se note habituellement ${\binom {n}{n_{1},n_{2},\ldots ,n_{k}}}$, et est connu sous le nom de coefficient multinomial.

Une démonstration est disponible via le lien (voir infra) vers Wikiversité.

Application

${\begin{matrix}(x_{1}+x_{2}+\ldots +x_{k})^{n}=&\underbrace {(x_{1}+x_{2}+\ldots +x_{k})(x_{1}+x_{2}+\ldots +x_{k})\ldots (x_{1}+x_{2}+\ldots +x_{k})} \\&{}_{n{\rm {\,fois}}}\end{matrix}}$.

Le développement de ce produit de facteurs est une somme de produits qui peuvent être représentés par un n-uplet d'éléments $x_{1},x_{2},\dots ,x_{k}$ dans lequel pour tout $1\leqslant i\leqslant k$, un terme du i-ième facteur se trouve à la i-ème place.

Pour tout $1\leqslant i\leqslant k$, on note $n_{i}$ le nombre de fois où $x_{i}$ apparaît dans un tel n-uplet. On a

$n_{1}+n_{2}+\cdots +n_{k}=n$.

Sous réserve que la loi × soit commutative (ou plus généralement que les $x_{i}$ commutent pour la loi ×), le produit correspondant à un tel n-uplet est égal à

$x_{1}^{n_{1}}x_{2}^{n_{2}}\ldots x_{k}^{n_{k}}$.

Étant donnés les entiers naturels $n_{1},n_{2},\dots ,n_{k}$ tels que $n_{1}+n_{2}+\cdots +n_{k}=n$, le nombre de termes de la forme $x_{1}^{n_{1}}x_{2}^{n_{2}}\ldots x_{k}^{n_{k}}$ est le nombre de permutations à $n$ éléments avec $n_{1},n_{2},\dots ,n_{k}$ répétitions.

On en déduit la formule du multinôme de Newton :

$(x_{1}+x_{2}+\ldots +x_{k})^{n}=\sum _{n_{1}+n_{2}+\ldots +n_{k}=n}{\frac {n!}{n_{1}!n_{2}!\ldots n_{k}!}}x_{1}^{n_{1}}x_{2}^{n_{2}}\ldots x_{k}^{n_{k}}$

(qui inclut, pour $k=2$, la formule du binôme).

Voir aussi

• Coefficient multinomial