Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Indicateur de cycles
Résumé
En combinatoire, un indicateur de cycles est un polynôme en plusieurs variables qui porte certaines informations sur l'action d'un groupe de permutations. Cette manière algébrique et condensée de stocker des informations est souvent utilisée dans des problèmes de dénombrement.
Toute permutation π d'un ensemble fini partitionne cet ensemble en cycles ; le monôme indicateur de cycles de π est un produit de puissances des variables a, a, ... qui décrit le « type » de cette partition, ou « type de cycles » de π : l'exposant de a est le nombre de cycles de π de longueur i. Le polynôme indicateur de cycles d'un groupe de permutations est la moyenne des monômes indicateurs de cycles des éléments de ce groupe.
Ce polynôme permet de compter les orbites de l'action du groupe. Il est l'ingrédient principal du théorème de dénombrement de Pólya. Effectuer sur ces polynômes des opérations algébriques formelles et des opérations de différentiation, puis les interpréter combinatoirement, est au cœur de la .
Groupe de permutations
Un groupe de permutations est un sous-groupe du groupe symétrique S des bijections d'un ensemble X dans lui-même.
Soient G un groupe et φ un morphisme de groupes de G dans S. L' est un groupe de permutations, et la donnée de φ équivaut à celle d'une action de G sur X, appelée une « représentation de G par permutations ».
Dans les applications combinatoires, on s'intéresse plus à l'ensemble X qu'au groupe G qui agit sur lui ; par exemple, on veut dénombrer les structures sur X invariantes par cette action. Dans ce cadre, on perd peu à s'intéresser plutôt à l'action du groupe de permutations φ(G) qu'à celle du groupe G lui-même. (Les algébristes, au contraire, s'intéressent plus aux groupes eux-mêmes, donc au de φ, qui mesure ce que l'on perd en passant de l'action de G à celle de φ(G).)
L'indice de cycles d'un groupe de permutations G agissant sur un ensemble X à n éléments est le polynôme en les variables a, a, ... a :
où pour tout élément g de G et pour chaque k de 1 à n, j(g) est le nombre de k-cycles de la permutation de X associée à g.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.