Indicateur de cycles
# Indicateur de cycles

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_1,$ $a_2,$ … qui décrit le « type » de cette partition, ou « type de cycles » de π : l'exposant de $a_i$ 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 théorie combinatoire des espèces de structures (en).

## Groupes de permutations et actions de groupes

Un groupe de permutations est un sous-groupe du groupe symétrique $S_X$ des bijections d'un ensemble X dans lui-même.

Soient G un groupe et φ un morphisme de groupes de G dans $S_X.$ 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 $a_1,$ $a_2,$ … $a_n$ :

$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 k de 1 à n, $j_k(g)$ est le nombre de k-cycles de la permutation de X associée à g. (Ces entiers naturels vérifient donc $\scriptstyle \sum _{k=1}^{n}kj_{k}(g)=n$.)

## Exemple

La représentation régulière du groupe cyclique $C_4$ 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 $a_1^4,$ $a_4,$ $a_2^2$ et $a_4.$ L'indicateur de cycles de ce groupe de permutations est donc

$Z(C_{4})={\frac {1}{4}}\left(a_{1}^{4}+a_{2}^{2}+2a_{4}\right).$

Le groupe $C_4$ 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 $K_4.$ 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}}\left(a_{1}^{6}+a_{1}^{2}a_{2}^{2}+2a_{2}a_{4}\right).$

On peut aussi faire agir $C_4$ sur les 16 couples de sommets (qui correspondent aux arcs du graphe orienté complet $D_4,$ avec une boucle à chaque sommet). On trouve alors comme indicateur

$Z(C_{4})={\frac {1}{4}}\left(a_{1}^{16}+a_{2}^{8}+2a_{4}^{4}\right).$

## 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}}\left(a_{1}^{3}+3a_{1}a_{2}+2a_{3}\right).$
* 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 représentation régulière du groupe cyclique $C_4.$ Celle du groupe cyclique $C_6$ 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}}\left(a_{1}^{6}+a_{2}^{3}+2a_{3}^{2}+2a_{6}\right).$
* 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 $K_3$ est isomorphe à son graphe adjoint, donc l'action de $S_3$ 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 $K_n$ 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 $S_4$ sur les 4 sommets du graphe complet $K_4$ 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 $C_4$ sur les paires de sommets. Accessoirement, on peut identifier $K_4$ à 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 $a_1^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 à $a_3^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 à $a_1^2a_2^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 $a_1^2a_2^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 $a_2a_4.$

L'indicateur de cycles de cette action est donc

$Z(G)={\frac {1}{24}}\left(a_{1}^{6}+8a_{3}^{2}+9a_{1}^{2}a_{2}^{2}+6a_{2}a_{4}\right).$

### Groupe de permutations des faces d'un cube

Le groupe des 24 rotations du cube (isomorphe à $S_4)$ 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 $a_1^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 $a_1^2a_4$
* les 3 demi-tours de mêmes axes, qui fixent aussi ces deux faces mais échangent 2 à 2 les quatre autres, de monômes $a_1^2a_2^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 $a_3^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 $a_2^3$

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

$Z(C)={\frac {1}{24}}\left(a_{1}^{6}+6a_{1}^{2}a_{4}+3a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}^{3}\right).$

## 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 $a_1,$ $a_2,$ … $a_n.$

### Groupe trivial $E_n$

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

$Z(E_{n})=a_{1}^{n}.$

### Groupe cyclique $C_n$

Le groupe cyclique $C_n$ 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 $C_n,$ 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}\varphi (d)a_{d}^{n/d}.$

### Groupe diédral $D_n$

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{cases}{\frac {1}{2}}a_{1}a_{2}^{(n-1)/2}&n{\mbox{ si impair,}}\\{\frac {1}{4}}\left(a_{1}^{2}a_{2}^{(n-2)/2}+a_{2}^{n/2}\right)&n{\mbox{ si pair.}}\end{cases}}$

### Groupe alterné $A_n$

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}+\ldots +kj_{k}=n}{\frac {1+(-1)^{j_{2}+j_{4}+\ldots }}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k=1}^{n}a_{k}^{j_{k}}.$

### Groupe symétrique $S_n$

L'indicateur de cycles du groupe symétrique $S_n$ pour son action naturelle est

$Z(S_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\ldots +kj_{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 $(j_1,$ … , $j_k),$ 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'ordres circulaires (en) 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 $j_k,$ qui sont permutés par $S_{jk}.$ 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 $S_n$ 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(S_0)$ = 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 $\scriptstyle {n-1 \choose p-1}$ façons de choisir les p – 1 é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}{n-1 \choose 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 $f_k$ et $F_k$ 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 $a_1,$ $a_2,$ … $a_n$ dans le polynôme Z(G) :

* la série génératrice ordinaire des $f_k$ est donnée par$\sum _{k=0}^{n}f_{k}t^{k}=Z(G)(1+t,1+t^{2},\ldots ,1+t^{n})$
* la série génératrice exponentielle des $F_k$ est donnée par$\sum _{k=0}^{n}F_{k}{\frac {t^{k}}{k!}}=Z(G)(1+t,1,1,\ldots ,1).$

Pour tout ensemble Y, l'action de G sur X en induit une sur l'ensemble $Y^X$ des applications de X dans Y, par (g.f)(x) = $f(g^{–1}.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 combinatoire symbolique (en) 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.

