Indicateur de cycles

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 a1, a2, … qui décrit le « type » de cette partition, ou « type de cycles » de π : l'exposant de ai 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[modifier | modifier le code]

Article détaillé : Groupe de permutations.

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

Soient G un groupe et φ un morphisme de groupes de G dans SX. 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[modifier | modifier le code]

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 a1, a2, … an :

Z(G)=\frac1{|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, jk(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}^nkj_k(g)=n.)

Exemple[modifier | modifier le code]

La représentation régulière du groupe cyclique C4 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 a14, a4, a22 et a4. L'indicateur de cycles de ce groupe de permutations est donc

Z(C_4)=\frac14\left(a_1^4+a_2^2+2a_4\right).

Le groupe C4 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 K4. 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)=\frac14\left(a_1^6+a_1^2a_2^2+2a_2a_4\right).

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

Z(C_4)=\frac14\left(a_1^{16}+a_2^8+2a_4^4\right).

Types d'actions[modifier | modifier le code]

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},(2 3),(1 2),(1 2 3),(1 3 2),(1 3)\}
    a pour indicateur de cycles
    Z(S_3)=\frac16\left(a_1^3+3a_1a_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 C4. Celle du groupe cyclique C6 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)=\frac16\left(a_1^6+a_2^3+2a_3^2+2 a_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[modifier | modifier le code]

Le graphe complet K3 est isomorphe à son graphe adjoint, donc l'action de S3 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 Kn a strictement plus d'arêtes que de sommets.

Groupe de permutations des arêtes du graphe complet sur 4 sommets[modifier | modifier le code]

L'action naturelle de S4 sur les 4 sommets du graphe complet K4 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 C4 sur les paires de sommets. Accessoirement, on peut identifier K4 à 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 a16.
  • 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 à a32.
  • 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 à a12a22.
  • 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 a12a22.
  • 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 a2a4.

L'indicateur de cycles de cette action est donc

Z(G)=\frac1{24}\left(a_1^6+8a_3^2+9 a_1^2a_2^2+6a_2a_4\right).

Groupe de permutations des faces d'un cube[modifier | modifier le code]

Le groupe des 24 rotations du cube (isomorphe à S4) 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 a16
  • 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 a12a4
  • les 3 demi-tours de mêmes axes, qui fixent aussi ces deux faces mais échangent 2 à 2 les quatre autres, de monômes a12a22
  • les 8 tiers de tours d'axes joignant deux sommets opposés, qui permutent circulairement 3 par 3 les six faces, de monômes a32
  • 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 a23

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

Z(C)=\frac1{24}\left(a_1^6+6a_1^2a_4+3a_1^2a_2^2+8a_3^2+6 a_2^3\right).

Indicateurs de cycles de quelques groupes de permutations[modifier | modifier le code]

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 a1, a2, … an.

Groupe trivial En[modifier | modifier le code]

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

Z(E_n)=a_1^n.

Groupe cyclique Cn[modifier | modifier le code]

Le groupe cyclique Cn 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 Cn, une permutation d'ordre d possède n/d cycles de longueur d, si bien que [5]

Z(C_n)=\frac1n\sum_{d|n}\varphi(d)a_d^{n/d}.

Groupe diédral Dn[modifier | modifier le code]

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

Z(D_n)=\frac12Z(C_n)+
\begin{cases}
\frac12a_1a_2^{(n-1)/2}&n\mbox{ si impair,}\\ 
\frac14
\left(a_1^2a_2^{(n-2)/2}+a_2^{n/2}\right)&n\mbox{ si pair.}
\end{cases}

Groupe alterné An[modifier | modifier le code]

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}^nk^{j_k}j_k!}\prod_{k=1}^na_k^{j_k}.

Groupe symétrique Sn[modifier | modifier le code]

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

Z(S_n)=\sum_{j_1+2j_2+3j_3+\ldots+k j_k=n}\frac1{\prod_{k=1}^nk^{j_k}j_k!}\prod_{k=1}^na_k^{j_k}.

Cette formule s'obtient en comptant le nombre de permutations de chaque type (j1, … , jk), 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 jk, qui sont permutés par Sjk. 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\frac1{j_k!}
=
\frac{n!}{\prod_{k=1}^nk^{j_k}j_k!}.

Cet indicateur de cycles de Sn 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(S0) = 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)=\frac1{n!}\sum_{p=1}^n{n-1\choose p-1}~\frac{p!}p~a_p~(n-p)!~Z(S_{n-p})=\frac1n\sum_{p=1}^n a_p~Z(S_{n-p}).

Applications[modifier | modifier le code]

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 fk et Fk 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 a1, a2, … an dans le polynôme Z(G)[6] :

  • la série génératrice ordinaire des fk est donnée par
    \sum_{k=0}^nf_kt^k=Z(G)(1+t,1+t^2,\ldots,1+t^n)
  • la série génératrice exponentielle des Fk est donnée par
    \sum_{k=0}^nF_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 YX 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[modifier | modifier le code]

(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 (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 » (no 163),‎ 1996 (ISBN 978-0-387-94599-6, lire en ligne), chap. 1.2 (« Symmetric groups »), p. 2
  5. (en) J. H. van Lint (de) et R. M. Wilson (de), A Course in Combinatorics, CUP,‎ 1992 (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[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]