Ê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
Théorème de dénombrement de Pólya
Résumé
Le théorème de dénombrement de Pólya est un théorème de combinatoire sur le nombre d'orbites d'une action d'un groupe fini sur les « coloriages » d'un ensemble fini, dont la démonstration est une version « pondérée » de celle du lemme de Burnside. Il a été publié pour la première fois par en 1927. En 1937, George Pólya l'a redécouvert indépendamment et l'a beaucoup popularisé en l'appliquant à de nombreux problèmes de dénombrement, en particulier pour compter les composés chimiques.
Le théorème de dénombrement de Pólya peut aussi être intégré à la et à la .
Soient X un ensemble fini et G un groupe de permutations de X (ou un groupe fini agissant sur X). On peut se représenter l'ensemble X comme un arrangement de perles et G comme un groupe de permutations que l'on choisit, sur ces perles. Par exemple, si X est un collier de n perles disposées en cercle, on peut choisir pour G le groupe cyclique C ; si X est un « bracelet » de n perles (en un cercle que l'on peut retourner), alors on peut choisir le groupe diédral D. Supposons de plus que C est un ensemble fini de t couleurs – les couleurs des perles – de telle sorte que l'ensemble C des applications de X dans C est l'ensemble des coloriages de l'arrangement X. Alors, l'action de G sur l'ensemble X des arrangements induit une action sur l'ensemble C des arrangements colorés, par (g.f)(x) = f(g.x). Le lemme de Burnside permet de calculer le nombre d'orbites sous G d'arrangements colorés, en notant, pour chaque élément g du groupe, j(g) le nombre de cycles de la permutation de X associée, et en utilisant qu'un coloriage est fixe par g si et seulement s'il est constant sur chacun de ces cycles :
On retrouvera ce résultat comme corollaire du théorème de dénombrement de Pólya.
Dans la version générale, à chaque couleur c est associée une variable y (il peut y en avoir une infinité) et le « poids » w(f) d'un coloriage f, c'est-à-dire d'une application de l'ensemble fini X dans l'ensemble C des couleurs, est le monôme produit des y, où chaque exposant n est le nombre d'éléments de X de couleur c.
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.