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₁, a₂, … 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 »^[1].

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)^[2].)

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₁, a₂, … a_n :

${\displaystyle 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 ${\displaystyle \scriptstyle \sum _{k=1}^{n}kj_{k}(g)=n}$.)

Exemple

La représentation régulière du groupe cyclique C₄ 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₁⁴, a₄, a₂² et a₄. L'indicateur de cycles de ce groupe de permutations est donc

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

Le groupe C₄ 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₄. 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

${\displaystyle 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₄ sur les 16 couples de sommets (qui correspondent aux arcs du graphe orienté complet D₄, avec une boucle à chaque sommet). On trouve alors comme indicateur

${\displaystyle 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${\displaystyle S_{3}=\{{\text{id}},(23),(12),(123),(132),(13)\}}$a pour indicateur de cycles${\displaystyle 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^[3].
  On a déjà vu l'exemple de la représentation régulière du groupe cyclique C₄. Celle du groupe cyclique C₆ 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${\displaystyle 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₃ est isomorphe à son graphe adjoint, donc l'action de S₃ 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₄ sur les 4 sommets du graphe complet K₄ 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₄ sur les paires de sommets. Accessoirement, on peut identifier K₄ à 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₁⁶.
• 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₃².
• 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₁²a₂².
• 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₁²a₂².
• 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₂a₄.

L'indicateur de cycles de cette action est donc

${\displaystyle 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₄) 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₁⁶
• 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₁²a₄
• 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₁²a₂²
• 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₃²
• 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₂³

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

${\displaystyle 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é »^[4] 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₁, a₂, … a_n.

Groupe trivial E_n

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

${\displaystyle 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 ^[5]

${\displaystyle 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,

${\displaystyle 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,

${\displaystyle 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

${\displaystyle 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₁, … , 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

${\displaystyle {\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 :

${\displaystyle 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₀) = 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 ${\displaystyle \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ù

${\displaystyle 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₁, a₂, … a_n dans le polynôme Z(G)^[6] :

• la série génératrice ordinaire des f_k est donnée par${\displaystyle \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${\displaystyle \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)^[7]. 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.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cycle index » (voir la liste des auteurs).

1. (en) Peter J. Cameron, Combinatorics : Topics, Techniques, Algorithms, CUP, 1994, 355 p. (ISBN 978-0-521-45761-3, lire en ligne), p. 227-228
2. Cameron 1994, p. 231, section 14.3
3. C'est elle qui induit la représentation régulière (linéaire) du groupe.
4. (en) John D. Dixon et Brian Mortimer, Permutation Groups, Springer, coll. « GTM » (n^o 163), 1996, 348 p. (ISBN 978-0-387-94599-6, lire en ligne), chap. 1.2 (« Symmetric groups »), p. 2
5. (en) J. H. van Lint et R. M. Wilson, A Course in Combinatorics, CUP, 1992, 530 p. (ISBN 978-0-521-42260-4), p. 464, Example 35.1
6. Cameron 1994, p. 248, Proposition 15.3.1
7. van Lint et Wilson 1992, p. 463, Theorem 35.1

Voir aussi

Liens externes

• (en) Marko Riedel, Pólya's enumeration theorem and the symbolic method, novembre 2009
• (en) Harald Fripertinger, « Cycle indices of linear, affine and projective groups », Linear Algebra and its Applications, vol. 263,‎ 1997, p. 133-156 (lire en ligne)

Bibliographie

• (en) Richard A. Brualdi, Introductory Combinatorics, Prentice Hall, 2010, 5^e éd., 605 p. (ISBN 978-0-13-602040-0), chap. 14 (« Pólya Counting »), p. 541-575
• (en) Fred S. Roberts (en) et Barry Tesman, Applied Combinatorics, CRC Press, 2009, 2^e éd., 848 p. (ISBN 978-1-4200-9982-9, lire en ligne), chap. 8.5 (« The Cycle Index »), p. 472-479
• (en) Alan Tucker, Applied Combinatorics, Wiley, 1995, 3^e éd., 462 p. (ISBN 0-471-59504-7), chap. 9.3 (« The Cycle Index »), p. 365-371