O índice de ciclos de um grupo de permutações



  • Dada uma permutação $ g\in S_n$ seja $ \ell_j(g)=$ número de ciclos de comprimento $ j$ na decomposição de $ g$ em ciclos disjuntos. A uma permutação desse tipo associamos o monómio nas variáveis $ X_1,X_2,\cdots,X_n$:

$\displaystyle X_1^{\ell_1(g)}X_2^{\ell_2(g)} \cdots X_n^{\ell_n(g)}$

  • O índice de ciclos de um grupo de permutações $ G$ é um polinómio que contem toda a informação combinatória àcerca do tipo de ciclos de todos os elementos desse grupo. Define-se por:
$\displaystyle {\bf Z}_G(X_1,X_2,\cdots,X_n)=\frac{1}{\vert G\vert}\sum_{g\in G}\, X_1^{\ell_1(g)}X_2^{\ell_2(g)} \cdots X_n^{\ell_n(g)}$ (11)







Exemplo 1

Índice de ciclos  do grupo das rotações $ C_6$ do hexágono regular:


Elemento Decomposição em ciclos Monómio
$ e$ $ (1)(2)(3)(4)(5)(6)$ $ X_1^6$
$ \rho$ $ (123456)$ $ X_6^1$
$ \rho^2$ $ (135)(246)$ $ X_3^2$
$ \rho^3$ $ (14)(25)(36)$ $ X_2^3$
$ \rho^4$ $ (153)(264)$ $ X_3^2$
$ \rho^5$ $ (165432)$ $ X_6^1$


Portanto o índice de ciclos de $ C_6$ é o polinómio:

$\displaystyle {\bf Z}_{C_6}(X_1,X_2,X_3,X_4,X_5,X_6)=\frac{1}{6}\left( X_1^6 + X_2^3 + 2 X_3^2 + 2X_6 \right)$




Exemplo 2

Índice de ciclos  do grupo diedral $ D_6$ :


Elemento Decomposição em ciclos Monómio
$ e$ $ (1)(2)(3)(4)(5)(6)$ $ X_1^6$
$ \rho$ $ (123456)$ $ X_6^1$
$ \rho^2$ $ (135)(246)$ $ X_3^2$
$ \rho^3$ $ (14)(25)(36)$ $ X_2^3$
$ \rho^4$ $ (153)(264)$ $ X_3^2$
$ \rho^5$ $ (165432)$ $ X_6^1$
$ s_1$ $ (12)(36)(45)$ $ X_2^3$
$ s_2$ $ (16)(25)(34)$ $ X_2^3$
$ s_3$ $ (14)(23)(56)$ $ X_2^3$
$ t_1$ $ (1)(4)(26)(35)$ $ X_1^2X_2^2$
$ t_2$ $ (3)(6)(24)(15)$ $ X_1^2X_2^2$
$ t_3$ $ (2)(5)(13)(46)$ $ X_1^2X_2^2$

Portanto o índice de ciclos de $ D_6$ é o polinómio:
$\displaystyle {\bf Z}_{R_6}(X_1,X_2,X_3,X_4,X_5,X_6)=\frac{1}{6}\left( X_1^6 + 3X_1^2X_2^2 + 4X_2^3 + 2 X_3^2 + 2X_6 \right)$ (13)







Generalizando:

Cálculo do índice de ciclos do grupo diedral $ D_n$


O grupo diedral $ D_n$ , das simetrias de um polígono regular de $ n$ vértices, tem ordem $ 2n$ :

$\displaystyle \vert D_n\vert=2n$

É constituído por $ n$ rotações:

$\displaystyle e,\rho=R_{2\pi/n},\rho^2, \cdots, \rho^{n-1}$
e por $ n$ reflexões relativamente a rectas.
  • Analisemos em primeiro lugar a decomposição em ciclos destas rotações e os respectivos índices de ciclos.


    •

Para cada $ m=0,1,2,\cdots, n-1$ , a rotação $ \rho^m$ quando actua nos vértices $ i=0,1,2,3,\cdots,n-1$ do polígono regular de $ n$ vértices, envia cada vértice $ i$ no vértice $ i+m$ (módulo $ n$ ).

  • Nota ... Há vantagem em usar a numeração $ 0,1,\cdots, para os vértices do polígono para que possamos descrever as transformações geométricas em termos das operações $ +$ e $ \cdot$ no anel $ \mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$ .

Assim por exemplo, quando $ n=6$ e $ m=4$ :


$\displaystyle \rho^4$ $\displaystyle =$ \begin{displaymath}\left(%  
  $\displaystyle =$ \begin{displaymath}\left(%  
  $\displaystyle =$ $\displaystyle (042)(153)$ (14)

Fixemos $ m$ . Se $ k\geq 1$ é o menor inteiro tal que $ km\equiv 0$ (mod $ n$ ), então $ \rho^m$ decompõe-se em $ n/k$ ciclos de comprimento $ k$. Por outro lado, se $ mdc(m,n)=d$ esse inteiro $ k$ não é mais do que $ k=n/d$ e portanto $ \rho^m$ decompõe-se em $ d$ ciclos de comprimento $ k=n/d$ .

Agrupemos as rotações $ \rho^m$ que têm o mesmo tipo de decomposição num produto de ciclos. Para isso recorremos à chamada função $ \phi$ de Euler:


  • Função $ \phi$ de Euler ... Para cada inteiro positivo $ a$ seja $ \phi(a)=$ número de inteiros $ m$ , com $ 1\leq , tais que $ m$ e $ a$ são primos entre si, i.e., $ mdc(m,a)=1$. Eis alguns valores de $ \phi(a)$ :


\begin{displaymath}


Para cada divisor $ d$ de $ n$ existem $ \phi(n/d)$ números $ m$ , entre $ 1$ e $ n$ , tais que $ mdc(m,n)=d$ . Portanto, por cada divisor $ d$ de $ n$ há $ \phi(n/d)$ rotações que contribuem com o monómio $ X_{n/d}^d$ para o índice de ciclos.

A contribuição das $ n$ rotações é pois $ \sum_{d\vert n}\, e, em particular, o índice de ciclos do grupo cíclico $ C_n$ é:

$\displaystyle {\bf Z}_{C_n}(X_1,X_2,\cdots,X_n)=\frac{1}{2n} \sum_{d\vert n}\, \phi(n/d)X_{n/d}^d =\frac{1}{2n} \sum_{d\vert n}\, \phi(d)X^{n/d}_d$ (15)


  • Analisemos agora a contribuição das reflexões para o índice de ciclos do grupo diedral $ D_n$ . Temos que distinguir duas situações:
  • Se $ n$ é ímpar, cada uma destas reflexões decompõe-se num produto de um ciclo de comprimento $ 1$ e $ \frac{n-1}{2}$ ciclos de comprimento $ 2$ . A contribuição total para o índice de ciclos das $ n$ reflexões é pois:

    $\displaystyle n X_1X_2^{\frac{n-1}{2}}$

  • Se $ n$ é par, metade destas reflexões decompõe-se num produto de $ \frac{n}{2}$ ciclos de comprimento $ 2$ e a outra metade num produto de dois ciclos de comprimento $ 1$ e $ \frac{n-2}{2}$ ciclos de comprimento $ 2$ . A contribuição total para o índice de ciclos das $ n$ reflexões é pois, neste caso:

    $\displaystyle \frac{n}{2} X_2^{\frac{n}{2}}+ \frac{n}{2} X_1^2 X_2^{\frac{n-2}{2}}$

Concluindo: O índice de ciclos do grupo diedral $ D_n$ é:

  • Se $ n$ é ímpar:
    $\displaystyle {\bf Z}_{D_n}(X_1,X_2,\cdots,X_n)=\frac{1}{2n} \sum_{d\vert n}\, \phi(d)X^{n/d}_d + \frac{1}{2}X_1X_2^{\frac{n-1}{2}}$ (16)

  • Se $ n$ é par:
    (17)








Em particular, o número de colares com $ n$ pérolas e $ k$ cores é igual a:

$\displaystyle {\bf Z}_{D_n}(k,k,\cdots,k)=\frac{1}{2n} \sum_{d\vert n}\, \phi(d... (18)

e:
$\displaystyle {\bf Z}_{D_n}(k,k,\cdots,k)=\frac{1}{2n} \sum_{d\vert n}\, \phi(d... (19)

Se $ k=2$ cores e $ n$ é um número primo ímpar, o número padrões de colares é:

$\displaystyle \frac{1}{2n}(2^n+2(n-1))+\frac{1}{2}2^{\frac{n+1}{2}}$





Mais exemplos de índices de ciclos:

\begin{displaymath}\begin{array}{lll}




Página seguinte
Página anterior
 Índice