Ações de Grupos Finitos e Problemas de Contagem
Clauciane Dias de Lima, UFPR
orientador: Marcelo M.S. Alves
Em teoria de grupos, temos o estudo da ação de um grupo em um conjunto, onde se considera um conjunto X não vazio e um grupo G qualquer.
Uma ação (à esquerda) de G em X é uma tranformação φ : G × X 7→ X,
indicada por φ(g, x) = g · x, satisfazendo os seguintes Axiomas:
(A1 ) Para todo x ∈ X temos e · x = x
(A2 ) Para todo x ∈ X e para todo g, h ∈ G temos (gh) · x = g · (h · x).
De modo equivalente, sendo SX o grupo das bijeções de X, uma ação
de G em X é um homomorfismo de grupos ϕ : G → SX , e a ação no
sentido anterior é dada por g · x = ϕ(g)(x). Diremos também que X é um
G-conjunto. Dado x ∈ X, sua órbita sob a ação de G é denotada por G(x)
e é definida por G(x) = {g · x; g ∈ G}. O conjunto Gx = {g ∈ G|g · x = x}
dos elementos de G que fixam x é um subgrupo de G que é chamado de
subgrupo de isotropia ou estabilizador de x. Se G é finito, temos
um primeiro teorema de contagem, conhecido como teorema da órbita e
estabilizador:
Teorema 1. Se o grupo finito G age no conjunto finito X, então
|G| = |G(x)||Gx |
para cada x ∈ X.
Esse resultado conta o número de elementos em cada órbita. Em particular, o número de elementos de X em cada órbita é um divisor da ordem
de |G|.
Um segundo resultado importante, que tem várias aplicações a problemas
de contagem, diz respeito ao número de órbitas em uma ação e é o teorema
de Burnside.
Teorema 2. Seja G um grupo que age num conjunto X (ambos finitos),
então o número de órbitas de X é dado por:
1 X
N=
F ix(τ )
|G|
τ ∈G
1
onde Fix(τ ) é o número de x ∈ X que são fixados por τ .
No entanto, este resultado não nos exibe informações sobre as órbitas.
Para fazer esse complemento, apresentaremos um método algébrico para descrever colorações de conjuntos, utilizando funções geradoras, onde o objetivo
é obter uma função geradora que determine o número de padrões (órbitas)
distintos para cada situação apresentada. Para poder listar efetivamente
estas órbitas, usaremos as seguintes definições:
Definição 1. Se um grupo G age em X = {1, 2, . . . , n} e se C é um conjunto
de q cores, então a ação G no conjunto C n de todas as n-uplas de cores é :
τ (c1 , . . . , cn ) = (cτ1 , cτ2 , . . . , cτn )
para todos τ ∈ G e c = (c1 , . . . , cn ) ∈ C n . Uma órbita de (c1 , . . . , cn ) ∈ Cn
é chamada de (q − G) coloração de X.
Definição 2. Se G é um grupo de permutações de n elementos, o ı́ndice
de ciclos de G, denotado por Z(G), é definido como sendo o polinômio
multivariado que é a soma de estruturas de ciclo de todas as permutações
em G:
1 X b1 (g) b2 (g)
Pg (X1 , X2 , · · · , Xn ) =
X1 X2
· · · Xnbn (g)
|G|
g∈G
onde bi (g) é o número de ciclos de comprimento i na decomposição cı́clica
completa de g.
Definição 3. Uma função peso ω no conjunto C é qualquer função ω : C →
A, onde A é uma Q-álgebra comutativa. O peso de um elemento c ∈ C é
ω(c).
Definição 4. Sejam D e C conjuntos finitos, e seja ω : C → A uma função
peso fixada. Como os pesos podem ser adicionados, podemos tomar a soma
de todos os pesos, que será chamada de chamaremos armazenador de C:
X
Armazenador C =
ω (c)
c∈C
Portanto o armazenador representa de maneira algébrica todos os valores
que os elementos do conjunto D podem receber através das colorações de D
em C.
Definição 5. Consideramos os conjuntos D e C e o conjunto de todas as
funções F(D, C) de D em C. Então, para cada função f ∈ F(D, C), definimos
seu peso W (f ) pela equação:
2
W (f )=
Y
ω (f (d))
d∈D
Definição 6. Uma lista de um conjunto X ⊂ F(D, C) de funções que
chamaremos de inventário é a soma dos seus pesos.
X
inventário do conjunto X de funções =
W (f )
f ∈X
Para poder construir o resultado mais importante deste trabalho, precisamos de mais uma definição para as c
Definição 7. Sejam D e C conjuntos finitos, onde G é um grupo que age
em D, e seja A uma Q-álgebra comutativa onde temos uma função (isto é,
um peso) ω : C → A. Diremos que duas funções f1 e f2 de D em C são
equivalentes se existir um g ∈ G tal que f1 = f2 ◦ g −1 .
No contexto acima, o grupo G age em F(D, C) por g · f = f ◦ g −1 , e duas
funções são equivalentes se e somente se estão na mesma órbita. As órbitas
de F(D, C) sob a ação de GY
são chamadas de padrões, e a cada padrão F
é associado o peso W(F)=
ω (f (d)), onde f é um elemento qualquer da
d∈D
órbita F . O peso do padrão está bem definido, pois funções equivalentes têm
o mesmo peso. O inventário dos padrões é a soma dos pesos de todos os
padrões.
Teorema 3 (Polya). Sejam D e C conjuntos finitos, onde G um grupo
finito agindo em D, e ω : C → A um peso. Entao o inventário dos padrões
é dado por:
!
X
X
X
ω (c) ,
ω (c)2 ,
ω (c)3 · · ·
PG
c∈C
c∈C
c∈C
onde Pg (X1 , X2 , · · · ) é o ı́ndice de ciclos de G.
Esse teorema fornece a função geradora contendo as informações sobre as
órbitas das colorações. Mostraremos aplicações deste resultado a problemas
concretos de contagens de padrões.
Referências
1. J.J. Rotman, Advanced Modern Algebra, AMS.
2. J. H. van Lint, R.M. Wilson, A course in Combinatorics, Cambridge.
3