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.

Lorsque nous permutons n objets partiellement discernables et rangés dans un certain ordre, nous retrouvons dans certains cas la même disposition. Considérons n objets dont k seulement sont distincts (kn) placés dans un n-uplet, et supposons que chacun d'entre eux apparaisse respectivement n1 fois, n2 fois, … , nk fois avec n1 + n2 + … + nk = n. Quand des éléments identiques de ce n-uplet sont permutés, nous obtenons le même n-uplet.

Par exemple, si nous voulons déterminer toutes les anagrammes du mot MATHÉMATIQUE, nous voyons qu'en échangeant les deux lettres A, le mot reste identique, tandis qu'en transposant les lettres É et E, nous obtenons un mot différent.

DéfinitionModifier

Soit E = {x1, x2, … , xk} un ensemble fini de cardinal k. Soient n1, n2, … , nk des entiers naturels et n leur somme.

Une permutation de n éléments de E avec n1, n2, … , nk répétitions est un n-uplet d'éléments de E dans lequel chacun des éléments x1, x2, … , xk de E apparaît respectivement n1, n2, … , nk fois.

ExempleModifier

Le n-uplet

 

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

ThéorèmeModifier

Le nombre de permutations de n éléments avec n1, n2, … , nk répétitions est égal à  .

Ce nombre se note habituellement  , et est connu sous le nom de coefficient multinomial.

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

ApplicationModifier

 .

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 x1, x2, … , xk dans lequel pour tout 1 ≤ in, un terme du i-ième facteur se trouve à la i-ème place.

Pour tout 1 ≤ ik, notons ni le nombre de fois où xi apparaît dans un tel n-uplet. Nous avons

n1 + n2 + … + nk = n.

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

 .

Étant donnés les entiers naturels n1, n2 , … , nk tels que n1 + n2 + … + nk = n, le nombre de termes de la forme   est le nombre de permutations de n éléments avec n1, n2 , … , nk répétitions.

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

 

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

Voir aussiModifier

Sur les autres projets Wikimedia :