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, et par contre en transposant les lettres É et E nous obtenons un mot différent.

Définition[modifier | modifier le code]

Soit E un ensemble fini de cardinal k (k ∈ ℕ), E={x1, x2, ..., xk}. Soient n un entier tel que kn et n1, n2, ..., nk des entiers naturels tels que

n1+n2 + ... + nk=n.

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 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 p(n1, n2, ..., nk) de permutations de n éléments avec n1, n2, ..., nk répétitions est

.

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

Démonstration 

Pour construire un n-uplet correspondant à une combinaison contenant n1 fois x1, n2 fois x2, ..., nk fois xk, il suffit

  • de choisir les n1 emplacements des x1, parmi n1 + n2 + ... +nk places disponibles,
  • de choisir les n2 emplacements des x2, parmi les n2 + ... +nk places restantes,
  • etc.
  • de choisir les nk emplacements des xk, parmi les nk places restantes.

Au total, il y a

.

Application[modifier | modifier le code]

Sous réserve que la loi + soit commutative (ou plus généralement que les termes de la somme commutent pour la loi +), on a : 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.

Le produit correspondant à un tel n-uplet est de la forme

.

É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).

Articles connexes[modifier | modifier le code]