Théorème de dénombrement de Pólya

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.