Indicateur de cycles

Modèle:Voir homonymes 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 aModèle:Ind, aModèle:Ind, … qui décrit le « type » de cette partition, ou « type de cycles » de π : l'exposant de aModèle:Ind 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 Modèle:Lien.

Groupes de permutations et actions de groupes

Modèle:Article détaillé Un groupe de permutations est un sous-groupe du groupe symétrique SModèle:Ind des bijections d'un ensemble X dans lui-même.

Soient G un groupe et φ un morphisme de groupes de G dans SModèle:Ind. L'image φ(G) 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 noyau de φ, qui mesure ce que l'on perd en passant de l'action de G à celle de φ(G).)

Définition

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 Modèle:Math :

$Z(G)=\frac{1}{|G|}\sum _{g\in G}\prod _{k=1}^n{a}_k^{j_k(g)},$

où pour tout élément g de G et pour chaque Modèle:Math de 1 à n, Modèle:Math(g) est le nombre de Modèle:Math-cycles de la permutation de X associée à g. (Ces entiers naturels vérifient donc ${\sum }_{k=1}^{n}k{j}_k(g)=n$.)

Exemple

La [[#Groupe cyclique Cn|représentation régulière du groupe cyclique CModèle:Ind]] des rotations du carré est l'action sur l'ensemble X = {1, 2, 3, 4} des sommets (numérotés consécutivement dans le sens trigonométrique). Plus précisément, les rotations d'angles 0°, 90°, 180° et 270° agissent respectivement par (1)(2)(3)(4), (1 2 3 4), (1 3)(2 4) et (1 4 3 2) et les monômes indicateurs de cycles de ces quatre permutations sont Modèle:Math et Modèle:Math. L'indicateur de cycles de ce groupe de permutations est donc

$Z(C_4)=\frac{1}{4}(a_1^4+a_2^2+2a_4).$

Le groupe CModèle:Ind agit aussi naturellement sur l'ensemble des 6 paires de sommets, A = {1, 2}, B = {2,3}, C = {3,4}, D = {4, 1}, E = {1,3} et F = {2,4}, qui correspondent aux quatre côtés et aux deux diagonales du carré ou, dans un cadre complètement différent, aux arêtes du graphe complet KModèle:Ind. Sur ce nouvel ensemble, les quatre éléments du groupe agissent respectivement par (A)(B)(C)(D)(E)(F), (A B C D)(E F), (A C)(B D)(E)(F) et (A D C B)(E F) donc l'indicateur de cycles de cette action est

$Z(C_4)=\frac{1}{4}(a_1^6+a_1^2{a}_2^2+2a_2{a}_4).$

On peut aussi faire agir CModèle:Ind sur les 16 couples de sommets (qui correspondent aux arcs du graphe orienté complet DModèle:Ind, avec une boucle à chaque sommet). On trouve alors comme indicateur

$Z(C_4)=\frac{1}{4}(a_1^{16}+a_2^8+2a_4^4).$

Types d'actions

Comme le montre l'exemple ci-dessus, l'indicateur dépend non seulement du groupe mais de son action. Comme un groupe a de nombreuses représentations par permutation, un peu de terminologie est utile pour les distinguer.

• Lorsqu'un groupe est défini comme sous-groupe d'un groupe symétrique, c'est un groupe de permutations et son « action naturelle » est le morphisme canonique d'inclusion du sous-groupe dans le groupe. Par exemple, l'action naturelle du groupe symétrique d'indice 3$S_3=\{\text{id},(23),(12),(123),(132),(13)\}$a pour indicateur de cycles$Z(S_3)=\frac{1}{6}(a_1^3+3a_1{a}_2+2a_3).$
• L'action d'un groupe sur lui-même par translations (cf. Théorème de Cayley), simplement transitive, sera appelée sa « représentation régulière » dans le cadre de cet article.
  On a déjà vu l'exemple de la [[#Exemple|représentation régulière du groupe cyclique CModèle:Ind]]. Celle du groupe cyclique CModèle:Ind contient les 6 permutations(1)(2)(3)(4)(5)(6), (1 2 3 4 5 6), (1 3 5)(2 4 6), (1 4)(2 5)(3 6), (1 5 3)(2 6 4) et (1 6 5 4 3 2)donc son indicateur de cycles est$Z(C_6)=\frac{1}{6}(a_1^6+a_2^3+2a_3^2+2a_6).$
• Pour d'autres actions, on choisit un nom qui les évoque, comme dans les trois exemples ci-dessous.

Groupe de permutations des arêtes du graphe complet sur 3 sommets

Le graphe complet KModèle:Ind est isomorphe à son graphe adjoint, donc l'action de SModèle:Ind sur les 3 arêtes, induite par son action naturelle sur les 3 sommets, est isomorphe à cette dernière et a par conséquent même indicateur de cycles.

Ce cas est exceptionnel : si n > 3, le graphe complet KModèle:Ind a strictement plus d'arêtes que de sommets.

Groupe de permutations des arêtes du graphe complet sur 4 sommets

L'action naturelle de SModèle:Ind sur les 4 sommets du graphe complet KModèle:Ind induit une action sur ses 6 arêtes. Pour dresser la liste des monômes indicateurs de cycles de cette action sur les arêtes, on procède exactement comme dans l'exemple ci-dessus du calcul de l'action de CModèle:Ind sur les paires de sommets. Accessoirement, on peut identifier KModèle:Ind à un tétraèdre régulier et interpréter ces 24 permutations (des sommets et des arêtes) comme les isométries de ce tétraèdre.

• L'identité fixe tous les points donc toutes les arêtes, donc son monôme est aModèle:IndModèle:6.
• Les 8 tiers de tour, d'axes joignant un sommet au centre de la face opposée, permutent circulairement trois des quatre sommets, donc permutent circulairement les trois arêtes de leur face commune, ainsi que les trois arêtes restantes, donc leurs 8 monômes sont égaux à aModèle:IndModèle:2.
• Les 3 demi-tours, d'axes joignant les centres de deux arêtes opposées, échangent 2 par 2 les quatre sommets, donc fixent les deux arêtes joignant chaque paire de sommets intervertis et échangent 2 par 2 les deux arêtes restantes, donc leurs 3 monômes sont égaux à aModèle:IndModèle:2aModèle:IndModèle:2.
• Les 6 réflexions, par rapport aux plans médiateurs des 6 arêtes, échangent deux sommets, donc fixent l'arête qui les joint et l'arête opposée et échangent 2 par 2 les quatre arêtes restantes, donc leurs 6 monômes sont encore aModèle:IndModèle:2aModèle:IndModèle:2.
• Les 6 permutations circulaires des quatre sommets (qui correspondent à des antirotations d'un quart de tour) permutent circulairement quatre des arêtes et échangent les deux restantes, donc leurs 6 monômes sont aModèle:IndaModèle:Ind.

L'indicateur de cycles de cette action est donc

$Z(G)=\frac{1}{24}(a_1^6+8a_3^2+9a_1^2{a}_2^2+6a_2{a}_4).$

Groupe de permutations des faces d'un cube

Le groupe des 24 rotations du cube (isomorphe à SModèle:Ind) permute les 8 sommets, les 12 arêtes et les 6 faces de ce cube. Les permutations sur les faces sont :

• l'identité, de monôme indicateur aModèle:IndModèle:6
• les 6 quarts de tour d'axes joignant les centres de deux faces opposées, qui fixent ces deux faces et permutent circulairement les quatre autres, de monômes aModèle:IndModèle:2aModèle:Ind
• les 3 demi-tours de mêmes axes, qui fixent aussi ces deux faces mais échangent 2 à 2 les quatre autres, de monômes aModèle:IndModèle:2aModèle:IndModèle:2
• les 8 tiers de tours d'axes joignant deux sommets opposés, qui permutent circulairement 3 par 3 les six faces, de monômes aModèle:IndModèle:2
• les 6 demi-tours d'axes joignant les milieux de deux arêtes opposées, qui échangent 2 à 2 les six faces, de monômes aModèle:IndModèle:3

L'indicateur de cycles de ce groupe de permutations C est donc

$Z(C)=\frac{1}{24}(a_1^6+6a_1^2{a}_4+3a_1^2{a}_2^2+8a_3^2+6a_2^3).$

Indicateurs de cycles de quelques groupes de permutations

Notons n le « degré » du groupe de permutations G, c'est-à-dire le cardinal de l'ensemble X sur lequel il agit. Le polynôme Z(G) a donc pour variables Modèle:Math.

Groupe trivial EModèle:Ind

Le groupe trivial contient une seule permutation, qui fixe tous les éléments.

$Z(E_n)=a_1^n.$

Groupe cyclique CModèle:Ind

Le groupe cyclique CModèle:Ind est le groupe des rotations d'un polygone régulier à n sommets. Il a φ(d) éléments d'ordre d pour chaque diviseur d de n, où φ(d) est l'indicatrice d'Euler de d, c'est-à-dire le nombre d'entiers strictement positifs inférieurs ou égaux à d et premiers avec d. Dans la représentation régulière de CModèle:Ind, une permutation d'ordre d possède n/d cycles de longueur d, si bien que

$Z(C_n)=\frac{1}{n}\sum _{d|n}\phi (d)a_d^{n/d}.$

Groupe diédral DModèle:Ind

Le groupe diédral contient le groupe cyclique, mais inclut aussi des réflexions. Pour son action naturelle,

$Z(D_n)=\frac{1}{2}Z(C_n)+\{\begin{array}{cc}\frac{1}{2}{a}_1{a}_2^{(n-1)/2}& n\text{ si impair,}\\ \frac{1}{4}(a_1^2{a}_2^{(n-2)/2}+a_2^{n/2})& n\text{ si pair.}\end{array}$

Groupe alterné AModèle:Ind

Le groupe alterné contient les n!/2 permutations paires sur n éléments. Pour son action naturelle,

$Z(A_n)=\sum _{j_1+2j_2+3j_3+\dots +k{j}_k=n}\frac{1+(-1{)}^{j_2+j_4+\dots }}{\prod _{k=1}^n{k}^{j_k}{j}_k!}\prod _{k=1}^n{a}_k^{j_k}.$

Groupe symétrique SModèle:Ind

L'indicateur de cycles du groupe symétrique SModèle:Ind pour son action naturelle est

$Z(S_n)=\sum _{j_1+2j_2+3j_3+\dots +k{j}_k=n}\frac{1}{\prod _{k=1}^n{k}^{j_k}{j}_k!}\prod _{k=1}^n{a}_k^{j_k}.$

Cette formule s'obtient en comptant le nombre de permutations de chaque type (jModèle:Ind, … , jModèle:Ind), en trois étapes : le nombre de partitions de ce type puis, pour chaque partie de taille k d'une telle partition, le nombre k!/k d'Modèle:Lien sur cette partie, puis la prise en compte du fait qu'on ne distingue pas les uns des autres les cycles de même longueur jModèle:Ind, qui sont permutés par SModèle:Ind. Ceci donne bien

$\frac{n!}{\prod _{k=1}^n(k!{)}^{j_k}}\prod _{k=1}^n{\left(\frac{k!}{k}\right)}^{j_k}\prod _{k=1}^n\frac{1}{j_k!}=\frac{n!}{\prod _{k=1}^n{k}^{j_k}{j}_k!}.$

Cet indicateur de cycles de SModèle:Ind se réécrit, en termes de polynômes de Bell complets :

$Z(S_n)=\frac{B_n(0!a_1,1!a_2,\dots ,(n-1)!a_n)}{n!}.$

Il peut aussi se calculer par récurrence, à partir de Z(SModèle:Ind) = 1, par le raisonnement suivant. Pour n > 0, si p (compris entre 1 et n) est la taille du cycle qui contient n, il y a $(\genfrac{}{}{0ex}{}{n-1}{p-1})$ façons de choisir les Modèle:Nobr éléments restants de ce cycle puis p!/p ordres circulaires sur ce cycle, d'où

$Z(S_n)=\frac{1}{n!}\sum _{p=1}^n(\genfrac{}{}{0ex}{}{n-1}{p-1})\frac{p!}{p}{a}_p(n-p)!Z(S_{n-p})=\frac{1}{n}\sum _{p=1}^n{a}_{p}Z(S_{n-p}).$

Applications

L'action naturelle d'un groupe de permutations G, sur un ensemble X de cardinal n, induit, pour tout entier naturel k ≤ n, une action sur l'ensemble des parties de X à k éléments et sur l'ensemble des k-uplets d'éléments de X (cf. exemple ci-dessus pour k = 2). Notons respectivement fModèle:Ind et FModèle:Ind le nombre d'orbites pour ces deux actions. Les séries génératrices correspondantes, qui sont de simples polynômes en une variable de degré n, se calculent par substitution des variables Modèle:Math dans le polynôme Z(G) :

• la série génératrice ordinaire des fModèle:Ind est donnée par$\sum _{k=0}^n{f}_k{t}^k=Z(G)(1+t,1+t^2,\dots ,1+t^n)$
• la série génératrice exponentielle des FModèle:Ind est donnée par$\sum _{k=0}^n{F}_k\frac{t^k}{k!}=Z(G)(1+t,1,1,\dots ,1).$

Pour tout ensemble Y, l'action de G sur X en induit une sur [[Exponentiation ensembliste|l'ensemble YModèle:Exp des applications de X dans Y]], par (g.f)(x) = f(gModèle:Exp.x). Si Y est fini, de cardinal b, le nombre d'orbites de cette action induite est Z(G)(b, b, … ,b). Ce résultat se déduit du lemme de Burnside ou de sa généralisation, le théorème de dénombrement de Pólya.

Ainsi, l'indicateur de cycles est un polynôme en plusieurs variables dont certaines évaluations fournissent des résultats de dénombrement. Ces polynômes peuvent aussi être formellement additionnés, soustraits, dérivés et intégrés. La Modèle:Lien fournit des interprétations combinatoires des résultats de ces opérations.

La question du type de la décomposition en cycles et autres statistiques d'une permutation aléatoire est importante en analyse des algorithmes.

Voir aussi

Liens externes

• Modèle:En Marko Riedel, Pólya's enumeration theorem and the symbolic method, Modèle:Date-
• Modèle:Article

Bibliographie

• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Ouvrage