Permutation avec répétition

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 (k ≤ n) 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.

Sommaire

Définition

Soit E un ensemble fini de cardinal k (k ∈ ℕ∗), E={x1, x2, ..., xk}. Soient n un entier tel que k ≤ n 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

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

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!}.

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 x1, x2, ..., xk 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 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

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

Étant donnés les entiers naturels n1, n2 , ... , nk tels que n1 + n2 + ... + nk=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 n1, n2 , ... , nk répétitions.

Ainsi

(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}.

Voyez également


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Permutation avec répétition de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Permutation avec repetition — 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.… …   Wikipédia en Français

  • Combinaison Avec Répétition — Sommaire 1 Première approche 2 Une autre représentation 3 Nombre de combinaisons avec répétition 4 Une troisième dé …   Wikipédia en Français

  • Combinaison avec repetition — Combinaison avec répétition Sommaire 1 Première approche 2 Une autre représentation 3 Nombre de combinaisons avec répétition 4 Une troisième dé …   Wikipédia en Français

  • Combinaison avec répétition — Dans le domaine des dénombrements (mathématiques), une combinaison avec répétition est une combinaison où donc l ordre des éléments n importe pas et où, contrairement à une combinaison classique, chaque élément de la combinaison peut apparaître… …   Wikipédia en Français

  • Permutation — En mathématiques, la notion de permutation exprime l idée de réarrangement d objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l ordre de succession de ces n objets. La… …   Wikipédia en Français

  • Permutable — Permutation En mathématiques, la notion de permutation exprime l idée de réarrangement d objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l ordre de succession de ces n objets …   Wikipédia en Français

  • Arrangement — Pour les articles homonymes, voir Arrangement (homonymie). La notion d arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire. En mathématiques, lorsque nous choisissons k objets parmi n objets et… …   Wikipédia en Français

  • Arrangement (Mathématiques) — Arrangement Pour les articles homonymes, voir Arrangement (homonymie). La notion d arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire. En mathématiques, lorsque nous choisissons k objets parmi n… …   Wikipédia en Français

  • Arrangement (mathematiques) — Arrangement Pour les articles homonymes, voir Arrangement (homonymie). La notion d arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire. En mathématiques, lorsque nous choisissons k objets parmi n… …   Wikipédia en Français

  • Arrangement (mathématiques) — Arrangement Pour les articles homonymes, voir Arrangement (homonymie). La notion d arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire. En mathématiques, lorsque nous choisissons k objets parmi n… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”