Permutation avec répétition

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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éfinition[modifier | modifier le code]

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.

Exemple[modifier | modifier le code]

Le n-uplet

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

Théorème[modifier | modifier le code]

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é.

Application[modifier | modifier le code]

.

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 aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :