1

O Teorema de Burnside e Aplicações

José Plínio O. Santos

e
Eduardo Bovo

Universidade Estadual de Campinas

1
1 - Permutações
Introduzimos, nesta seção, o conceito fundamental de permutação que servirá de base para todo nosso
estudo.
Com a nalidade de sermos concisos, denotamos, para todo n 2 N, o conjunto nito f1; 2; :::; ng pelo
símbolo [n].

De nição 1.1 Dado um conjunto não-vazio X, uma bijeção : X ! X é denominada uma permutação
do conjunto X.

Exemplo 1.1 Considere um baralho de 52 cartas em certa ordem (b1 ; b2 ; :::; b52 ). Qualquer embaral-
hamento de X = (b1 ; :::; b52 ) é perfeitamente descrito por uma reindexação conveniente de seus indices
(bj1 ; :::; bj52 ), com fj1 ; :::; j52 g = [52] = f1; 2; 3; :::; 52g. Qualquer embaralhamento das cartas possui uma
ordem, geralmente diferente da anterior, se bem embaralhado, digamos (b10 ; b12 ; b1 ; b6 ; :::; b34 ) mas ainda
é composto das mesmas cartas fb1 ; :::; b52 g.
Assim podemos pensar no embaralhamento como uma permutação do conjunto X = fb1 ; :::; b52 g das
52 cartas do baralho.

Denotamos o conjunto S (X) como o conjunto de todas as permutações do conjunto X. Se X é nito

com #X = n, isto é, X = fx1 ; :::; xn g, então para formar qualquer permutação destes n elementos, temos

n n 1 ::: 2 1

n possibilidades de preenchimento para o primeiro quadrado da la, n 1 possibilidades para o

segundo, ..., 2 possiblidades para o (n 1)-ésimo e 1 para o enésimo (último).
Assim, pelo princípio multiplicativo temos n! permutações em S (X), isto é, #S (X) = n!.
Na maioria dos casos, estaremos mais interessados em estudar permutações de X = [n] e denotamos
Sn = S ([n]).
Se 2 Sn e j 2 [n], a notação (j) denota o valor da função bijetiva no ponto j. Desta forma
podemos denotar a permutação pelo seguinte diagrama

1 ::: n
=
(1) ::: (n)

exibindo visualmente o domínio e o contradomínio da bijeção considerada.

1 2 3 4 5 6 7 8
Exemplo 1.2 = 2 S8 . Observe que após aplicada esta permutação, os
1 5 2 4 6 3 8 7
números 1 e 4 permanecem xos.

A segunda representação, muito importante para nós, é a representação por ciclos. Antes de introduzi-la,

2
é conveniente olharmos o exemplo acima por diagrama de setas
1!1
2!5
3!2 1!1
4!4 2!5!6!3!2
que é equivalente a e que iremos denotar por (1) (2563) (4) (78)
5!6 4!4
6!3 7!8!7
7!8
8!7
De maneira geral, se 2 Sn , para todo j 2 [n] temos que deve existir lj 2 [n] tal que
lj
(j) = ( ( (::: ( (j)) :::))) = j
| {z }
lj aplicações
Se não existisse tal lj , ou lj n + 1, então após a n-ésima iteração teríamos o valor resultante fora do
conjunto [n], um absurdo pois é uma bijeção de nida em [n]. Assim, temos um ciclo de determinado
por j; (j) ; 2 (j) :::; lj 1 (j) de comprimento lj . Tomamos um outro elemento k não contido no
ciclo j; (j) ; 2 (j) :::; lj 1 (j) e temos que deve existir lk tal que k; (k) ; 2 (k) :::; lk 1 (k) seja
um ciclo de comprimento lk . Aplicamos este procedimento sucessivamente aos elementos que ainda não
tenham aparecido nos ciclos anteriormente construídos até que todos os membros de [n] sejam utilizados.
Desta forma obtemos uma representação da permutação por meio de ciclos disjuntos. Denominamos um
ciclo de comprimento k simplesmente de k-ciclo; se k = 1 dizemos que o ciclo é um ponto xo e se k = 2
dizemos que o ciclo é uma transposição.

1 2 3 4 5 6
Exemplo 1.3 A permutação pode ser representada na notação de ciclos disjuntos
2 1 3 6 4 5
por (12) (3) (465). O ciclo (12) é uma transposição e o ciclo (3) é um ponto xo da permutação.

Observe que se permutarmos ciclicamente os elementos de um ciclo qualquer, ou se reordenarmos os

ciclos isto não mudará a permutação representada. A menos destas possíveis variações, a representação
por ciclos disjuntos é única.
É costume omitir da composição de permutações o símbolo , e simplesmente justapor os operandos.
Assim 1 2 é denotada por 1 2 , onde entendemos que primeiro aplicamos 2 e depois 1 .

2 - Grupos de Permutações
A seguir demonstramos alguns lemas elementares que versam sobre S (X), e provamos que se trata na
verdade de um grupo com a operação de composição de funções.
2.1 S (X) é um grupo de permutações
Consideramos nos resultados abaixo que X é um conjunto não-vazio qualquer, mas podemos te-lo em
mente como sendo o conjunto [n].

Lema 2.1 O conjunto S (X) é fechado por composição de permutações, isto é,

1; 2 2 S (X) ) 1 2 2 S (X)

3
Dem. Dadas 1 ; 2 2 S (X), mostramos que 1 2 é também uma bijeção de X em X, e portanto pertence
a S (X).
1 2 é injetiva. De fato, se tomarmos x; y 2 X; x 6= y, como 2 é injetiva segue que 2 (x) 6= 2 (y).
Assim, como 1 é injetiva também, segue que 1 2 (x) 6= 1 2 (y) e portanto 1 2 é também injetiva.
Mostramos agora que 1 2 é sobrejetiva e para isso seja z 2 X. Como 1 e 2 são sobrejetivas, 9y 2 X
com 1 (y) = z, 9x 2 X com 2 (x) = y. Isto é, existe x 2 X tal que 1 ( 2 (x)) = z e portanto 1 2 é
sobrejetiva.
Assim concluímos que 1 2 2 S (X), e o conjunto é fechado por composição de permutações.

Lema 2.2 A função e : X ! X de nida por e (x) = x para todo x 2 X é uma bijeção e funciona como
a identidade de S (X), isto é
8 2 S (X) , temos e = e =
Além disso, dada qualquer permutação 2 S (X), existe uma permutação inversa 1 2 S (X) tal que
1 1
= =e

Dem. É imediato veri car que a função e (x) identidade é uma permutação e que funciona como elemento
neutro de S (X). Como toda função bijetiva possui inversa, e esta inversa também é bijetiva, segue a
existência dos inversos em S (X).
Sabemos que a composição de funções é associativa o que nos permite concluir diretamente, pela
de nição de operação que demos em S (X), que

Lema 2.3 Dadas as permutações 1; 2 e 3 em S (X), temos

1 ( 2 3) =( 1 2) 3

Esses três lemas acima mostram que S (X) é um grupo com a operação de composição de funções.
Na próxima seção, relembramos as de nições dos axiomas de grupo e demonstramos alguns resultados
fundamentais.
2.2 Axiomas de Grupo
Uma operação binária em um conjunto G é entendida como uma função : G G ! G que associa
a cada par de elementos de G, um elemento de G. Desta forma, se uma tal operação binária puder ser
de nida em G, teremos que obrigatoriamente G é fechado por ela. Assim o conceito de o conjunto G ser
fechado pela operação está implícito no conceito de operação binária em G.

De nição 2.1 Um grupo é um par ordenado (G; ), onde G é um conjunto e é uma operação binária em
G satisfazendo:
(G1) Identidade: Existe e 2 G tal que 8x 2 G ) x e = e x = x
O elemento e é chamado de identidade de G.
(G2) Inversos: 8x 2 G, existe x 1 2 G tal que x x 1 = x 1 x = e
Dado x, o elemento x 1 é chamado de inverso de x.
(G3) Associatividade: 8x; y; z 2 G, temos x (y z) = (x y) z

4
 A associatividade nos permite abandonar os parênteses na composição de operações entre elementos de
G.

Temos então o seguinte teorema, que é conseqüência dos lemas da seção anterior:

Teorema 2.1 Se X é um conjunto não-vazio, (S (X) ; ) é um grupo chamado de grupo de permutações

de X, e denotado simplesmente por S (X).

Exemplo 2.1 Como exemplos básicos, temos que os seguintes pares são grupos:
(Z; +) ; (Q; +) ; (R; +) ; (C; +)

Exemplo 2.2 Todos os conjuntos do exemplo acima são fechados por multiplicação, tendo 1 como identi-
dade. No entanto, apenas os elementos não-nulos dos conjuntos Q, R e C possuem inversos. Assim temos
mais três exemplos de grupos,
(Q ; ) ; (R ; ) ; (C ; )

Exemplo 2.3 Seja p um primo, Zp = 0; 1; :::; p 1 a classe dos resíduos módulo p. Então (Zp ; +p ) e
Zp ; p são grupos com as operações de soma e multiplicação módulo p, respectivamente.

Exemplo 2.4 O grupo simétrico Sn , formado pelas permutações dos símbolos f1; 2; :::; ng.

2.3 Subgrupos e o Teorema de Lagrange

A seguir apresentamos a de nição de subgrupo de um grupo G. Essencialmente, entendemos por um
subgrupo H de G, um subconjunto H de G tal que H se comporte como um grupo pela operação herdada
da de nida em G.
Como H G, consideramos como operação binária em H a restrição de ao domínio H H. Pelo
fato de a associatividade ser válida para todos os elementos de G, em particular é válida para todos os
elementos de H, H G.

De nição 2.2 Dado um grupo G e H G, H é um subgrupo de G se

(SG1) H é fechado sob a operação , isto é, 8x; y 2 H ) x y 2 H
(SG2) H contém o elemento identidade e de G.
(SG3) H contém inversos, isto é, 8x 2 H temos x 1 2 H

As condições da de nição acima são equivalentes a uma mais concisa, que é dada na proposição abaixo

Proposição 2.1 Se G é um grupo e H 6= ; é um subconjunto de G, então

H é subgrupo de G () 8g; h 2 H temos g h 1
2 H.

5
 A partir de agora, omitimos, como de costume o símbolo da operação do grupo G e simplesmente
justapomos os elementos sendo operados, como na notação multiplicativa, onde xy signi ca x y.
Vamos de nir alguns conceitos que nos serão úteis na demonstração do Teorema de Lagrange.

De nição 2.3 Seja G um grupo e H um subgrupo de G. Para cada g 2 G, a classe lateral gH é de nida
como sendo o conjunto
gH = fgh : h 2 Hg

Lema 2.4 Se H é um subgrupo de G, e g1 ; g2 2 G, então temos

g1 H = g2 H () g2 1 g1 2 H

Dem. Supomos primeiramente que g1 H = g2 H. Como a identidade e 2 H, temos

g1 e = g1 2 (g1 H) ) g1 2 (g2 H)
Assim, existe h 2 H tal que g1 = g2 h, o que equivale a g2 1 g1 = h, e portanto g2 1 g1 2 H.
Agora supomos que g2 1 g1 2 H. Disto tiramos que g2 1 g1 = h 2 H, ou seja, que g1 = g2 h.
Vamos mostrar que g1 H g2 H. Seja x 2 g1 H, isto é, x = g1 h1 para algum h1 2 H. Temos
x = g1 h1 = (g2 h) h1 = g2 (hh1 ) = g2 h2 com h2 2 H, pois H é subgrupo de G
Desta forma temos que x 2 g2 H e portanto g1 H g2 H.
Reescrevemos a equação g1 = g2 h utilizando o inverso de h em H, obtendo g2 = g1 h 1 (lembre-se que
H é subgrupo de G , e portanto h 1 2 H). Assim podemos aplicar o raciocínio anterior para mostrar que
g2 H g1 H. Portanto temos a igualdade g1 H = g2 H.

Lema 2.5 Se H é um subgrupo de G então quaisquer classes laterais de H ou são idênticas, ou são
disjuntas. Em símbolos:
8g1 ; g2 2 H, temos exclusivamente que g1 H = g2 H ou g1 H \ g2 H = ;.

Dem. Suponha que g1 H \ g2 H 6= ; e seja x 2 g1 H \ g2 H. Então existem h1 ; h2 2 H tais que

x = g1 h1 = g2 h2 , o que signi ca que g2 1 g1 = h2 h1 1 . Mas h2 h1 1 2 H, pois H é subgrupo de G, o que
implica que g2 1 g1 2 H e assim pelo lema 2.4 temos g1 H = g2 H.

De nição 2.4 Em vista do lema anterior, de nimos como índice de H em G o número de diferentes
classes laterais de H em G, e denotamos por jG : Hj. Em símbolos,
jG : Hj = # fgH : g 2 Gg

Agora temos as ferramentas necessárias para a demonstração do importante Teorema de Lagrange,

acerca da ordem de subgrupos de G.

Teorema 2.2 Se H é um subgrupo de um grupo nito G, então

jG : Hj jHj = jGj

6
Dem. Como H é subgrupo de G, a identidade e está em H. Portanto, para cada g 2 G, g = ge 2 gH, e
assim cada elemento de G está em alguma classe lateral de H em G.
Mostramos agora que cada classe lateral de H em G possui ordem igual à ordem de H. Como H G e
H é subgrupo, temos que jHj < 1. Seja H = fh1 ; :::; hm g com os hj todos distintos (isto é, jHj = m).
A rmamos que para todo g 2 G, ghj são todos distintos com j percorrendo os valores 1; :::; m. De fato, se
tivéssemos ghj = ghk com j 6= k, poderíamos cancelar g à esquerda e obter hj = hk , um absurdo. Assim
concluimos que para qualquer classe lateral gH, jgHj = jHj.
Portanto, utilizando o lema 2.5 temos que as diferentes classes laterais de H em G particionam G em
jG : Hj conjuntos de cardinalidade jHj e concluímos nossa demonstração.
Assim obtemos o importante

Teorema 2.3 (Teorema de Lagrange) Se H é subgrupo de um grupo nito G, então a ordem de H divide
a ordem de G.

Dem. Como G e H são grupos nitos, os números jG : Hj, jHj e jGj são inteiros positivos. Portanto, pela
de nição de divisibilidade e pela equação do teorema anterior, temos que jGj é divisível por jHj.

3 - Grupos de Simetria
A seguir de nimos o que se entenderá por simetria de guras planas ou espaciais.

De nição 3.1 Entendemos por uma …gura um conjunto F de pontos de R2 ou R3 .

De nição 3.2 Dada uma gura F , uma simetria de F é uma aplicação f : F ! F com as seguintes
propriedades
(i) f é uma isometria
(ii) f é sobrejetiva

Pela de nição dada, uma simetria é uma aplicação que leva a gura nela mesma e que preserva
distâncias.

Exemplo 3.1 Um triângulo equilátero possui 6 simetrias: 1 delas é a identidade, 2 são rotações horárias
centradas em seu centro de gravidade de ângulos 23 e 43 e 3 delas são re exões através de suas medianas.

Exemplo 3.2 Um quadrado desenhado no plano possui 8 simetrias: 1 delas é a identidade, 3 são rotações
horárias centradas em seu centro de gravidade de ângulos 2 , e 32 , 2 são re exões através de suas
mediatrizes e 2 são re exões através de suas diagonais.

Podemos utilizar números para marcar as guras e assim relacionar os grupos de simetrias a grupos de
permutações. Fazemos isso comumente associando números aos vértices de guras, mas de uma maneira
geral podemos também associar números a lados, diagonais, ou outros elementos das guras.

7
 Na Figura 1 abaixo, estão listadas as 6 simetrias do triângulo e as 8 do quadrado, bem como as
permutações correspondentes de seus vértices numerados. Também denominamos as simetrias do
quadrado para referência futura.
TRIÂNGULO QUADRADO
SIMETRIA RESULTADO PERMUTAÇÃO SIMETRIA RESULTADO PERMUTAÇÃO
e e
1 1
1 2 1 2
(1)(2)(3) e = (1)(2)(3)(4)
3 4 3 4
2 3 2 3 /2
/3
1 2 3 1
1 2 a1 = (1243)
3 4 4 2
(132)
2 3 3 1
1 2 4 3
/3 a2 = (14)(23)
3 4 2 1
1 3
/2
(123)
1 2 2 4
2 3 1 2 a3 = (1342)
3 4 1 3

1 1
(1)(23) 1 2 2 1
p1 = (12)(34)
3 4 4 3
2 3 3 2

1 3 1 2 3 4
p2 = (13)(24)
(13)(2) 3 4 1 2

2 3 2 1
1 2 1 3
q1 = (1)(23)(4)
1 2 3 4 2 4
1
(12)(3)
2 3 1 3 1 2 4 2
q2 = (14)(2)(3)
3 4 3 1

Figura 1: Simetrias do triângulo e do quadrado

Teorema 3.1 Seja F uma gura. Então o conjunto de todas as simetrias de F , com a operação de com-
posição de funções, forma um grupo.

Dem. Seja G o conjunto de todas as simetrias de F . Veri camos a seguir que G munido da operação de

8
composição de funções satisfaz os axiomas de grupo.
A identidade IF : F ! F é obviamente uma simetria, e portanto G possui um elemento identidade.
Denotando por d (x; y) a distância entre os pontos x e y, suponha que f; g 2 G. Inicialmente, temos que
f g é uma isometria, pois
d (f (g (x)) ; f (g (y))) = d (g (x) ; g (y)) , pois f é uma isometria
= d (x; y) , pois g é uma isometria
Como (f g) (F ) = f (g (F )) = f (F ) = F , e f g é uma isometria, segue então que f g é uma
simetria e portanto está em G.
Toda simetria (isometria) f é injetora, e portanto possui uma inversa f 1 : Dados z; w 2 F , como f é
sobrejetiva também,
1 1 1 1
d f (z) ; f (w) = d f f (z) ; f f (w) = d (z; w)
Assim f é uma simetria e portanto pertence a G.
1

A associatividade da composição de simetrias segue diretamente da associatividade de composição de

funções.

Exemplo 3.3 Temos 3 diferentes tipos de eixos de rotação para um cubo, indicados na gura abaixo:

(a) (b) (c)

(a) Rotação em torno de um eixo que passa pelos centros de faces opostas,
(b) Rotação em torno de um eixo que passa pelos pontos médios de arestas opostas
(c) Rotação em torno de um eixo que passa por vértices opostos
Assim, as 24 simetrias rotacionais de um cubo são divididas em:
1) A identidade e;
2) 3 rotações de um ângulo de 2 pelo eixo indicado em (a);
3) 3 rotações de um ângulo de pelo eixo indicado em (a);
4) 3 rotações de um ângulo de 32 pelo eixo indicado em (a);
5) 6 rotações de um ângulo de pelo eixo indicado em (b);
6) 4 rotações de um ângulo de 23 pelo eixo indicado em (c) e
7) 4 rotações de um ângulo de 43 pelo eixo indicado em (c).

9
4 - Ordens de Permutações
4.1 Tipo cíclico e partições de inteiros
Pelas observações que zemos anteriormente, uma permutação 2 Sn possui a seguinte representação por
t = t ( ) ciclos disjuntos,
(1) (1) (1) (2) (2) (2) (t) (t) (t)
= j1 j2 :::jl1 j1 j2 :::jl2 ::: j1 j2 :::jlt
com t 2 N, [n] particionado pela seguinte reunião disjunta
t n
[ o
(i) (i)
[n] = j1 ; :::; jli
i=1

Sabemos que esta representação é única a menos de permutações dos ciclos e de permutações cíclicas
dos elementos internos de cada ciclo.
Sendo G um grupo nito, a ordem de um elemento g é de nida como o menor inteiro positivo k tal que
g k = e. Isto implica que para qualquer múltiplo m = rk de k, tambem temos a equação g m = e.
Portanto, uma permutação que seja um k-ciclo possui ordem k e este k-ciclo elevado a qualquer
múltiplo de k também resulta na identidade. Como os ciclos da representação de são disjuntos, para todo
k2N
k k k
k (1) (1) (1) (2) (2) (2) (t) (t) (t)
= j1 j2 :::jl1 j1 j2 :::jl2 ::: j1 j2 :::jlt
Assim para encontrarmos a ordem de , precisamos que todos os ciclos de sua representação, quando
elevados a k, atinjam a identidade, o que ocorrerá quando k for um múltiplo comum de l1 ; :::; lt . Mas pela
de nição de ordem de um elemento, queremos o menor k que seja um múltiplo comum. Temos então que
a ordem de é igual a mmc [l1 ; :::; lt ].
De nimos agora um termo polinomial que de certa forma re ete a estrutura cíclica de uma permutação
2 Sn .

De nição 4.1 De nimos o tipo cíclico de 2 Sn como sendo o monômio T C ( ) dado por
Y
t
TC ( ) = x li (1)
i=1

1 2 3 4 5 6
Exemplo 4.1 = = (12) (3) (465) tem tipo cíclico T C ( ) =
2 1 3 6 4 5
x2 x1 x3 = x1 x2 x3 . Repare que a comutatividade do produto em T C ( ) expressa a propriedade de que
a ordem dos ciclos na representação de é irrelevante.

Exemplo 4.2 = (1) (276) (3) (4589) 2 S9 tem tipo cíclico T C ( ) = x1 x3 x1 x4 = x21 x3 x4 .

É costume omitir da representação de os ciclos unitários, porém é fundamental para a determinação do

tipo cíclico de uma permutação, que os ciclos unitários não sejam "esquecidos". Desta forma, ou devemos
logo listar os ciclos unitários, ou ter em mente o grupo subjacente ao qual a permutação analisada pertence.

10
 Observe que na representação (1) podemos ter ciclos disjuntos de mesmo comprimento. Assim
os números l1 ; :::; lt podem não ser todos distintos. Suponha, sem perda de generalidade, que no
conjunto fl1 ; :::; lt g tenhamos apenas s t números distintos, e os redenominamos na ordem crescente
l1 < l2 < ::: < ls . Consequentemente, podemos a rmar que existem k1 ciclos de comprimento l1 , k2 ciclos
de comprimento l2 , ...., ks ciclos de comprimento ls ; onde kj ; lj 2 [n] para j = 1; 2; :::; s. Desta forma,
podemos concluir que para toda 2 Sn xada, temos a unicidade dos números s ( ) ; kj ( ) e lj ( ), onde
j = 1; 2; :::; s.
Assim o tipo cíclico de toma a seguinte forma, mais intuitiva e explícita,

T C ( ) = xkl11 xkl22 :::xklss

onde kj é o número de ciclos de comprimento lj para j = 1; :::; s. Aqui o total de ciclos da representação
é k1 + k2 + ::: + ks .
Como 2 Sn é uma permutação dos números de [n], devemos ter n símbolos distribuídos entre
todos os ciclos de sua representação. Isto implica que k1 l1 + k2 l2 ::: + ks ls = n, e pela ordenação
1 l1 < l2 < ::: < ls n , e de nições de kj , temos então uma partição do inteiro n = k1 l1 + ::: + ks ls .
Reciprocamente, se temos uma partição do inteiro n dada por

n = k1 l1 + k2 l2 + ::: + ks ls
kj ; lj 2 [n] ; l1 < ::: < ls

onde temos kj partes iguais a lj para j = 1; ::; s, então é possível encontrar uma permutação 2 Sn com
tipo cíclico T C ( ) = xkl11 xkl22 :::xklss . Na verdade existem muitas permutações em Sn com este tipo cíclico
dado, e o teorema a seguir nos diz quantas são. A demonstração abaixo é devida a Cauchy.

Teorema 4.1 Seja uma partição de n, dada por n = k1 l1 + k2 l2 + ::: + ks ls , com kj ; lj 2 [n] e l1 < l2 <
::: < ls . Então existem

n!
l1k1 k1 !l2k2 k2 !:::lsks ks !

permutações 2 Sn com tipo cíclico xkl11 xkl22 :::xklss

Dem. Seja h o número de permutações 2 Sn satisfazendo T C ( ) = xkl11 xkl22 :::xklss , isto é, contendo kj
ciclos de comprimento lj para j = 1; :::; s.
Vamos considerar as permutações com o tipo cíclico desejado, quebradas em seus ciclos componentes.
Primeiro listamos os k1 ciclos de comprimento l1 e representamos cada ciclo por l1 quadrados,
depois listamos os k2 ciclos de comprimento l2 , e representamos cada ciclo por l2 quadrados e assim

11
sucessivamente, até nalmente listarmos os ks ciclos de comprimento ls e seus quadrados.
8
>
> z
k
}|1 {
>
>
>
> l1 l1 l1
>
> z }| { z }| { z }| {
>
>
>
>
>
> k
>
> z }|2 {
>
< l2 l2 l2
z }| { z }| { z }| {
s
>
>
>
> .. .. ..
>
> . . .
>
>
>
> k
>
> z }|s {
>
> ls ls ls
>
> z }| { z }| { z }| {
>
:

Sabemos que o total de quadrados do diagrama acima é n, pois trata-se de uma permutação em Sn .
Então procedemos preenchendo arbitrariamente os n símbolos dentro dos n quadrados, isto é, vamos
inserir as n! permutações dos números [n] dentro dos n quadrados. Assim obtemos uma aplicação do
conjunto das n! permutações no conjunto das permutações com o tipo cíclico determinado acima.
Claramente, ao preencher os quadrados, podemos ter mais de uma permutação determinando o mesmo
resultado. Por exemplo, se n = 8, T C ( ) = x1 x22 x3 , ambos os preenchimentos abaixo resultam na mesma
permutação (4) (23) (15) (687):
4 2 3 5 1 7 6 8
4 1 5 3 2 8 7 6
Seja P uma das h permutações de Sn com o tipo cíclico desejado. Como P possui k1 ciclos de
comprimento l1 , a m de produzirmos P no preenchimento, suas k1 l1 -uplas de elementos devem ser
colocados nos k1 blocos de l1 quadrados cada. Cada l1 -upla pode ser colocada em qualquer ordem entre
os k1 blocos, assim temos k1 ! possiblidades para isso. Cada um dos k1 blocos, pode ser rotacionado
ciclicamente e isto pode ser feito de l1 maneiras por bloco, pois seu comprimento é l1 . Assim temos l1k1
possibilidades para as rotações cíclicas dos elementos dos blocos e portanto no total temos k1 !l1k1 maneiras
de obtermos os k1 ciclos de comprimento l1 de P . O mesmo raciocínio pode ser aplicado aos demais ciclos
k
de P , isto é, temos kj !lj j maneiras de obter os kj ciclos de comprimento lj para j = 1; :::; s. Portanto,
temos um total de
k1 !l1k1 k2 !l2k2 :::ks !lsks
permutações que quando colocadas nos quadrados geram os ciclos de P . Portanto, se plugarmos todas as
n! permutações nos quadrados do diagrama, cada permutação com esse tipo cíclico é gerada exatamente o
número de vezes indicado acima. Assim concluímos que
h k1 !l1k1 k2 !l2k2 :::ks !lsks = n!
de onde segue o resultado.

Corolário 4.1 Existe uma correspondência biunívoca entre os tipos cíclicos dos elementos de Sn e as
partições do inteiro n. Portanto, existem p (n) diferentes tipos cíclicos para as permutações de Sn , onde
p (n) é o número de partições do inteiro n.

Abaixo colocamos, a título de curiosidade, uma tabela contendo alguns valores de p (n).

12
 n p (n) n p (n)
1 1 10 42
2 2 20 627
3 3 30 5604
4 5 40 37338
5 7 50 204226
6 11 60 966467
7 15 70 4087968
8 22 80 15796476
9 30 90 56634173
Para encontrarmos a maior ordem que um elemento de Sn pode ter, por exemplo, uma maneira é
procurar nas partições de n = x1 + ::: + xs , aquela que tem o maior valor para mmc [x1 ; :::; xs ].
4.2 Índice de ciclos

De nição 4.2 Se G é um grupo de permutações, o índice de ciclos de G, denotado Z (G), é de nido como
sendo o polinômio
1 X
Z (G) = TC ( )
jGj 2G

Observe que a soma dos coe cientes do polinomio deve ser igual a 1, isto porque temos jGj termos na
soma, dividos pelo fator jGj.

Exemplo 4.3 Em S1 temos apenas a permutação identidade que possui tipo cíclico x1 . Isto nos dá triv-
ialmente
Z (S1 ) = x1
Em S2 temos as permutações (1) (2) e (12), que possuem tipos cíclicos iguais a x21 e x2 , respectivamente.
Portanto,
1 2
Z (S2 ) = x + x2
2 1
Para S3 , temos a permutação (1) (2) (3) com tipo cíclico igual a x31 , as permutações (12) (3), (13) (2),
(23) (1) com tipo cíclico x1 x2 e as permutações (123), (132) com tipo cíclico x3 . Assim, obtemos para o
índice de ciclos
1 3
Z (S3 ) = x + 3x1 x2 + 2x3
6 1
Abaixo fornecemos a fórmula fechada para os coe cientes do índice de ciclos de Sn .

Teorema 4.2 Temos a seguinte expressão geral para o índice de ciclos do grupo simétrico Sn
X 1
Z (Sn ) = k1 k2
xkl11 xkl22 :::xklss
k
l k !l k !:::ls ks !
s
k1 l1 +:::+ks ls =n 1 1 2 2
onde a soma é efetuada sobre todas as partições do inteiro n.

Dem. Este resultado sai diretamente do teorema 4.1 e da de nição de índice de ciclos. Basta somar nos
p (n) diferentes tipos cíclicos possíveis para as permutações de Sn .

13
5 - Ações de Grupos
Considerando um tabuleiro 2 2 temos um total de 24 = 16 colorações utilizando 2 cores (preta e branca):

C1 C2 C3 C4

C5 C6 C7 C8

C9 C10 C11 C12

C13 C14 C15 C16

Figura 2: 16 colorações de um tabuleiro de xadrez 2 2, nas cores preto e branco.

Do total listado acima, podemos inferir os seguintes conjuntos de padrões equivalentes:
fC1g
fC2; C3; C4; C5g
fC6; C7; C8; C9g
fC10; C11g
fC12; C13; C14; C15g
fC16g
Assim, por exemplo C6 e C8 estão no mesmo conjunto, pois um pode ser obtido do outro através de
uma rotação de um ângulo . Num tabuleiro 2 2 por ser mais simples, não faz diferença se considerarmos
ou não as re exões; isto é, basta considerarmos as rotações para diferenciar os padrões.
Se tivéssemos por exemplo, considerando tabuleiros 3 3, os diagramas abaixo não poderiam ser
obtidos um do outro apenas por rotações; necessitaríamos também das re exões.

14
 De qualquer forma, nas nossas observações sobre padrões de coloração equivalentes são as simetrias do
quadrado que estão sendo consideradas na diferenciação. O que estão implícitos em toda esta discussão
são conceitos sobre a interação entre um grupo (como o de simetrias de um quadrado, por exemplo) e os
membros de algum outro conjunto (como as 16 colorações do tabuleiro 2 2).

6 - Colorações
A seguir de nimos rigorosamente o que se entende por colorações de objetos, sejam tabuleiros, contas,
vértices, faces, etc...
Primeiro, como um exemplo mais concreto, consideramos novamente o tabuleiro de xadrez 2 2.

1 2

3 4

Então, se estamos colorindo de branco e preto, podemos considerar uma coloração f como uma aplicação
do conjunto dos quadrados f 1; 2; 3; 4g no conjunto das cores fpreto; brancog, isto é

f : f 1; 2; 3; 4g ! fpreto; brancog

As 16 colorações diferentes correspondem então às 16 aplicações diferentes com os domínios e

contradomínios de nidos acima.
A título de exemplo, a coloração correspondente a C10 denotada por f10 é a coloração

determinada por

f10 ( 1) = f10 ( 4) = preto

f10 ( 2) = f10 ( 3) = branco

Como utilizaremos este exemplo do tabuleiro 2 2 de maneira recorrente, é conveniente denotar por fj
a coloração correspondente ao diagrama Cj da Figura 2.

15
 Procedemos agora para o conceito geral. Sejam C e D dois conjuntos não-vazios (em geral são
diferentes também), e X = F (D; C), o conjunto de todas as funções com domínio D e contradomínio C.
Então dizemos que qualquer função f 2 X é uma coloração de D. Este é o caso mais abstrato.
Estaremos mais interessados nos casos em que C e D são nitos, e se #D = n; #C = m, temos pelo
princípio multiplicativo um total de mn colorações de D diferentes, isto é #X = mn

Exemplo 6.1 Se D é um conjunto de provas de alunos, podemos ter C como conjunto de notas (números)

Exemplo 6.2 Se D é um conjunto de contas ou pedrinhas, podemos ter C como conjunto de cores.

Exemplo 6.3 Se D é um conjunto de quadrados de um tabuleiro 2 2, podemos ter C como o conjunto

das cores fpreto; brancog

7 - Os Axiomas de Ação de Grupos

Queremos descrever a situação geral onde temos uma interação entre um grupo G e um conjunto X não
vazio.

De nição 7.1 Seja G um grupo e X um conjunto não-vazio. Dizemos que G age em X se, para todo
g 2 G e para todo x 2 X, existir um elemento g x 2 X satisfazendo as seguintes propriedades:
(A1) Para todo x 2 X, eG x = x, onde eG é a identidade de G.
(A2) Para todo g; h 2 G, x 2 X, temos

g (h x) = (gh) x

O axioma A1 signi ca que a ação do elemento identidade de G é sempre trivial, isto é, xa todo
elemento de X.
O segundo relaciona a ação do grupo à sua operação.
Sempre que um grupo age em um conjunto, dizemos que temos uma ação de grupo, e os axiomas A1 e
A2 são chamados de axiomas de ação de grupos.
Ao contrário do que fazemos com as operações de grupos, jamais devemos omitir o símbolo que
representa a ação de grupos. Isto porque estamos combinando elementos de conjuntos que geralmente são
diferentes (G e X).

Exemplo 7.1 Tome G como o grupo das simetrias do quadrado, e seja X o conjunto das colorações de
um tabuleiro 2 2 nas cores preta e branca.

Exemplo 7.2 Tome G como o grupo das simetrias rotacionais de um cubo, e X o conjunto de colorações
das faces do cubo usando vermelho, preto e verde.

16
Exemplo 7.3 Seja G qualquer grupo e X o conjunto dos elementos de G. De nimos uma ação de grupo
por
8g; x 2 G, temos g x = gxg 1
Esta ação é chamada de conjugação e o elemento do grupo gxg 1 é chamado de conjugado de x.

Lema 7.1 Seja G um grupo que age no conjunto X. Então para todo g 2 G, x; y 2 X, temos
1
g x = y () g y=x

Dem. Sejam g 2 G, x; y 2 X e suponha que g x = y. Então

1
g y = g 1 (g x)
= g 1 g x
= e x
= x
A recíproca é obtida aplicando o que acabamos de demonstrar, trocando x por y e g por g 1 .
Retornamos agora ao exemplo de colorações de tabuleiros 2 2, e vamos avaliar como uma permutação
age sobre uma coloração. Considere novamente o tabuleiro:

1 2

3 4

É fácil ver que para cada simetria do quadrado aplicada no tabuleiro, existe uma permutação correspondente
do conjunto dos quadrados f 1; 2; 3; 4g. Assim, se considerarmos a rotação a1 do tabuleiro por um
ângulo de 2 , temos

1 2 a1 3 1

3 4 4 2

que corresponde à permutação 1 = ( 1 2 4 3). Vamos tomar então nosso grupo G como sendo
o das permutações dos símbolos f 1; 2; 3; 4g e considerar sua ação no conjunto de colorações
X = F (f 1; 2; 3; 4g ; fpreto; brancog).
Por exemplo, a permutação 1 agindo na coloração f10 resulta na coloração f11

C10 C11

17
 e portanto
1 f10 = f11
Desta forma notamos que 1 f10 designa a cor branca para o quadrado 1, porque esta é a cor que f10
designa para o quadrado 3 que acabou de ser movido para o quadrado 1 por 1 . Como 1 1 ( 1) = 3,
podemos concluir que este processo é equacionado por
1
1 f10 ( 1) = f10 1 ( 1)

Esta fórmula se aplica em geral, e abaixo desenvolvemos mais rigorosamente este conceito.
Na notação da seção anterior, temos o conjunto de colorações X = F (D; C) e tomamos G como
algum grupo de permutações de símbolos de D. Isto é, G é algum subgrupo de S (D), o grupo de todas as
permutações do conjunto D.
De nimos uma ação de G no conjunto das colorações X, por
8 2 G; 8f 2 X ) f =f 1
(2)
e veri camos que realmente isto de ne uma ação de grupo.

Teorema 7.1 A fórmula (2) acima de ne uma ação de grupo.

Dem. Seja e a identidade de G. Então e é a aplicação identidade e : D ! D e para toda f 2 X,

1
e f =f e =f e=f
e assim (A1) se veri ca.
Sejam 1 ; 2 2 G e f 2 X. Então, pela nossa de nição,
1
2 ( 1 f) = 2 f 1
1 1
= f 1 2
1 1
= f 1 2
1
= f ( 2 1)
= ( 2 1) f
e portanto (A2) também é válido concluindo a demonstração.

8 - Órbitas

8.1 Relações de equivalência por ação de grupos

De nimos o conceito de ação de grupos, de forma a estabelecer o que entendemos por diferentes padrões de
coloração. No caso do tabuleiro 2 2, o grupo relevante é o grupo de simetrias do quadrado. Consideramos
que duas colorações do tabuleiro são essencialmente as mesmas se a ação de uma das simetrias leva uma
coloração na outra. Agora tornamos mais precisos estes conceitos de equivalência.

De nição 8.1 Seja G um grupo agindo em X. De nimos uma relação G em X da seguinte forma:
Para todo x; y 2 X,
x G y () 9g 2 G tal que g x = y

18
Lema 8.1 A relação G no conjunto X é uma relação de equivalência.

Dem. Mostramos que G é re exiva, simétrica e transitiva.

Sejam x; y; z 2 X. Como e 2 G é sua identidade, por (A1) segue que e x = x e portanto temos que
x G x e G é re exiva.
Se tivermos que x G y, então existe g 2 G com g x = y. Como G é grupo, existe o inverso g 1 e pelo
lema 7.1 temos que g 1 y = x e portanto y G x. Assim G é simétrica.
Suponhamos agora que x G y e y G z. Então existem g; h 2 G tais que g x = y e h y = z. Como
G é grupo, temos que hg 2 G e usando (A2) obtemos

(hg) x = h (g x) = h y = z
o que implica em x G z. Isto mostra que G é transitiva, e encerramos a demonstração do lema.
No exemplo envolvendo as colorações do tabuleiro de xadrez, temos que as classes de equivalência são
aqueles conjuntos que possuem colorações todas com o mesmo padrão.
Em geral, as classes de equivalência da relação G são chamadas de órbitas da ação do grupo. A órbita
à qual o elemento x pertence é denotada por Ox . Assim

Ox = Oy () x G y
e como x G y () y = g x para algum g 2 G, segue que

Ox = fg x : g 2 Gg
No exemplo 7.3, as classes de equivalência são chamadas de classes de conjugação do grupo em
questão. Pode-se mostrar, por exemplo, que duas permutações em Sn são conjugadas se, e somente se,
possuirem o mesmo tipo cíclico. Assim, se G = Sn , existe um total de p(n) classes de conjugação.
Como as órbitas são classes de equivalência, elas particionam o conjunto X em conjuntos disjuntos.
Assim nossa pergunta de quantos padrões diferentes temos ao colorir os tabuleiros é na verdade a de
quantas órbitas diferentes existem.
8.2 Inventários de colorações
Vamos desenvolver um método algébrico para descrever colorações, utilizando funções geradoras. Aqui a
situação ideal é obter uma função geradora que determine o número de padrões de cada tipo para a situação
em questão.
Já vimos que temos um total de 16 maneiras de colorir um tabuleiro de xadrez 2 2, sem considerarmos
as relações de equivalência de padrões; isto é, não estamos contando as órbitas. Observe que na expansão

(p + b)4 = (p + b) (p + b) (p + b) (p + b) = p4 + 4p3 b + 6p2 b2 + 4pb3 + b4

obtemos cada coe ciente escolhendo de cada parênteses o símbolo p ou b, e isso corresponde às 16
colorações diferentes do tabuleiro 2 2 nas cores preta e branca. Mais ainda, cada termo na expansão lista
o número de colorações de acordo com quantas cores brancas e pretas estão sendo utilizadas. Deste modo,
o termo p3 b tem como coe ciente 4, que é o número de colorações (C12, C13, C14 e C15) contendo 3
cores pretas e 1 branca. O termo p4 tem coe ciente 1, indicando que temos apenas 1 coloração (C16)
contendo 4 cores pretas.
No entanto, esta expressão algébrica não nos diz nada acerca de quantos padrões diferentes existem
por equivalência; isto é, não nos exibe informações sobre as órbitas das colorações. Mais à frente,

19
enunciaremos um teorema que nos permitirá obter uma função geradora que contenha tal informação; e as
de nições a seguir serão necessárias para a aplicação daquele resultado.
Os símbolos algébricos p e b correspondem às cores preta e branca, respectivamente, ambas elementos
do conjunto C. No caso geral, entendemos por uma função peso no conjunto C, uma função ! que associa
a cada c 2 C, um símbolo algébrico ou um número denotado por ! (c), denominado peso de c.
P
O enumerador de estoque é de nido pela soma c2C ! (c), isto é, representa de maneira algébrica
todos os valores que os elementos do conjunto D podem receber através das colorações de D em
C. Por exemplo, sejam C = fvermelho claro; vermelho escuro; azulg, ! (vermelho claro) = r,
! (vermelho escuro) = R e ! (azul) = a. Então o enumerador de estoque (de tintas, ou cores, no caso)
é r + R + a; isto é, interpretando a soma como função geradora, signi ca que temos exatamente 1 cor
vermelho clara, 1 cor vermelho escura e 1 cor azul. Assim, nosso enumerador de estoque é na verdade uma
generalização do conceito de função geradora. Se colocarmos r = R, temos como enumerador de estoque
2R + a, o que signi ca que temos 2 cores vermelhas e 1 cor azul para designar aos elementos de D. Vale
ressaltar que os dois tipos de tinta vermelha ainda são dois tipos distintos, mesmo que tenhamos designado
o mesmo peso para as duas. Se os dois tipos de tinta vermelha fossem indistinguíveis, o enumerador de
estoque seria dado por R + a, ao invés de 2R + a.
Para cada coloração f 2 X, de nimos seu peso W (f ) pela equação
Y
W (f ) = ! (f (d))
d2D
Finalmente, dado um subconjunto S de X, o inventário de S é de nido por
X
W (f )
f 2S

Exemplo 8.1 Suponha que desejamos saber todas as maneiras de pintarmos 3 bolas distintas nas cores
sólidas vermelho claro, vermelho escuro e azul. Seja D o conjunto das 3 bolas, e seja C o conjunto dos 3
tipos de tinta mencionados. Designamos os pesos para as cores como anteriormente, obtendo o enumerador
de estoque r + R + a que nos fornece o número de maneiras que 1 bola pode ser pintada nas cores de C.
Assim, como as bolas são distintas, (r + R + a)3 nos dá o total de maneiras diferentes de pintarmos 3
bolas com as cores escolhidas. Em outras palavras, (r + R + a)3 é o inventário do conjunto de todas as
colorações de D em C.

Retornamos ao exemplo do tabuleiro 2 2 para tornar claras as de nições dadas acima.

Relembramos que D = f 1; 2; 3; 4g, o conjunto dos 4 quadrados do tabuleiro, C =
fpreto; brancog, o conjunto das cores e X = F (f 1; 2; 3; 4g ; fpreto; brancog) é o conjunto das
colorações de D em C.
A função peso no nosso exemplo é dada por
! (preto) = p
! (branco) = b
A coloração f10 é tal que
f10 ( 1) = preto
f10 ( 2) = branco
f10 ( 3) = branco
f10 ( 4) = preto

20
 e portanto
Y
W (f10 ) = ! (f10 (d)) = ! (f10 ( 1)) ! (f10 ( 2)) ! (f10 ( 3)) ! (f10 ( 4))
d2D
= ! (preto) ! (branco) ! (branco) ! (preto)
= pbbp
= p2 b2
O inventário de todas as 16 colorações (isto é S = X), como visto anteriormente, é dado por
X
W (f ) = p4 + 4p3 b + 6p2 b2 + 4pb3 + b4 = (p + b)4
f 2X

O problema de maior interesse para nosso estudo é o de determinar o inventário das colorações que
contém exatamente 1 coloração de cada padrão (órbita). No caso dos tabuleiros ele seria dado por

p4 + p3 b + 2p2 b2 + pb3 + b4
conforme pode ser visto na Figura 2 da página 14.
Este inventário é chamado de inventário padrão, e o teorema que determina sua função geradora é o
celebrado Teorema Enumerador de Pólya.

9 - Estabilizadores
Na seção 7, através do axioma (A1), determinamos que a identidade e de um grupo G agindo em X,
xasse todos os elementos de X. No entanto, podemos ter, além da identidade, outros elementos de g
xando elementos de X.
Assim, dado x 2 X, chamamos de estabilizador de x, o conjunto dos elementos de G que na ação de
grupo xam x.
Em símbolos, o estabilizador de x é de nido por

Sx = fg 2 G : g x = xg
A seguir mostramos que para qualquer x 2 X, o estabilizador Sx é um subgrupo de G.

Lema 9.1 Seja G um grupo agindo em X. Então, para todo x 2 X, temos que Sx é subgrupo de G.

Dem. Veri camos as condições de subgrupo para Sx . Primeiro suponha que g; h 2 Sx . Então g x = x e
h x = x, e pelo axioma (A2) temos que

(gh) x = g (h x) = g x = x
e assim gh 2 Sx , o que mostra que Sx é fechado.
Por (A1), e x = x e assim Sx contém a identidade de G.
Novamente, se g 2 Sx , temos que g x = x e pelo lema 7.1 temos que g 1 x = x o que mostra que g 1

também está em Sx . Assim Sx é um subgrupo de G.

Abaixo colocamos um quadro com os estabilizadores e as órbitas das colorações de um tabuleiro de
xadrez 2 2:

21
 Elemento de X Estabilizador Órbita
C1 fe; a1 ; a2 ; a3 ; p1 ; p2 ; q1 ; q2 g fC1g
C2 fe; q1 g
C3 fe; q2 g
fC2; C3; C4; C5g
C4 fe; q1 g
C5 fe; q2 g
C6 fe; p2 g
C7 fe; p1 g
fC6; C7; C8; C9g
C8 fe; p2 g
C9 fe; p1 g
C10 fe; a2 ; q1 ; q2 g
fC10; C11g
C11 fe; a2 ; q1 ; q2 g
C12 fe; q2 g
C13 fe; q1 g
fC12; C13; C14; C15g
C14 fe; q2 g
C15 fe; q1 g
C16 fe; a1 ; a2 ; a3 ; p1 ; p2 ; q1 ; q2 g fC16g

Observe que quanto maior o estabilizador, menor a órbita e vice-versa. Mais ainda, repare que em todas
as linhas (elementos x de X) temos a equação # (Ox ) # (Sx ) = 8. Isto não é uma coincidência e abaixo
provamos este resultado, muito importante para nosso estudo.

Teorema 9.1 (O Teorema Órbita-Estabilizador) Seja G um grupo que age em X. Então para cada
x 2 X,
# (Ox ) # (Sx ) = # (G)

Dem. Pelo lema 9.1, temos que Sx é um subgrupo de G, e pelo teorema de Lagrange segue que

jG : Sx j # (Sx ) = # (G)
Assim precisamos mostrar que
# (Ox ) = jG : Sx j (3)
Os elementos de Ox possuem a forma g x, para g 2 G e as classes laterais de Sx possuem a forma
gSx para g 2 G. Podemos provar a equação (3) mostrando que a correspondência g x $ gSx é uma
correspondência um-a-um entre os elementos de Ox e as classes laterais de Sx em G. Em outras palavras,
basta mostar que, para todo g; h 2 G;

gSx = hSx () g x = h x
Sejam g; h 2 G. Então
gSx = hSx () h 1 g 2 Sx , pelo lema 2.4
() (h 1 g) x = x, pela de nição de Sx
() h 1 (g x) = x, por (A2)
() g x = h x, pelo lema 7.1

22
Corolário 9.1 Seja G um grupo nito que age no conjunto X. Então o número de elementos de X em
cada órbita é um divisor da ordem de G.

Dem. Imediata a partir da equação multiplicativa do teorema Órbita-Estabilizador.

O Teorema Órbita-Estabilizador fornece uma relação entre o número de elementos em cada órbita e o
número de elementos em cada estabilizador. Abaixo provamos facilmente um teorema que modi ca esta
relação para derivarmos uma fórmula para o número de diferentes órbitas da ação.

Teorema 9.2 Seja G um grupo nito agindo em X. Então o número de órbitas distintas é dado por
1 X
# (Sx )
# (G) x2X

Dem. Suponhamos que existam m órbitas distintas Ox1 ; :::; Oxm . Se 1 j m, temos para a j-ésima
órbita que
X X # (G)
# (Sx ) = , pelo Teorema Órbita-Estabilizador
x2O x2O
# (Ox )
xj xj

X 1
= # (G) , pois Ox = Oxj para todo x 2 Oxj
x2Oxj
# Oxj
# (G) X
= 1
# O xj x2Oxj

= # (G)
Assim, somando para todas as órbitas obtemos,
X X
m X X
m
# (Sx ) = # (Sx ) = # (G) = m# (G)
x2X j=1 x2Oxj j=1

o que nos fornece o resultado desejado.

Observe que esta fórmula ainda não é de muito uso, pois devemos listar todos os elementos de X, o que
nos possibilitaria, sem nenhuma teoria elaborada, diferenciar os padrões desejados por inspeção. No caso
do tabuleiro 2 2, temos que # (X) = 16, mas no caso do tabuleiro de xadrez 8 8, por exemplo, temos
que # (X) = 264 > 1019 , o que torna impraticável listar todos os elementos de X.
Na seção seguinte, demonstramos um resultado que nos permite obter o número de órbitas somando nos
elementos de G, ao invés de X:

10 - O Teorema de Burnside
Apesar do teorema (usualmente chamado de lema) a seguir ter se associado ao nome de William Burnside,
ele foi primeiramente provado por Georg Frobenius em 1887. Burnside publicou um livro muito in uente
em teoria dos grupos e sua primeira edição foi o primeiro texto em inglês deste assunto, por exemplo.
Nesta primeira edição, Burnside coloca o teorema e o atribui a Frobenius, mas essa atribuição não passou
para a segunda edição, de muito maior penetração. É provável que isso tenha originado toda essa confusão
histórica.

23
 A m de obtermos a versão desejada para o número de órbitas, consideramos a tabela abaixo,
Elementos de X
xj

Elementos de G gi

onde as linhas correspondem a elementos de G e as colunas a elementos de X.

Marcamos uma entrada na tabela na interseção de uma j-ésima coluna com uma i-ésima linha, isto é,
da coluna de um elemento de X, com a linha de um elemento de G, se e somente se,
gi xj = xj
isto é, se e somente se, gi 2 Sxj .
P Assim, o número de marcas em uma coluna j é # Sxj e portanto o número total de marcas na tabela é
x2X # (Sx ).
Agora ao invés de adicionarmos as marcas por colunas, adicionaremos por linhas.
O número de marcas na i-ésima linha é dado pelo número de elementos do conjunto
fx 2 X : gi x = xg
isto é, o número de elementos de X que são xados pelo elemento gi de G.

De nição 10.1 Seja G um grupo agindo em X, de nimos o Fix de g 2 G como

F ix (g) = fx 2 X : g x = xg

Desta forma se somarmos o total de marcas de cada linha, obtemos todas as marcas da tabela, isto é,
X X
# (F ix (g)) = # (Sx )
g2G x2X

Demonstramos então o seguinte teorema:

Teorema 10.1 (Teorema de Burnside) Se G é um grupo nito agindo em um conjunto X, então o número
de órbitas distintas é dado por
1 X
# (F ix (g))
# (G) g2G

24
11 - Aplicações

Problema 11.1 Obter o número de permutações circulares de n elementos; isto é, determinar o número
de maneiras de arranjarmos n objetos distintos em torno de um círculo.

Solução 11.1 Neste problema, o conjunto X de colorações é formado pelas n! permutações (aqui C =
D = [n]) dos n objetos distintos. Para de nirmos o grupo G de simetrias, basta notar que uma disposição
em círculo é considerada a mesma que outra, se uma puder ser obtida da outra por alguma rotação.
Portanto o grupo G é o composto pela identidade e por (n 1) rotações. A identidade e xa todos os n!
elementos de X, mas qualquer outro elemento g 2 G é tal que F ix (g) = 0. Isto porque os n elementos
são todos distintos e qualquer rotação não-trivial leva uma con guração de X em alguma outra diferente.
Pelo teorema de Burnside temos então que o número de permutações circulares de n elementos é dado por
0 1
n 1 zeros
1@ z }| {
n! + 0 + ::: + 0A = (n 1)!
n

Problema 11.2 De quantas maneiras diferentes podemos pintar as faces de um cubo, utilizando c cores
diferentes? Calcule o número de pinturas utilizando as cores vermelho, preto e verde.

Solução 11.2 O número total de colorações presentes em X neste caso é dado por c6 , pois um cubo tem 6
faces. Entendemos por igualdade entre uma pintura e outra, se uma puder ser obtida da outra por alguma
simetria de rotação do cubo. No exemplo 3.3 listamos as 24 simetrias rotacionais do cubo descrevendo-as
em 7 itens. Uma coloração de X é xada por g 2 G se, e somente se, todas as faces no mesmo ciclo de g
possuem a mesma cor. Vamos calcular aqui para cada simetria de cada item quantos elementos de X ela
xa:
(1) A identidade e xa todos os elementos de X ) F ix (e) = c6 ;
(2) Cada rotação de 2 pelo eixo indicado em (a) possui 1 ciclo de comprimento 4 e 2 ciclos de compri-
mento 1 nas faces. Assim, se uma coloração destas faces permanece inalterada após a rotação, teremos c
diferentes possibilidades de cores para as 4 faces que compõem o ciclo de comprimento 4 e c cores difer-
entes para as faces de cada ciclo unitário. Portanto pelo princípio multiplicativo, temos c c c diferentes
colorações que são xadas por cada rotação de 2 indicada em (a). A contribuição destas 3 rotações é de
3c3 ;
(3) Para a rotação de pelo eixo indicado em (a), temos 2 ciclos de comprimento 2 e 2 ciclos de com-
primento 1. Pelas mesmas considerações feitas no item (2) acima, concluímos pelo princípio multiplicativo
que o F ix de cada uma das 3 rotações é dado por c c c c. Assim a contribuição destas 3 rotações é de
3c4 ;
(4) Uma rotação de 32 pelo eixo de (a) é equivalente a uma de 2 pelo mesmo eixo. Por simetria temos
a mesma contribuição do item (2), isto é, 3c3 ;
(5) Cada rotação de pelo eixo indicado em (b) possui 3 ciclos de comprimento 2. Assim temos uma
contribuição de 6c3 ;

25
 (6) Cada rotação de 23 pelo eixo indicado em (c) possui 2 ciclos de comprimento 3. Portanto temos uma
contribuição de 4c2 ;
(7) Uma rotação de 43 é equivalente a uma de 23 , e por simetria temos a mesma contribuição do item
(6), isto é, 4c2 .
Pelo teorema de Burnside, temos então que o número de pinturas distintas das faces do cubo utilizando
c cores é
1 6 1 6
c + 3c3 + 3c4 + 3c3 + 6c3 + 4c2 + 4c2 = c + 3c4 + 12c3 + 8c2
24 24
Para 3 cores, basta substituir c = 3 no polinômio acima para obter 57 pinturas distintas.

Problema 11.3 Quantas moléculas orgânicas diferentes da forma

X
X C X
X
existem, onde C é um átomo de carbono e cada X denota qualquer um dos 4 componentes CH3 (metil),
C2 H5 (etil), H (hidrogênio) ou Cl (cloro)? (Aqui da química sabemos que cada molécula desse tipo pode
ser modelada por um tetraedro regular com o carbono ocupando seu centro e os componentes X ocupando
os vértices).

Solução 11.3 Considere a gura abaixo exibindo os dois tipos de eixo de rotação que o tetraedro regular
possui:

(a) (b)

Temos um total de 44 = 256 colorações diferentes no conjunto X, pois neste caso estamos colorindo os
vértices do tetraedro com 4 "cores" distintas. G é de nido como o grupo das 12 simetrias rotacionais do
tetraedro regular e vamos calcular o F ix de cada uma elas:
(1) A identidade xa todas as 256 colorações de X.

26
 (2)Temos 8 simetrias de rotação pelo tipo de eixo indicado em (a), que passa por um vértice e pelo centro
da face oposta. São 4 simetrias de rotação de um ângulo de 23 e 4 simetrias de rotação de um ângulo de
2
3
. Cada rotação é composta de 1 ciclo de comprimento 1 e 1 ciclo de comprimento 3. Assim temos uma
contribuição de 8 4 4 = 128 colorações xadas.
(3) Temos 3 simetrias de rotação de um ângulo de pelo tipo de eixo indicado em (b), que passa pelos
pontos médios de arestas opostas. Cada rotação desta é composta de 2 ciclos de comprimento 2. Portanto
temos uma contribuição de 3 4 4 = 48 colorações xadas.
Aplicando o teorema de Burnside obtemos que o número de moléculas distintas nas condições do prob-
lema é igual a
1
(256 + 128 + 48) = 36
12

12 - O Teorema Enumerador de Pólya

Enunciamos o teorema de Pólya e apresentamos nesta seção uma de suas aplicações aos problemas
anteriores.

Teorema 12.1 (Teorema de Pólya) Seja X = F (D; C) o conjunto de todas as colorações do conjunto
D em C, e seja ! uma função peso em C. Seja G o grupo das permutações de D que age em X de maneira
usual. Se o índice de ciclos de G é
Z (G; x1 ; x2 ; x3 ; :::)
então o inventário padrão é dado por
!
X X X
Z G; ! (c) ; ! (c)2 ; ! (c)3 ; :::
c2C c2C c2C

Problema 12.1 De quantas maneiras podemos colorir as faces de um cubo utilizando as cores verde,
amarelo e branco, de maneira que em cada pintura tenhamos exatamente 2 faces amarelas e 2 verdes? E a
quantidade de pinturas contendo exatamente 1 face amarela?

Solução 12.1 Baseado nas considerações do problema 11.2, podemos obter facilmente a seguinte ex-
pressão para o índice de ciclos das simetrias de rotação de um cubo:
1
x6 + 3x21 x22 + 6x21 x4 + 6x32 + 8x23
24 1
Colocamos como peso de cada cor

! (amarelo) = a
! (verde) = v
! (branco) = b
e assim obtemos o enumerador de estoque
a+v+b

27
Então, pelo teorema de Pólya, temos que o inventário padrão é dado por
1 2
((a + v + b)6 + 3 (a + v + b)2 a2 + v 2 + b2 + 6 (a + v + b)2 a4 + v 4 + b4 +
24
3 2
+6 a2 + v 2 + b2 + 8 a3 + v 3 + b3 )

É conveniente usar algum software de álgebra simbólica para expandir esta soma e obter

