Permutation avec répétition

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

En mathématiques, 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 (k ≤ n) placés dans un n-uplet, et supposons que chacun d'entre eux apparaisse respectivement n₁ fois, n₂ fois, ..., n_k fois avec n₁+n₂+...+n_k=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 :

Soit E un ensemble fini de cardinal k (k ∈ ℕ^∗), E={x₁, x₂, ..., x_k}. Soient n un entier tel que k ⩽ n et n₁, n₂, ..., n_k des entiers naturels tels que

n₁+n₂ + ... + n_k=n.

Une permutation de n éléments de E avec n₁, n₂, ..., n_k répétitions, est un n-uplet d'éléments de E dans lequel chacun des éléments x₁, x₂, ..., x_k de E apparaît n₁, n₂, ..., 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 p(n₁, n₂, ..., n_k) de permutations de n éléments avec n₁, n₂, ..., n_k répétitions est

$p(n_1, n_2, \ldots, n_k)=\frac{n!}{n_1!.n_2!\ldots n_k!}$ .

Ce nombre se note habituellement $C_{n}^{n_1,n_2, \ldots, n_k}$ .

Démonstration :

Pour construire un n-uplet correspondant à une combinaison contenant n₁ fois x₁, n₂ fois x₂, ..., n_k fois x_k, il suffit

de choisir les n₁ emplacements des x₁, parmi n₁ + n₂ + ... +n_k places disponibles,
de choisir les n₂ emplacements des x₂, parmi les n₂ + ... +n_k places restantes,
etc.
de choisir les n_k emplacements des x_k, parmi les n_k places restantes.

Au total, il y a

$C_{n_1+n_2+\ldots+n_k}^{n_1}.C_{n_2+\ldots+n_k}^{n_2}\ldots C_{n_k}^{n_k}=\frac{n!}{n_1!n_2!\ldots n_k!}$ .

[modifier] 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₁, x₂, ..., x_k dans lequel pour tout 1 ⩽ i ⩽ n, un terme du i-ième facteur se trouve à la ième place.

Pour tout 1 ⩽ i ⩽ k, notons n_i le nombre de fois où x_i apparaît dans un tel n-uplet. Nous avons

n₁ + n₂ + ... + n_k=n.

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

$x_1^{n_1}.x_2^{n_2}\ldots x_k^{n_k}$ .

Étant donnés les entiers naturels n₁, n₂ , ... , n_k tels que n₁ + n₂ + ... + 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 de n éléments avec n₁, n₂ , ... , n_k répétitions.