Permutations et Combinaisons

Les permutations dénombrent les arrangements ordonnés d'objets et les combinaisons dénombrent les sélections non ordonnées ; ensemble, elles constituent le cœur élémentaire de l'énumération.

Definition

Une permutation d'un ensemble est un arrangement ordonné de ses éléments (ou une bijection de l'ensemble sur lui-même) ; une combinaison est une sélection non ordonnée d'un nombre fixe d'éléments d'un ensemble.

Scope

Ce sujet développe le dénombrement des arrangements (avec et sans répétition), des sélections, et leurs raffinements, incluant les dérangements, les permutations circulaires et les permutations avec positions restreintes. Il introduit des statistiques de permutation telles que les descentes, les inversions et la structure cyclique, qui relient le dénombrement élémentaire à la théorie moderne plus riche du groupe symétrique.

Core questions

• De combien de manières n objets distincts peuvent-ils être ordonnés, et de combien de manières r d'entre eux peuvent-ils l'être ?
• Comment la répétition et l'indiscernabilité modifient-elles le dénombrement des arrangements ?
• Que sont les dérangements, et à quelle fréquence une permutation aléatoire ne fixe-t-elle aucun élément ?
• Quelles statistiques sur les permutations sont équidistribuées ?

Key concepts

• Factorielle et factorielle décroissante
• Arrangements avec et sans répétition
• Dérangements
• Permutations circulaires
• Inversions et descentes
• Nombres de Stirling

Key theories

Décomposition en cycles des permutations

Chaque permutation se factorise de manière unique en cycles disjoints ; le dénombrement des permutations par leur type de cycle est régi par les nombres de Stirling de première espèce et sous-tend la structure du groupe symétrique.

Dénombrement des dérangements

Le nombre de permutations sans point fixe, dérivé par le principe d'inclusion-exclusion, approche n!/e, ce qui donne le résultat classique qu'environ 37 % des permutations sont des dérangements.

Clinical relevance

Les dénombrements de permutations et de combinaisons apparaissent en probabilité (résultats équiprobables), dans les algorithmes de tri et de mélange, la conception expérimentale et les espaces de clés cryptographiques, où la taille d'un espace d'arrangement détermine la difficulté et la sécurité.

History

La combinatoire des permutations a été systématisée par les travaux de MacMahon au début du XXe siècle sur l'analyse combinatoire et approfondie par la suite grâce à la théorie moderne des statistiques de permutation.

Key figures

• Percy MacMahon
• Richard P. Stanley

Seminal works

• stanley2011

Frequently asked questions

Combien de permutations un ensemble de n éléments possède-t-il ?

Il possède n! permutations, le produit de tous les entiers positifs jusqu'à n, puisque chacune des n positions est remplie par un élément distinct restant.

Qu'est-ce qu'un dérangement ?

Un dérangement est une permutation dans laquelle aucun élément ne reste à sa position d'origine, comme un remaniement où aucune lettre ne retourne à sa propre enveloppe.