a6 + b6 + v 6 + ab5 + a5 b + av 5 + a5 v + bv 5 + b5 v +
+2abv 4 + 2ab4 v + 2a4 bv + 2a2 b4 + 2a3 b3 + 2a4 b2 +
+2a2 v 4 + 2a3 v 3 + 2a4 v 2 + 2b2 v 4 + 2b3 v 3 + 2b4 v 2 +
+3ab2 v 3 + 3ab3 v 2 + 3a2 bv 3 + 3a2 b3 v + 3a3 bv 2 + 3a3 b2 v + 6a2 b2 v 2

Para responder a primeira parte do problema, buscamos o coe ciente do termo a2 v 2 b2 , que é igual a 6.
Para a segunda pergunta, devemos agrupar todos os termos que contém a1 :

a b5 + v 5 + 2bv 4 + 2b4 v + 3b2 v 3 + 3b3 v 2

totalizando então 12 maneiras distintas:

Problema 12.2 No problema 11.3, qual é o número de moléculas que contém um ou mais átomos de
hidrogênio?

Solução 12.2 O índice de ciclos para o problema 11.3 é facilmente obtido de sua resolução, sendo dado
por
1
x41 + 8x1 x3 + 3x22
12
Designamos os pesos

! (CH3 ) = w1
! (C2 H5 ) = w2
! (Cl) = w3
! (H) = 0
a cada um dos componentes do problema.
Assim nosso enumerador de estoque é
w1 + w2 + w3
que, pelas nosssas considerações na seção 8.2, é a função geradora para 1 componente CH3 , 1 compo-
nente C2 H5 , 1 componente Cl e nenhum componente H. Desta forma estaremos enumerando primeiro as
moléculas que não possuem átomos de hidrogênio.
Pelo teorema de Pólya, temos então que o inventário padrão é dado por
1 2
(w1 + w2 + w3 )4 + 8 (w1 + w2 + w3 ) w13 + w23 + w33 + 3 w12 + w22 + w32
12

28
que ao ser expandido resulta em:
w14 + w24 + w34 + w1 w23 + w13 w2 + w1 w33 + w13 w3 +
+w2 w33 + w23 w3 + w1 w2 w32 + w1 w22 w3 + w12 w2 w3 +
+w12 w22 + w12 w32 + w22 w32
Portanto temos um total de 15 moléculas não contendo átomos de hidrogênio. Repare que a expressão
acima diz muito mais que isso, pois nela está determinada qual a composição em componentes de cada
uma das 15 moléculas. Também é interessante observar que, na função geradora acima, temos apenas 1
molécula para cada combinação dos 3 componentes CH3 , C2 H5 e Cl.
Como nesta resolução estamos interessados no número total de moléculas, pouparíamos trabalho se
tivéssemos logo atribuído o peso 0 ao componente hidrogênio e peso 1 aos 3 componentes restantes. Do
teorema de Pólya obteríamos diretamente o número
1 4
3 + 8 3 3 + 3 32 = 15
12
Assim, como o número total de moléculas obtidas no problema 11.3 é 36, temos
36 15 = 21
moléculas que contém pelo menos 1 átomo de hidrogênio.

13 - Apêndice: Enumerando colares distintos

Ao contar colares, necessitamos encontrar o índice de ciclos do grupo cíclico Cn (se considerarmos apenas
rotações) e do grupo diedral D2n (se inversões são permitidas). Isto porque, num colar contendo n contas
distintas, podemos considerar cada conta como ocupando cada um dos vértices de um polígono regular
de n lados. Se um colar não puder ser invertido (virado, re etido), então não utilizamos as simetrias de
re exões presentes em D2n , nos limitando às rotações que compõe Cn .
Neste apêndice, denotamos o mdc (a; b) simplesmente por (a; b).

De nição 13.1 A função totiente de Euler : N ! N é de nida por

X
(n) = 1
1 d n
(d;n)=1

sendo dada pelo número de inteiros positivos menores ou iguais a n que são coprimos com n. Esta função
também pode ser interpretada como o número de classes de congruência módulo n que são coprimas com
n.

Para nossas aplicações, fazemos uso do seguinte resultado:

Lema 13.1 O grupo Cn (cíclico de ordem n) contém para cada divisor d de n, (d) elementos de ordem
d. Cada um desses elementos possui n=d ciclos de comprimento d.

Assim temos que o índice de ciclos de Cn é dado por

1X n=d
Z (Cn ) = (d) xd
n
djn

29
onde a soma é efetuada nos divisores d de n e é a função totiente de Euler.
O grupo diedral D2n contém o subgrupo Cn mais n re exões. Se n 1 (mod 2) então cada re exão
tem um ponto xo e (n 2 1) transposições (2-ciclos); enquanto que se n 0 (mod 2), temos metade que são
n
2
transposições e a outra metade são 2 pontos xos e (n 2 2) transposições. Desta forma
1
Z (D2n ) = (Z (Cn ) + Rn )
2
onde 8 n 1
< x1 x2 2 , se n 1 (mod 2)
Rn = n (n 2)
: 1
2
x2 + x21 x2
2 2
, se n 0 (mod 2)
A seguir apresentamos a enumeração geral dos colares e alguns exemplos particulares.

Problema 13.1 Qual o número de colares distintos, formados por n contas de m cores diferentes? (Con-
sidere os argumentos iniciais desta seção e divida o problema em dois casos).

Solução 13.1 Se considerarmos apenas as rotações, pelo teorema de Pólya, temos que o número é dado
por
1X
(d) mn=d (4)
n
djn
onde atribuímos peso 1 a cada uma das m cores, e substituimos
X X
xd = ! (c)d = 1d = m
c2C c2C

no índice de ciclos de Cn .
Ao considerarmos também as inversões (re exões), aplicamos o teorema de Pólya e substituimos o
enumerador de estoque no índice de ciclos de D2n . Desta forma obtemos a expressão
0 1
1 @1 X
(d) mn=d + Rn (m)A (5)
2 n
djn

onde n+1
m 2 , se n 1 (mod 2)
Rn (m) n
1
2
m 2 (1 + m) , se n 0 (mod 2)

Problema 13.2 Calcule:

(a) o número de colares diferentes, por rotações, com 6 contas coloridas em preto e branco;
(b) o número de colares diferentes, por rotações e inversões, com 5 contas coloridas em preto, cinza e
branco;
(c) as mesmas condições do item (b), exceto que cada colar deverá ter exatamente 1 conta na cor preta.

30
Solução 13.2 (a) Na fórmula 4 do problema 13.1 colocamos n = 6; m = 2 para obter
1X 1
(d) 26=d = (1) 26 + (2) 23 + (3) 22 + (6) 2
6 6
dj6
1
= (64 + 8 + 8 + 4)
6
= 14
Portanto temos 14 colares distintos como resposta.
(b) Substituimos na fórmula 5 do problema anterior n = 5; m = 3 e obtemos
0 1
1 @1 X 1 1
(d) 35=d + R5 (3)A = (1) 35 + (5) 3 + 33
2 5 2 5
dj5

1 1
= (243 + 12) + 27
2 5
1 255
= + 27
2 5
1
= (78)
2
= 39
Temos então 39 colares distintos como resposta. É interessante comparar as respostas dos itens (a) e (b)
e suas condições. De lá para cá, diminuímos 1 conta do total e consideramos colares re etidos como
idênticos; isto tende a diminuir o número de padrões distintos. No entanto, aumentamos 1 cor no estoque
e isso foi o su ciente para termos quase o triplo de padrões distintos do item anterior. (Esta análise pode
ser facilmente inferida no caso geral do formato do índice de ciclos utilizado)
(c) Desta vez atribuímos os pesos

! (preto) = p
! (cinza) = 1
! (branco) = 1
Aplicamos o teorema de Pólya e substituímos nosso enumerador de estoque no índice de ciclos de D10 ,
obtendo
0 1
1 @1 X 5=d 2
(d) pd + 1d + 1d + (p + 1 + 1) p2 + 12 + 12 A
2 5
dj5
2
1 (p + 2) (p2 + 2)
= (p + 2)5 + 4 p5 + 2 +
10 2
= 10p + 12p2 + 6p3 + 2p4 + p5 + 8
Nesta função geradora buscamos o coe ciente de p1 que é igual a 10. Portanto temos 10 colares difer-
entes nas condições requisitadas e contendo exatamente 1 conta preta (veri que na gura a seguir os 10
colares!).
Na página seguinte listamos todos os colares correspondentes aos números encontrados neste problema:

31
Colares diferentes por rotação, Colares diferentes por rotação e inversão
contendo 6 contas nas cores contendo 5 contas nas cores preto, cinza e
preto e branco: branco:

32