Permutation avec répétition
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (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 (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les mathématiques...), 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 (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) 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 (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...) 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 (Une combinaison peut être :) 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 ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le total des dettes". En physique le total n'est pas forcément...), 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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

  • Permutation
  • coefficient (En mathématiques un coefficient est un facteur multiplicatif qui dépend d'un certain objet, comme une variable (par exemple, les coefficients d'un polynôme), un espace vectoriel, une fonction de base et...) multinomial
  • Formule du multinôme
Page générée en 0.012 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique