Leçons de niveau 13

Combinatoire/Permutations avec répétition

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Permutations avec répétition
Icône de la faculté
Chapitre no 6
Leçon : Combinatoire
Chap. préc. :Permutations sans répétition
Chap. suiv. :Combinaisons sans répétition
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Combinatoire : Permutations avec répétition
Combinatoire/Permutations avec répétition
 », n'a pu être restituée correctement ci-dessus.

Dans le cas où il existerait une ou des répétitions dans le groupe à réordonner, nous devons limiter ce nombre. En effet, les éléments de ces répétitions sont indiscernables entre eux et dès lors une inversion de tels éléments ne crée pas une nouvelle permutation.

Exemple[modifier | modifier le wikicode]

Les « anagrammes » (avec ou sans signification quelle que soit la langue) du mot « CELLULE », c'est-à-dire les permutations des 7 lettres {C,E,E,L,L,L,U}.

Si toutes les lettres avaient été distinctes, nous aurions eu le cas d'une « Permutation sans répétition », donc nous aurions pu déduire du chapitre précédent le nombre .

Cependant il y a deux groupes de répétitions : 2×E et 3×L. Dans l’ensemble des anagrammes on ne peut donc pas distinguer les « mots » dont la seule différence est d'inverser les deux E entre eux, par exemple. Les deux anagrammes obtenus par la méthode « sans répétition » mais qui ne diffèrent que par l'inversion de ces deux E sont donc identiques à présent et il faut décompter tous les cas semblables. Dans cet exemple, nous devons supprimer tous les cas dus aux deux E (2! cas) et ceux dus aux trois L (3! cas, c'est-à-dire 6 cas).

On obtient donc le résultat .

Cas général[modifier | modifier le wikicode]

Wikipédia possède un article à propos de « Permutation avec répétition ».

Soit E un multiensemble de n éléments pas forcément tous distincts.

Numérotons x1, x2, … , xk les éléments distincts de E et pour chaque indice i, notons ni le nombre de fois que l'élément xi apparaît dans E.

Le nombre de permutations de E est alors :

.

Remarquez que quand un élément xi n'apparaît qu'une fois, on peut négliger le ni correspondant car 1! = 1.

Formule du multinôme[modifier | modifier le wikicode]

Wikipédia possède un article à propos de « Formule du multinôme ».

Les nombres de permutations avec répétition apparaissent tout naturellement dans la preuve combinatoire de la formule suivante (dont le cas particulier est la formule du binôme) :

.