Embed Size (px)
Citation preview
O Teorema de Enumeração de Pólya,
Generalizações e Aplicações
por
Eduardo Bovo
2 0 0 5
FICHA CATALOGRÁFICA ELABORADA PELA BIBLIOTECA DO IMECC DA UNICAMP
Bibliotecario: Maria Júlia Milani Rodrigues – CRB8a / 2116
Bovo, Eduardo
B669t O teorema de enumeração de Pólya, generalizações e aplicações / --
Campinas, [S.P. :s.n.], 2005.
Orientador : José Plínio de Oliveira Santos
Dissertação (mestrado) - Universidade Estadual de Campinas,
Instituto de Matemática, Estatística e Computação Científica.
1. Problemas de enumeração combinatória. 2. Grupos de
permutação. 3. Funções geradoras . I. Santos, José Plínio de Oliveira. II.
Universidade Estadual de Campinas. Instituto de Matemática, Estatística
e Computação Científica. III. Título.
Título em inglês: Pólya´s enumeration theorem, generalizations and applications. Palavras-chave em inglês (Keywords): 1. Combinatorial enumeration problems. 2. Permutation groups. 3. Generating functions. Área de concentração: Combinatória enumerativa Titulação: Mestre em Matemática Aplicada Banca examinadora: Prof. Dr. José Plínio de Oliveira Santos (IME-UNICAMP) Prof. Dr. Paulo Mondek (UFMS) Prof. Dr. Paulo Regis Caron Ruffino (IME-UNICAMP) Data da defesa: 29/04/2005
Abstract
In this dissertation we present algebraic, analytic and combinatorial results that areused to prove Polya's Enumeration Theorem. Applications to counting patterns(graphs, colourings, permutations, etc.) are given. This classical Theorem has itsfoundations on the theory of groups and uses, mainly, the concept of generatingfunctions which allows great generality and computability of results. At the end somegeneralizations of the main theorem are given including applications and, aiso, animportant probabilistic interpretation.
Resumo
Nestetrabalho são desenvolvidos conceitos algébricos, analíticos e combinatórios queculminam no Teorema de Enumeração de Polya: bem como são fornecidas muitas desuasaplicações em enumeração de padrões (grafos, colorações geométricas, tipos depermutações, etc.). Tal teorema clássico, que tem suas bases em Teoria dos Grupos,utiliza fundamentalmente o conceito de funções geradoras, o que permite. grandegeneralidade e computabilidade de resultados. Finalmente são apresentadas algumasgeneralizações do resultado principal, aplicações destas e também uma importanteinterpretação probabilística. ..
2
Sumário
Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Capítulo 1. Definições e resultados preliminares . . . . . . . . . . 41.1. Grupos de Simetria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2. Anel de séries de potências formais com coe�cientes complexos . . . . 81.3. Partições de Inteiros . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Capítulo 2. Grupos de Permutações . . . . . . . . . . . . . . . . . . . 132.1. Representação por ciclos disjuntos . . . . . . . . . . . . . . . . . . . . 132.2. Ordens de Permutações . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3. Números de Stirling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Capítulo 3. Índice de Ciclos . . . . . . . . . . . . . . . . . . . . . . . . 203.1. Tipo cíclico, Índice de ciclos e partições de Inteiros . . . . . . . . . . 203.2. A função geradora para o índice de ciclos de Sn e aplicações . . . . . 273.3. Interpretação probabilística do Índice de Ciclos de Sn . . . . . . . . . 31
Capítulo 4. Ação de Grupos e Colorações . . . . . . . . . . . . . . . 354.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.2. Ação de grupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.3. Colorações e ações de grupos . . . . . . . . . . . . . . . . . . . . . . . 38
Capítulo 5. Órbitas e Estabilizadores . . . . . . . . . . . . . . . . . . 415.1. Órbitas e relações de equivalência . . . . . . . . . . . . . . . . . . . . 415.2. Estabilizadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.3. Objetos rotulados e não-rotulados . . . . . . . . . . . . . . . . . . . . 465.4. O Lema de Burnside . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.5. Aplicações do Lema de Burnside . . . . . . . . . . . . . . . . . . . . . 50
Capítulo 6. O Teorema de Enumeração de Pólya . . . . . . . . . . 546.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546.2. Pesos de colorações, enumerador de estoque e inventários . . . . . . . 546.3. Demonstração do Teorema de Pólya e Corolários . . . . . . . . . . . . 586.4. Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.5. Enumerando grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716.6. Generalizações e Aplicações . . . . . . . . . . . . . . . . . . . . . . . 77
Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4
Capítulo 1
Definições e resultados preliminares
Neste capítulo de�nimos conceitos e desenvolvemos vários resultados que permearão
todo o trabalho.
De�nição 1. (i) Dado n 2 N = f1; 2; 3; : : :g, de�nimos [n] = f1; 2; 3; : : : ; ng;
(ii) N0= f0g [ N isto é, o conjunto dos inteiros não-negativos;
(iii) Dados dois inteiros k1; k2, denotamos seu máximo divisor comum e mínimo
múltiplo comum, respectivamente, por (k1; k2) e [k1; k2];
(iv) A função maior inteiro é a que associa a cada número real x o maior inteiro
menor do que ou igual a x. Denotamos este valor por bxc.
De�nição 2. Dado x 2 C; n 2 N0 de�nimos as potências fatoriais crescentes e
decrescentes, respectivamente por
xn =
�1, se n = 0x (x+ 1) � � � (x+ n� 1) , se n 2 N
e
xn =
�1, se n = 0x (x� 1) � � � (x� n+ 1) , se n 2 N
Observe que a segunda linha em cada de�nição é um produto vazio para n = 0, o
que geralmente de�nimos como tendo valor igual a 1.
A título de curiosidade, pois neste trabalho não utilizaremos esta propriedade,
estas expressões são chamadas de potências fatoriais, pois se� é o operador diferença,
�f (x) = f (x+ 1)� f (x), então
�xn = nxn�1.
5
1.1 Grupos de Simetria
Para a enumeração de diversos objetos combinatórios e geométricos, o conceito de
grupo de simetrias é muito útil.
De�nição 3. Para as aplicações, entende-se por uma �gura um conjunto F de pontos
de R2 ou R3.
De�nição 4. 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 5. Um triângulo eqüilátero possui 6 simetrias: 1 delas é a identidade, 2
são rotações horárias centradas em seu centro de gravidade de ângulos 2�3e 4�
3e 3
delas são re�exões através de suas medianas.
Exemplo 6. Um quadrado desenhado no plano possui 8 simetrias: 1 delas é a iden-
tidade, 3 são rotações horárias centradas em seu centro de gravidade de ângulos �2,
� e 3�2, 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, faces, ou outros elementos das �guras.
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.
6
1
SIMETRIA RESULTADO PERMUTAÇÃO
(1)(2)(3)
2 3
1
2 3
e
1
(132)
2 3
2
3 1
/3
1
(123)
2 3
3
1 2
/3
1
(1)(23)
2 3
1
3 2
1
(13)(2)
2 3
3
2 1
1
2 3
21
1 3
(12)(3)
SIMETRIA RESULTADO PERMUTAÇÃO
1
e
3
2
4
1
3
2
4 e = (1)(2)(3)(4)
1
3
2
4
3
4
1
2a1 = (1243)
1
3
2
4
4
2
3
1a2 = (14)(23)
1
3
2
4
2
1
4
3 a3 = (1342)
/2
/2
1
3
2
4
2
4
1
3p1 = (12)(34)
1
3
2
4
3
1
4
2p2 = (13)(24)
1
3
2
4
1
2
3
4q1 = (1)(23)(4)
1
3
2
4
4
3
2
1 q2 = (14)(2)(3)
TRIÂNGULO QUADRADO
Figura 1 : Simetrias do triângulo e do quadrado
Teorema 7. Seja F uma �gura. Então o conjunto de todas as simetrias de F , com
a operação de composiçã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 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.
7
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,
d�f�1 (z) ; f�1 (w)
�= d
�f�f�1 (z)
�; f�f�1 (w)
��= d (z; w)
Assim f�1 é uma simetria e portanto pertence a G.
A associatividade da composição de simetrias segue diretamente da associatividade
de composição de funções.
Exemplo 8. Temos 3 diferentes tipos de eixos de rotação para um cubo, indicados
na �gura abaixo:
(a) (b) (c)
Figura 2: Os 3 tipos de eixos das simetrias rotacionais do cubo
(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.
8
Assim, as 24 simetrias rotacionais de um cubo são divididas em:
1) A identidade e;
2) 3 rotações de um ângulo de �2pelo tipo de eixo indicado em (a);
3) 3 rotações de um ângulo de � pelo tipo de eixo indicado em (a);
4) 3 rotações de um ângulo de 3�2pelo tipo de eixo indicado em (a);
5) 6 rotações de um ângulo de � pelo tipo de eixo indicado em (b);
6) 4 rotações de um ângulo de 2�3pelo tipo de eixo indicado em (c);
7) 4 rotações de um ângulo de 4�3pelo tipo de eixo indicado em (c).
1.2 Anel de séries de potências formais com coe�cientes com-plexos
Os conceitos a seguir servirão de base para a manipulação de séries e produtos in�nitos
de séries de potências formais.
Entendemos por C [[x]] =�P
n�0 anxn : an 2 C;8n 2 N0
como o anel de séries
de potências formais com respeito às operações usuais de adição e multiplicação.
Consultar [3] para as de�nições básicas e demonstrações dos resultados sobre este
anel.
De�nição 9. De�nimos a função [x�]� : N0 � C [[x]] ! C que extrai o n-ésimo
coe�ciente de f (x) por:
8n 2 N0;8f (x) =1Xm=0
amxm 2 C [[x]] , colocamos [xn] f (x) = [xn]
1Xm=0
amxm := an
É costume denotar o coe�ciente a0 = [x0] f (x) simplesmente por f (0).
Abaixo está a de�nição do que entendemos por convergência de uma seqüência de
séries de potências formais.
De�nição 10. Se hfi (x)ii2N é uma seqüência em C [[x]] e f (x) 2 C [[x]], dizemos
que fi (x) converge para f (x) quando i!1, denotando fi (x)! f (x), se para todo
9
n 2 N0, existir um número � (n) su�cientemente grande tal que
[xn] f (x) = [xn] fi (x) ;8i � � (n)
Em outras palavras; à medida que fazemos i cada vez maior, eventualmente
a seqüência de coe�cientes h[xn] fi (x)ii2N torna-se constante e igual ao coe�ciente
[xn] f (x).
De�nição 11. Dada f (x) 2 C [[x]], f (x) 6= 0, de�nimos o grau de f (x) como sendo
deg f (x) = minn�0
fn : an 6= 0g = minn�0
fn : [xn] f (x) 6= 0g
Observamos que para quaisquer f; g 2 C [[x]] vale a seguinte identidade
deg (f (x) g (x)) = deg f (x) + deg g (x)
De posse do conceito de grau de uma série de potências formais, podemos formular
o conceito de convergência de séries e produtos in�nitos pela seguinte proposição.
Proposição 12. (i) Seja hfiii2N0 uma seqüência em C [[x]]. Então a série in�nitaPi�0 fi (x) converge se, e somente se, limi!1 deg fi (x) =1.
(ii) Seja hfiii2N uma seqüência em C [[x]] com fi (0) = 1;8i 2 N. Então o produto
in�nitoQi�1 fi (x) converge se, e somente se, limi!1 deg (fi (x)� 1) =1.
Dem. A demonstração é trivial.
É essencial observar que ao avaliarmos uma série convergenteP
i�0 fi (x) (ou sim-
ilarmente um produtoQi�1 fi (x)), o coe�ciente de x
n pode ser computado utilizando
apenas processos �nitos. Com efeito, se i é su�cientemente grande, digamos i > � (n),
então deg fi (x) > n é tal que
[xn]
1Xi=0
fi (x) = [xn]
�(n)Xi=0
fi (x)
onde a última expressão claramente envolve uma soma �nita apenas.
A aplicação combinatória mais importante da noção de convergência acima é para
a composição de séries de potências formais, de�nida a seguir.
10
De�nição 13 (Composição de séries de potências). Sejam f (x) ; g (x) 2 C [[x]], com
f (x) =P
j�0 ajxj e g (0) = 0. De�nimos a composição f (g (x)) como sendo a série
f (g (x)) :=1Xj=0
ajg (x)j (1.1)
Proposição 14. A composição de séries em (1:1) é bem de�nida.
Dem. A série composta é bem de�nida uma vez que deg�g (x)j
�= j deg g (x) � j
(pois g (0) = 0), e podemos aplicar a Proposição 12 (i).
Assim podemos ver porque uma expressão como e1+x =P
j�0(1+x)j
j!não faz sen-
tido, pois não converge pela de�nição feita anteriormente. Por outro lado, uma ex-
pressão como eex�1 faz sentido, pois possui a forma f (g (x)) com
f (x) =Xj�0
xj
j!e g (x) =
Xj�1
xj
j!
De�nição 15. Se f (x) 2 C [[x]], de�nimos a derivada formal dfdx(também denotada
por f 0 (x) ou Df (x)) como sendo a série de potências formais
df
dx=
1Xn=0
(n+ 1) an+1xn
A proposição a seguir é imediata, para mais detalhes e outros resultados consulte
[3]:
Proposição 16. (i) (f + g)0 = f 0 + g0
(ii) (fg)0 = f 0g + fg0
(iii) f (g (x))0 = g0 (x) f 0 (g (x))
Os conceitos de convergência para séries formais se estendem de maneira muito
direta para séries de potências em várias variáveis. Várias noções algébricas e topológ-
icas, assim como profundos resultados combinatórios sobre estes anéis podem ser
encontrados em [7] e [8].
11
1.3 Partições de Inteiros
Uma partição do inteiro positivo n é uma soma
n = kl1l1 + kl2l2 + � � �+ klslscom lj; klj 2 [n] ; l1 < � � � < ls
(1.2)
onde temos klj partes iguais a lj para j = 1; : : : ; s, s 2 N. Nesta notação estamos
pensando o número de partes como função de seus tamanhos, klj = k (lj)
De maneira equivalente, uma partição do inteiro positivo n é uma soma
n = k1 + k2 � 2 + � � �+ kn � ncom kn 2 f0g [ [n]
(1.3)
onde temos kj partes iguais a j para j = 1; : : : ; n, n 2 N.
É usual listar uma partição com as partes aparecendo em ordem não-crescente,
adotamos o contrário aqui devido à facilidade de relacioná-las a ciclos de permutações.
O número de partições de um inteiro n é denotado por p (n).
Abaixo consta uma tabela, a título de curiosidade, de alguns valores de p (n).
n p (n) n p (n)1 1 10 422 2 20 6273 3 30 56044 5 40 373385 7 50 2042266 11 60 9664677 15 70 40879688 22 80 157964769 30 90 56634173
Exemplo 17. De acordo com a de�nição das condições (1:2):
10 = 1 + 1 + 2 + 3 + 3, com l1 = 1; k1 = 2; l2 = 2; k2 = 1; l3 = 3; k3 = 2
12 = 3 + 4 + 5, com l1 = 3; l2 = 4; l3 = 5ek1 = k2 = k3 = 1
De acordo com a de�nição das condições (1:3):
10 = 2 � 1 + 1 � 2 + 2 � 3, com k1 = k3 = 2; k2 = 1, kj = 0 se j =2 [3]
12 = 1 � 3 + 1 � 4 + 1 � 5, com k3 = k4 = k5 = 1, kj = 0 se j =2 f3; 4; 5g
12
Teorema 18. O número de partições de n em exatamente k partes é dado pelo coe-
�ciente de zkxn na expansão do produto in�nito
1Yj=1
1
1� zxj
Dem. Para uma demonstração ver [6, Pág. 560]. Observe que este produto in�nito
formal converge, pelas nossas de�nições.
13
Capítulo 2
Grupos de Permutações
2.1 Representação por ciclos disjuntos
Denotamos o conjunto S (X) como o conjunto de todas as permutações do conjunto
X. S (X) munido de composição de funções é um grupo e se #X = n, isto é,
X = fx1; : : : ; xng, temos então que jS (X)j = n!. Denota-se Sn = S ([n]).
Um algoritmo simples ([2, Pág. 30]) fornece para uma permutação � 2 Sn a
seguinte representação por t = t (�) ciclos disjuntos,
� =�j(1)1 j
(1)2 : : : j
(1)l1
��j(2)1 j
(2)2 : : : j
(2)l2
�� � ��j(t)1 j
(t)2 : : : j
(t)lt
�(2.1)
com t 2 N, [n] = f1; 2; : : : ; ng particionado pela seguinte reunião disjunta
[n] =t[i=1
nj(i)1 ; : : : ; j
(i)li
oEsta representação é única a menos de permutações dos ciclos e permutações
cíclicas dos elementos internos de cada ciclo. Portanto obtemos uma representação
da permutação � por meio de ciclos disjuntos. Denominamos um ciclo de comprimento
l simplesmente de l-ciclo; se l = 1 dizemos que o ciclo é um ponto �xo e se l = 2
dizemos que o ciclo é uma transposição. Uma involução é uma permutação composta
apenas de pontos �xos e transposições.
Observe que na representação (2:1) podemos ter ciclos disjuntos de mesmo com-
primento. Assim os números l1; : : : ; lt podem não ser todos distintos. Suponha, sem
perda de generalidade, que no conjunto fl1; : : : ; ltg tenhamos apenas s � t números
distintos, e os redenominamos na ordem crescente l1 < l2 < : : : < ls. Conseqüen-
temente, podemos a�rmar que existem kl1 ciclos de comprimento l1, kl2 ciclos de
comprimento l2, ..., kls ciclos de comprimento ls; onde klj ; lj 2 [n] para j = 1; 2; : : : ; s.
14
Desta forma, podemos concluir que para toda � 2 Sn �xada, temos a unicidade dos
números s = s (�) ; lj = lj (�) e klj (�), onde j = 1; 2; : : : ; s.
De maneira semelhante, podemos tomar l1 = 1; l2 = 2; : : : ; ln = n e fazer kj = 0,
caso não tenhamos ciclos de comprimento j. Claramente os inteiros não-negativos
k1; k2; : : : ; kn são únicos por esta de�nição.
Formalizamos também para permutações a notação já adotada anteriormente para
partições.
De�nição 19. Dada � 2 Sn, de�nimos
(i) ki = ki (�) := o número de ciclos de � com comprimento i;
(ii) k = k (�) := o número total de ciclos de �.
Observe então que, de acordo com a representação (2:1), temos veri�cadas as
equações n =P
i2[n] iki (�) e k = k (�) =P
i2[n] ki (�).
Proposição 20. O sinal de uma permutação � 2 Sn é dado pela fórmula
sgn (�) = (�1)n�k(�)
Dem. Em qualquer livro-texto básico de grupos podemos encontrar o fato de que um
(e apenas um, módulo a identidade sgn (� � �) = sgn (�) � sgn (�)) sinal do conjunto
f+1;�1g está bem de�nido para toda permutação � em Sn; mais ainda, o sinal é +1
sse � for produto de um número par de transposições, e �1 sse � for um produto de
um número ímpar de transposições. Como
(j1j2 : : : jl) = (j1jl) � � � (j1j3) (j1j2)
então um ciclo de comprimento l possui sinal �1 sse seu comprimento é par, o que
mostra que
sgn (�) =Yi par
(�1)ki(�)
15
Como n =P
i iki (�) e k =P
i ki (�) podemos escrever
(�1)n�k(�) = (�1)Pi(i�1)ki(�)
= (�1)Pi par (i�1)ki(�) � (�1)
Pi ímpar (i�1)ki(�)
=Yi par
�(�1)(i�1)
�ki(�)�Y
i ímpar
�(�1)(i�1)
�ki(�)=
Yi par
(�1)ki(�) �Y
i ímpar
1ki(�)
= sgn (�)
e assim demonstramos nossa proposição.
2.2 Ordens de Permutações
Seja G um grupo �nito. A ordem de um elemento g é (bem) de�nida como o menor
inteiro positivo l tal que gl = e. Isto implica que para qualquer múltiplo m = rl de l,
também temos a equação gm = e.
Portanto, uma permutação que seja um l-ciclo possui ordem l e este l-ciclo el-
evado a qualquer múltiplo de l também resulta na identidade. Como os ciclos da
representação de � são disjuntos, para todo l 2 N
�l =�j(1)1 j
(1)2 : : : j
(1)l1
�l �j(2)1 j
(2)2 : : : j
(2)l2
�l� � ��j(t)1 j
(t)2 : : : j
(t)lt
�l(Aqui entende-se o expoente l como sendo a iteração l-ésima da permutação em Sn.)
Assim para encontrar a ordem de �, precisa-se que todos os ciclos de sua rep-
resentação, quando elevados a l, resultem na identidade, o que ocorrerá quando l
for um múltiplo comum de l1; : : : ; lt. Mas pela de�nição de ordem de um elemento,
queremos o menor l que seja um múltiplo comum. Portanto a ordem de � é igual a
mmc [l1; : : : ; lt].
É costume omitir da representação de � os ciclos unitários, porém, será funda-
mental mais adiante, para a determinação do tipo cíclico de uma permutação, que
16
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.
2.3 Números de Stirling
Temos 2 seqüências muito importantes na análise de permutações que de�niremos
a seguir e demonstraremos algumas de suas propriedades. Existe uma miríade de
resultados e identidades envolvendo estas seqüências, e citamos o livro [9, Seção 6.1]
como bom ponto de partida para um estudo deles.
De�nição 21. (i) O número�nk
�de permutações de Sn com exatamente k ciclos
disjuntos é chamado de número de Stirling de primeiro tipo. Em símbolos,�n
k
�= # f� 2 Sn : k (�) = kg
(ii) O número de Stirling do segundo tipo�nk
é de�nido como o número de par-
tições distintas do conjunto [n] em k subconjuntos não-vazios.
A seguir estabelecemos as importantes relações de recorrência que estas duas se-
qüências satisfazem.
Lema 22. (i) Os números�nk
�satisfazem a seguinte relação de recorrência�
n
k
�= (n� 1)
�n� 1k
�+
�n� 1k � 1
�, n; k 2 N
com�nk
�= 0 se n � 0 ou k � 0 exceto c (0; 0) = 1;
(ii) Os números�nk
satisfazem a seguinte relação de recorrência�n
k
�= k
�n� 1k
�+
�n� 1k � 1
�, n; k 2 N
com�nk
= 0 se n � 0 ou k � 0 exceto
�00
= 1.
17
Dem. (i) Aqui de�nimos�00
�= 1, e observamos que uma permutação em Sn deve ter
pelo menos um ciclo, o que implica na igualdade�n0
�= 0;8n 2 N. Se n = 1, então
por estas observações temos trivialmente a recorrência acima satisfeita. Também
de�nimos por conveniência�nk
�= 0 quando n � 0, k < 0.
Seja n > 1, e considere uma permutação � 2 Sn�1 com k ciclos. Podemos inserir
o símbolo n depois de qualquer um dos números 1; : : : ; n � 1 na decomposição de �
por ciclos disjuntos de n � 1 maneiras. O resultado é uma decomposição em ciclos
disjuntos de uma permutação �0 2 Sn com k ciclos, no qual n aparece num ciclo de
comprimento maior ou igual a 2. Portanto existem (n� 1)�n�1k
�permutações �0 2 Sn
com k ciclos para as quais �0 (n) 6= n.
Por outro lado, se escolhermos uma permutação � 2 Sn�1 com k � 1 ciclos,
podemos estendê-la para uma permutação �0 2 Sn com k ciclos satisfazendo � (n) = n,
de�nindo
�0 (i) =
�� (i) , se i 2 [n� 1]
n, se i = n
Portanto existem�n�1k�1�permutações �0 2 Sn com k ciclos para as quais �0 (n) = n,
concluindo a demonstração.
(ii) Por uma argumentação e de�nições semelhantes às feitas inicialmente em (i),
podemos concluir que�nk
= 0 se n � 0 ou k � 0 exceto
�00
= 1.
Considere um conjunto com n > 1 objetos particionado em k subconjuntos (não-
vazios). Podemos colocar o último objeto tanto num subconjunto unitário de�n�1k�1
maneiras, ou podemos colocá-lo junto de outro subconjunto dos outros n� 1 objetos
anteriores. Existem k�n�1k
possibilidades para este último caso. Com efeito, cada
uma das�n�1k
maneiras de distribuirmos os primeiro n � 1 objetos em k subcon-
juntos, nos fornece k subconjuntos aos quais o n-ésimo objeto pode se unir. E assim
concluímos a demonstração.
18
Teorema 23. Seja x uma variável e n � 0 �xo. EntãonXk=0
�n
k
�xk = x (x+ 1) � � � (x+ n� 1) = xn
enXk=0
�n
k
�xk =
nXk=0
�n
k
�x (x� 1) � � � (x� k � 1) = xn
Dem. De�nimos Fn (x) = xn =Pn
k=0 f (n; k)xk. Claramente f (0; 0) = 1 pois x0 =
1, e f (n; k) = 0 se n < 0 ou k < 0. Mais ainda, como Fn (x) = (x+ n� 1)Fn�1 (x),
temos
Fn (x) =nXk=1
f (n� 1; k � 1)xk + (n� 1)n�1Xk=0
f (n� 1; k)xk
e isto implica que
f (n; k) = (n� 1) f (n� 1; k) + f (n� 1; k � 1)
Assim f (n; k) satisfaz a mesma relação de recorrência e condições iniciais de�nk
�, e
portanto são idênticas.
De maneira completamente análoga podemos derivar a segunda identidade.
Estas analogias observadas entre os números de Stirling de primeiro e segundo
tipo não são coincidências, e o teorema a seguir pode ser demonstrado facilmente.
Teorema 24. (i) xn = (�1)n (�x)n
(ii) Os números de Stirling de primeiro e segundo tipo são de certa forma inversos
um do outro, satisfazendo a fórmula de inversão
nXk=0
(�1)n�k�n
k
��k
m
�=
nXk=0
(�1)n�k�n
k
��k
m
�= �mn,
onde �mn é o símbolo � de Kronecker.
(iii) Sejam D = ddz; # = zD operadores diferenciais. Então temos as seguintes
19
fórmulas operacionais que os relacionam
#n =nXk=0
�n
k
�zkDk
znDn =
nXk=0
�n
k
�(�1)n�k #k
Dem. Ver [9, Seção 6.1] para (i) e (ii), e o exercício 6.13 do mesmo livro para (iii).
20
Capítulo 3
Índice de Ciclos
3.1 Tipo cíclico, Índice de ciclos e partições de Inteiros
A de�nição a seguir captura a estrutura cíclica de uma permutação, e será muito
importante nos desenvolvimentos posteriores.
De acordo com a representação (2:1) por ciclos disjuntos, de�nimos
De�nição 25. O tipo cíclico de � 2 Sn é o monômio TC (�) determinado pelo
produto
TC (�) =tYi=1
xli (3.1)
De�nição 26. Se G é um grupo de permutações, o índice de ciclos de G, denotado
Z (G), é de�nido como sendo o polinômio
Z (G) =1
jGjX�2G
TC (�)
A soma dos coe�cientes do polinômio acima deve ser igual a 1, uma vez que temos
jGj termos monomiais com coe�cientes unitários na soma, divididos pelo fator jGj.
Pelas observações feitas na seção 2:1, temos que o tipo cíclico de � toma as
seguintes formas, mais intuitivas e explícitas,
TC (�) = xkl1l1xkl2l2� � �xklsls = xk11 x
k22 � � �xknn
onde cada natural klj é o número de ciclos de comprimento lj para j = 1; : : : ; s e
k (�) =P
j klj é o total de ciclos. Na segunda representação do tipo cíclico, temos kj
como sendo o número de ciclos de comprimento j, podendo algum kj eventualmente
ser nulo. É também muito útil representar o tipo cíclico como o vetor (k1; k2; : : : ; kn).
21
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 kl1l1+kl2l2+
� � �+ klsls = n, e pela ordenação 1 � l1 < l2 < � � � < ls � n , e de�nições de klj , temos
então uma partição do inteiro n = kl1l1 + � � �+ klsls.
Reciprocamente, se temos uma partição do inteiro n dada por
n = kl1l1 + kl2l2 + � � �+ klslscom lj; klj 2 [n] ; l1 < � � � < ls
onde temos klj partes iguais a lj para j = 1; ::; s, então é possível encontrar uma
permutação � 2 Sn com tipo cíclico TC (�) = xkl1l1xkl2l2:::x
klsls. Na verdade podem
existir 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 é devido a Cauchy e foi adaptada da
referência [14, Págs. 71-72].
Teorema 27. Seja uma partição de n, dada por n = kl1l1 + kl2l2 + � � � + klsls, com
lj; klj 2 [n] e l1 < l2 < ::: < ls. Então existem
n!
lkl11 kl1 !l
kl22 kl2 ! � � � l
klss kls !
permutações � 2 Sn com tipo cíclico TC (�) = xkl1l1xkl2l2� � �xklsls . De forma mais sim-
pli�cada; dado um tipo cíclico xk11 xk22 � � �xknn temos
h (k1; : : : ; kn) =n!
k1!2k2k2! � � �nknkn!
permutações em Sn com este tipo cíclico.
Dem. Seja h o número de permutações � 2 Sn satisfazendo TC (�) = xkl1l1xkl2l2� � �xklsls ,
isto é, contendo klj ciclos de comprimento lj para j = 1; : : : ; s.
Vamos considerar as permutações com o tipo cíclico desejado, decompostas em seus
ciclos componentes. Primeiro listamos os kl1 ciclos de comprimento l1 e represen-
tamos cada ciclo por l1 quadrados, depois listamos os kl2 ciclos de comprimento l2,
22
e representamos cada ciclo por l2 quadrados e assim sucessivamente, até �nalmente
listarmos os kls ciclos de comprimento ls e seus quadrados.
s
8>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>:
kl1z }| {l1z }| {� � �
l1z }| {� � � � � �
l1z }| {� � �
kl2z }| {l2z }| {� � �
l2z }| {� � � � � �
l2z }| {� � �
......
...klsz }| {
lsz }| {� � �
lsz }| {� � � � � �
lsz }| {� � �
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, TC (�) = x1x22x3, 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 �xado anteriormente.
Como P possui kl1 ciclos de comprimento l1, a �m de produzirmos P no preenchi-
mento, suas kl1 l1-uplas de elementos devem ser colocados nos kl1 blocos de l1 quadra-
dos cada. Cada l1-upla pode ser colocada em qualquer ordem entre os kl1 blocos, assim
temos kl1 ! maneiras de fazer isso. Cada um dos kl1 blocos, pode ser rotacionado ci-
clicamente e isto pode ser feito de l1 maneiras por bloco, pois seu comprimento é l1.
23
Assim temos lkl11 possibilidades para as rotações cíclicas dos elementos dos blocos e
portanto no total temos kl1 !lkl11 maneiras de obtermos os kl1 ciclos de comprimento
l1 de P . O mesmo raciocínio pode ser aplicado aos demais ciclos de P , isto é, temos
klj !lkljj maneiras de obter os klj ciclos de comprimento lj para j = 1; : : : ; s. Portanto,
temos um total de
kl1 !lkl11 kl2 !l
kl22 � � � kls !lklss
permutações que quando colocadas nos quadrados geram os ciclos de P . Assim, se
preenchermos 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. Como
temos, por de�nição, h permutações de Sn com este tipo cíclico, podemos concluir
que
h � kl1 !lkl11 kl2 !l
kl22 � � � kls !lklss = n!
de onde segue o resultado.
Corolário 28. Existe uma correspondência biunívoca entre os tipos cíclicos dos el-
ementos 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.
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].
Os resultados a seguir relacionam o tipo cíclico à relação de conjugação em Sn.
De�nição 29. Duas permutações �1, �2 2 Sn são conjugadas se existir h 2 Sn tal
que �2 = h�1h�1
Teorema 30. Duas permutações possuem o mesmo tipo cíclico se, e somente se, elas
são conjugadas.
24
Dem. Suponha que para algum h 2 Sn, �2 = h�1h�1. Seja (x1x2 : : : xk) um ciclo
de �1, tal que �1 (xi) = xi+1 para i 2 [k � 1], e �1 (xk) = x1. Seja yi = h (xi) para
i 2 [k]. Então para i 2 [k � 1], temos que
�2 (yi) = (h�1)�h�1 (yi)
�= (h�1) (xi) = h (�1 (xi)) = h (xi+1) = yi+1
e de maneira similar �2 (yk) = y1. Portanto (y1y2 : : : yk) é um ciclo de �2. Assim
obtemos uma decomposição em ciclos de �2 dos ciclos de �1, substituindo cada ponto
pela sua imagem por h. Desta forma o tipo cíclico é o mesmo para �1 e �2.
Reciprocamente, suponha que �1 e �2 possuam o mesmo tipo cíclico. Calculamos
a decomposição por ciclos de cada uma, e escrevemos a de �2 abaixo da de �1, de
tal forma que os ciclos de mesmo comprimento correspondam verticalmente. Agora
seja h a permutação obtida pela aplicação que associa cada ponto da decomposição
de �1 ao ponto verticalmente abaixo dele. Então �2 = h�1h�1 pelos mesmos cálculos
acima.
O teorema abaixo fornece uma fórmula fechada para os coe�cientes do índice de
ciclos de Sn:
Teorema 31. Temos a seguinte expressão geral para o índice de ciclos do grupo
simétrico Sn
Z (Sn) =X
kl1 l1+���+kls ls=nlj ;klj2[n]
1
lkl11 kl1 !l
kl22 kl2 !:::l
klss kls !
xkl1l1xkl2l2:::x
klsls
=1
n!
Xk1+k2�2+:::+kn�n=n
kj2f0g[[n]
h (k1; : : : ; kn)xk11 x
k22:::xknn
onde a soma é efetuada sobre todas as partições do inteiro n.
Dem. Este resultado sai diretamente do Teorema 27 e da De�nição 26, do índice
de ciclos. Basta somar nos p (n) diferentes tipos cíclicos possíveis para as permutações
de Sn.
25
Corolário 32 (Identidade de Cauchy).Xk1+k2�2+:::+kn�n=n
kj2f0g[[n]
1
1k1k1!2k2k2!:::nknkn!= 1
Dem. Pela observação feita na De�nição 26, a soma dos coe�cientes no Teorema
31 deve ser 1. Isto conclui a demonstração.
Acima encontramos uma expressão para o índice de ciclos de Sn somando sobre as
partições do inteiro n. A seguir demonstramos uma fórmula fechada para o índice de
ciclos do grupo cíclico Cn, desta vez somando sobre os divisores de n. De posse desta
última, também deduzimos uma expressão para o índice de ciclos do grupo diedral
D2n.
Lema 33. O grupo Cn (cíclico de ordem n) contém para cada divisor d de n, � (d)
elementos de ordem d, onde � é a função totiente de Euler. Cada um desses elementos
possui n=d ciclos de comprimento d.
Dem. Podemos identi�car Cn com o grupo (Zn;+n) =�0; 1; :::; n� 1
�. A ordem de
uma classe m, de congruência módulo n , é o menor inteiro positivo x tal que
xm =
x somandosz }| {m+n m+n :::+n m = 0
e esta igualdade ocorre se, e somente se, existir algum y 2 N tal que
xm = ny = yn (3.2)
Dividimos ambos os lados desta equação por (m;n) para obter
xm
(m;n)= y
n
(m;n)
Como dividimos m e n pelo máximo de seus divisores comuns, temos�m
(m;n);
n
(m;n)
�= 1
26
e portantom
(m;n)jy e n
(m;n)jx
o que signi�ca que existem k; l 2 N tais que
m
(m;n)k = y e
n
(m;n)l = x (3.3)
Assim, a menor solução positiva x de (3:2) é obtida colocando l = 1 em (3:3), a
saber,
x =n
(m;n)e y =
m
(m;n)
e portanto a ordem de m é n= (m;n).
Além disso, dado um divisor d de n, desejamos saber quantas classes distintas
m possuem ordem n= (m;n) = d. Para um tal m temos m = (m;n) y onde y deve
satisfazer (y; d) = 1. Temos � (d) escolhas para y nestas condições, cada uma delas
originando um único m = ny=d. Isso encerra a demonstração.
Teorema 34. O índice de ciclos de Cn é dado por
Z (Cn) =1
n
Xdjn
� (d)xn=dd
onde a soma é efetuada nos divisores d de n.
Dem. Imediata a partir do Lema 33 anterior e da de�nição do índice de ciclos.
Corolário 35. O índice de ciclos do grupo diedral D2n é dado por
Z (D2n) =1
2(Z (Cn) +Rn)
onde
Rn =
8<: x1xn�12
2 , se n � 1 (mod 2)12
�xn22 + x
21x
(n�2)2
2
�, se n � 0 (mod 2)
27
Dem. 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�1)2transposições (2-ciclos); enquanto que se
n � 0 (mod 2), temos n2re�exões formadas por n
2transposições e n
2re�exões formadas
por 2 pontos �xos e (n�2)2
transposições. Desta forma obtemos o resultado.
O índice de ciclos, apesar de caracterizar várias propriedades combinatórias de
um grupo, não o caracteriza completamente em sua tábua de Cayley. Pólya forneceu
um exemplo de 2 grupos não isomorfos com o mesmo índice de ciclos. Estes 2 grupos
possuem ordem p3, ambos com a propriedade de que todos os seus elementos, exceto
a identidade, possuem ordem p; entretanto um deles é abeliano enquanto o outro é
não-abeliano.
Este exemplo foi dado em [10, Pág. 176], mas podemos encontrar uma tradução
da construção em [5, Pág. 37].
3.2 A função geradora para o índice de ciclos de Sn e apli-cações
No teorema fundamental abaixo está a função geradora ordinária para o índice de
ciclos de Sn, onde é conveniente de�nirmos Z (S0) = 1. Esta função geradora, apesar
da grande quantidade de informação que carrega, possui uma fórmula fechada muito
elegante.
Teorema 36. Seja x = (x1; x2; : : :), então a função geradora ordinária para Sn, em
série de potências formais é dada por
C (x; z) :=
1Xn=0
Z (Sn;x1; : : : ; xn) zn = exp
1Xj=1
xjzj
j
!
Dem. Para a convergência do membro direito, primeiro observamos que
exp
1Xj=1
xjzj
j
!= f (g (z)) ,
28
com f (z) = exp z =1Xj=0
zj
j!e g (z) =
1Xj=1
xjzj
j, com g (0) = 0.
Assim temos pela Proposição 14 que a composta é bem de�nida. Portanto1Xn=0
Z (Sn;x1; : : : ; xn) zn =
1Xn=0
Xk1+k2�2+:::+kn�n=nk1�0;k2�0;:::;kn�0
1
1k1k1!2k2k2!:::nknkn!xk11 x
k22:::xknn z
n
=X
k1�0;k2�0;:::
xk11 zk1
1k1k1!
xk22 z2k2
2k2k2!
xk33 z3k3
3k3k3!� � �
=Xk1�0
(x1z)k1 1
k1!
Xk2�0
�x2z
2
2
�k2 1k2!
Xk3�0
�x3z
3
3
�k3 1k3!� � �
= ezx1ez2x22 e
z3x33 � � �
= exp
1Xj=1
xjzj
j
!
Apresentamos a seguir uma série de aplicações da função geradora obtida no Teo-
rema 36.
Vale observar que todas as substituições abaixo estão em conforme com a existên-
cia da composta demonstrada na dedução da função geradora para C (x; z).
Corolário 37. Podemos obter novamente a primeira parte do Teorema 23 pela
função geradora de C (x; z), isto é,nXk=0
�n
k
�xk = xn
Dem. Se �zermos a substituição
x1 = x2 = � � � = x
no índice de ciclos de Sn, estaremos interessados em permutações de Sn que possuem
k (�) = k1 + � � �+ kn ciclos, independentemente de seus comprimentos. Em símbolos
esta a�rmação signi�ca que
Z
Sn;
nz }| {x; : : : ; x
!=1
n!
nXk=0
�n
k
�xk
29
Portanto, pelo Teorema 36,
1Xn=0
1
n!
nXk=0
�n
k
�xk
!zn = exp
1Xj=1
xzj
j
!
= exp
�x log
�1
1� z
��= exp
�log
�1
1� z
��x=
�1
1� z
�x=
1Xn=0
xn
n!zn
onde a última passagem segue por uma aplicação do teorema binomial ver [11, Págs.
122-123] e De�nição 2, da potência fatorial crescente.
Corolário 38. O número d (n; k) de permutações de Sn contendo exatamente k ciclos,
nenhum dos quais é um ponto �xo, é dado pela função geradora
nXk=0
d (n; k)xk =nXk=0
(�1)k�n
k
�xkxn�k
com a seguinte fórmula para d (n; k)
d (n; k) =kXj=0
(�1)j�n
j
��n� jk � j
�Dem. De acordo com a de�nição de d (n; k), vemos que este número é o coe�ciente
de xk em
Z
Sn; 0;
n�1z }| {x; : : : ; x
!.
30
Assim, pelo Teorema 36 e pela demonstração do Corolário 37 temos1Xn=0
1
n!
nXk=0
d (n; k)xk
!zn = exp
1Xj=2
xzj
j
!
= exp
�x
�log
1
1� z
�� z�
=
�1
1� z
�xexp (�xz)
=
1Xn=0
xn
n!zn
1Xn=0
(�1)n xn
n!zn
=1Xn=0
nXk=0
(�1)k�n
k
�xkxn�k
zn
n!
onde na última manipulação, multiplicamos duas funções geradoras exponenciais
em séries de potências.
Obtemos a fórmula para d (n; k), substituindo a expressão para função geradora
xn�k dos números de Stirling de primeiro tiponXk=0
d (n; k)xk =nXk=0
(�1)k�n
k
�xkxn�k
=nXk=0
(�1)k�n
k
�xk
n�kXj=0
�n� kj
�xj
=nXk=0
n�kXj=0
(�1)k�n
k
��n� kj
�xj+k
=
nXk=0
nXj=k
(�1)k�n
k
��n� kj � k
�xj
=
nXj=0
jXk=0
(�1)k�n
k
��n� kj � k
�xj
=nX
k0=0
k0Xj0=0
(�1)j0�n
j0
��n� j0k0 � j0
�!xk
0
onde na penúltima passagem invertemos a ordem dos somatórios e na última
aplicamos as mudanças de variáveis mudas j ! k0 e k ! j0. Desta forma concluímos
a demonstração.
31
Corolário 39. Seja m 2 N, �xado. O número de permutações de Sn cuja m-ésima
potência é a identidade possui como função geradora exponencial
exp
0@Xdjm
xd
d
1ADem. Segundo as observações feitas anteriormente, se �m = e, então todos os seus
comprimentos de ciclos devem ser divisores de m. Desta forma, no índice de ciclos de
Sn fazemos esta triagem colocando
xj =
�1, se jjm0, c.c.
e obtemos diretamente do Teorema 36 a função geradora requerida.
Corolário 40. O número de involuções tn em Sn é dado pela função geradoraXn�0
tnn!xn = ex+
12x2
Dem. Basta tomar m = 2 no Corolário 39 e observar que apenas a identidade e e
transposições t satisfazem t2 = e.
3.3 Interpretação probabilística do Índice de Ciclos de Sn
Como n! é o número total de permutações de Sn e h (k1; : : : ; kn) é o número delas que
possui tipo cíclico k = (k1; : : : ; kn), em vista do Teorema 31, podemos interpretar o
índice de ciclos
Z (Sn;x1; : : : ; xn) =X
k1+k2�2+:::+kn�n=nkj2f0g[[n]
�1
n!h (k1; : : : ; kn)
�xk11 x
k22:::xknn
de forma probabilística, colocando xk = xk11 xk22:::xknn ,
Z (Sn;x1; : : : ; xn) =X
k1+k2�2+:::+kn�n=nkj2f0g[[n]
Prob (k; n)xk
32
onde Prob (k; n) é a probabilidade de que uma permutação de n símbolos possui o
tipo cíclico k.
A seguir demonstramos um lema elementar, que nos permitirá extrairmos infor-
mações analíticas da função geradora formal para o índice de ciclos de Sn.
Lema 41. SejaP
j bj uma série convergente no sentido usual. Então na expansão
em série de potências da função
1
1� zXj
bjzj =
Xn
�nzn
temos que limn �n existe e é igual aP
j bj.
Dem. Por manipulação de séries de potências (ver [12, Pág. 37]), temos que �n é a
soma dos bj para j � n. A última soma claramente aproxima o limite requerido.
Sejam jzj < 1 e T um conjunto (�nito ou in�nito) de inteiros positivos, com a
propriedade que Xt2T
1
t<1
Na função geradora C (x; z) colocamos todos xi = 1 para todo i =2 T . Isto signi�ca
que não estaremos interessados nos comprimentos de ciclos que não estão no conjunto
T . Os demais são arbitrários, e portanto
C (x; z) =1Xn=0
Z (Sn;x1; : : : ; xn) zn
= exp
Xi2T
xizi
i+Xi=2T
zi
i
!
= exp
Xi2T
(xi � 1)i
zi + log1
1� z
!
=1
1� z exp Xi2T
(xi � 1)i
zi
!
33
Pelo Lema 41, escolhendo os xi limitados para i 2 T , temos que o coe�ciente de
zn na última expressão acima se aproxima do limite
exp
Xi2T
(xi � 1)i
!quando n!1. Assim temos provado que limn!1 Prob (k; n) existe, e concluímos o
seguinte resultado:
Teorema 42. Seja T um conjunto de inteiros positivos tais queP
t2T1tconverge, e
seja k um vetor de tipo cíclico �xado. Então a probabilidade de que o tipo cíclico
de uma permutação qualquer escolhida ao acaso, coincida com k em todos os seus
componentes cujos índices pertençam a T existe e é igual a
e�(Pt2T
1t )�xk�exp
Xt2T
xtt
!=
1Qt2T
�e1t tktkt!
� (3.4)
Exemplo 43. Tome T = f1g, o que signi�ca que estamos interessados apenas em
pontos �xos. Então por (3:4), a probabilidade de que uma permutação escolhida aleato-
riamente tenha exatamente k pontos �xos é dada por 1k!e;8k � 0. Obviamente as
permutações de
Exemplo 44. Tome T = frg, então a probabilidade de que uma permutação escolhida
aleatoriamente tenha exatamente k r-ciclos é dada por
1
e1r rkk!
;8k � 0:
Exemplo 45. Seja T = fr; sg. A probabilidade de que uma permutação escolhida
aleatoriamente possua exatamente kr r-ciclos e exatamente ks s-ciclos é
1
e1r+ 1s rkrskskr!ks!
:
De�nição 46. Se Re (s) > 1, de�nimos a função zeta de Riemann por
� (s) =
1Xn=1
1
ns
34
Exemplo 47. Seja s 2 N, s � 2. Qual é a probabilidade de que uma permutação es-
colhida aleatoriamente não possua ciclos de comprimentos que sejam s-ésimas potên-
cias naturais?
Tomamos Ts = fns : n 2 Ng e k com componentes quaisquer cujos índices não
pertençam a Ts (isto é, que não sejam s-ésimas potências). Primeiramente observa-
mos que Xt2Ts
1
t=
1Xn=1
1
ns= � (s)
converge para s � 2. Pelo Teorema 42, esta probabilidade é dada por
1Qt2Ts
�e1t
� = 1
ePt2Ts
1t
= e��(s)
Para s = 2 é bem sabido que � (2) = �2
6. Desta forma, a probabilidade de que
uma permutação escolhida ao acaso não possua ciclos de comprimentos que sejam
quadrados é de
e��2
6 � 0; 193
aproximadamente 20%.
35
Capítulo 4
Ação de Grupos e Colorações
4.1 Introdução
Considere um tabuleiro de xadrez 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 3 : 16 colorações de um tabuleiro de xadrez 2� 2, nas cores preto e branco.
36
Do total listado acima, podemos inferir os seguintes conjuntos de padrões equiv-
alentes:fC1g
fC2; C3; C4; C5gfC6; C7; C8; C9gfC10; C11g
fC12; C13; C14; C15gfC16g
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.
Figura 4 : Um padrão não pode ser levado no outro por rotações
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).
Queremos descrever a situação geral onde temos uma interação entre um grupo
G e um conjunto X não vazio.
Por motivos didáticos, devemos manter este exemplo dos tabuleiros de xadrez
em mente nos desenvolvimentos a seguir. Utiliza-se largamente a referência [1] nas
37
visualizações e construções dos conceitos que permeiam todo este trabalho.
4.2 Ação de grupos
De�nição 48. 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 49. 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 50. Tome G como o grupo das simetrias rotacionais de um cubo, e X o
conjunto de colorações das faces do cubo usando as cores vermelho, preto e verde.
Exemplo 51. 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
38
Esta ação é chamada de conjugação e o elemento do grupo gxg�1 é chamado de
conjugado de x, como visto anteriormente.
Abaixo encontra-se um lema fundamental para ações de grupos.
Lema 52. Seja G um grupo que age no conjunto X. Então para todo g 2 G, x; y 2 X,
temos
g � x = y () g�1 � y = x
Dem. Sejam g 2 G, x; y 2 X e suponha que g � x = y. Então
g�1 � 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.
4.3 Colorações e ações de grupos
Primeiro, como um exemplo mais concreto, consideramos novamente o tabuleiro de
xadrez 2� 2.
1 2
3 4
Figura 5 : Tabuleiro 2� 2 genérico
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
39
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
Figura 6 : Coloração C10
determinada por
f10 (�1) = f10 (�4) = preto
f10 (�2) = f10 (�3) = branco
Como utilizaremos este exemplo do tabuleiro 2� 2 de maneira recorrente, é con-
veniente denotar por fj a coloração correspondente ao diagrama Cj da Figura 3.
Procedemos agora para a de�nição geral do conceito.
De�nição 53. Sejam C e D dois conjuntos não-vazios (em geral são diferentes tam-
bém), e X = F (D;C) = CD, o conjunto de todas as funções com domínio D e
contradomínio C. Dizemos então que qualquer função f 2 X é uma coloração de D
em C.
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
40
Exemplo 54. Se D é um conjunto de contas ou pedrinhas, podemos ter C como
conjunto das formas fquadrada; redonda; triangularg.
Exemplo 55. Se D é um conjunto de quadrados de um tabuleiro 2� 2, podemos ter
C como o conjunto das cores fpreto; brancog
Agora relacionamos o conceito de ações de grupos com colorações.
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 (4.1)
Teorema 56. A fórmula (4:1) 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,
e � f = f � e�1 = 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,
�2 � (�1 � f) = �2 ��f � ��11
�=
�f � ��11
�� ��12
= f ����11 � ��12
�= f � (�2 � �1)�1
= (�2 � �1) � f
e portanto (A2) também é válido concluindo a demonstração.
41
Capítulo 5
Órbitas e Estabilizadores
5.1 Órbitas e relações de equivalência
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.
Lembramos que consideramos X como um conjunto �nito.
De�nição 57. 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 � Gy () 9g 2 G tal que g � x = y
Para simpli�car a notação, vamos denotar esta relação simplesmente por �.
Lema 58. A relação � no conjunto X é uma relação de equivalência.
Dem. Mostramos que � é 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 � x, e � é re�exiva.
Se tivermos que x � y, então existe g 2 G com g � x = y. Como G é grupo, existe
o inverso g�1 e pelo Lema 52 temos que g�1 � y = x e portanto y � x. Assim � é
simétrica.
42
Suponhamos agora que x � y e y � 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 � z. Isto mostra que � é 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 � são chamadas de órbitas da ação
do grupo. A órbita à qual o elemento x pertence é denotada por Ox. Assim
Ox = Oy () x � y
e como x � y () y = g � x para algum g 2 G, segue que
Ox = fg � x : g 2 Gg
No Exemplo 51, as classes de equivalência são chamadas de classes de conjugação
do grupo em questão. Assim, se G = Sn, existe um total de p(n) classes de conjugação
em vista dos resultados anteriores.
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.
5.2 Estabilizadores
Na seção 4.2, 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.
43
Assim, dado x 2 X, chamamos de estabilizador de x, o conjunto dos elementos
de G que na ação de grupo �xam x.
De�nição 59. O estabilizador Sx de x é de�nido por
Sx = fg 2 G : g � x = xg
O lema a seguir mostra que para qualquer x 2 X, o estabilizador Sx é um subgrupo
de G.
Lema 60. 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 52 temos que g�1 � x = x
o que mostra que g�1 também está em Sx. Assim Sx é um subgrupo de G.
Abaixo consta um quadro com os estabilizadores e as órbitas das colorações de
um tabuleiro de xadrez 2� 2:
44
Elemento de X Estabilizador ÓrbitaC1 fe; a1; a2; a3; p1; p2; q1; q2g fC1gC2C3C4C5
fe; q1gfe; q2gfe; q1gfe; q2g
fC2; C3; C4; C5g
C6C7C8C9
fe; p2gfe; p1gfe; p2gfe; p1g
fC6; C7; C8; C9g
C10C11
fe; a2; q1; q2gfe; a2; q1; q2g
fC10; C11g
C12C13C14C15
fe; q2gfe; q1gfe; q2gfe; q1g
fC12; C13; C14; C15g
C16 fe; a1; a2; a3; p1; p2; q1; q2g fC16g
Observe que em todas as linhas (elementos x de X) temos a equação #(Ox) �
#(Sx) = 8. Isto não é uma coincidência e a seguir está um teorema a respeito, muito
importante para nosso estudo.
Teorema 61 (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 60, temos que Sx é um subgrupo de G, e pelo teorema de Lagrange
segue que
jG : Sxj �#(Sx) = # (G)
Assim precisamos mostrar que
#(Ox) = jG : Sxj (5.1)
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 (5:1) mostrando que a
45
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 mostrar que, para
todo g; h 2 G;
gSx = hSx () g � x = h � x
Sejam g; h 2 G. Então
gSx = hSx () h�1g 2 Sx, pelo Lema 60() (h�1g) � x = x, pela de�nição de Sx() h�1 � (g � x) = x, por (A2)() g � x = h � x, pelo Lema 52
Corolário 62. 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 está um
resultado, que será modi�cado adiante para a obtenção do lema de Burnside, que
fornece uma fórmula para o número de diferentes órbitas da ação.
Teorema 63. Seja G um grupo �nito agindo em X. Então o número de órbitas
distintas é dado por1
# (G)
Xx2X
#(Sx)
Dem. Suponhamos que existam m órbitas distintas Ox1 ; :::; Oxm. Se 1 � j � m,
46
temos para a j-ésima órbita queXx2Oxj
#(Sx) =Xx2Oxj
#(G)
# (Ox), pelo Teorema Órbita-Estabilizador
= #(G)Xx2Oxj
1
#�Oxj� , pois Ox = Oxj para todo x 2 Oxj
=#(G)
#�Oxj� Xx2Oxj
1
= # (G)
Assim, somando para todas as órbitas obtemos,
Xx2X
#(Sx) =mXj=1
Xx2Oxj
#(Sx) =mXj=1
#(G) = m#(G)
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.
5.3 Objetos rotulados e não-rotulados
Ações de grupos e estabilizadores são úteis no discernimento entre objetos rotulados
e não-rotulados. Nesta seção, objetivamos um desenvolvimento não tão formal destes
conceitos, a título de exposição. Para maiores detalhes, ver [2, Seções 14.1-14.4].
Podemos considerar um objeto como um par (X;S) onde X é um conjunto e S
uma estrutura qualquer em X, que não precisa ser especi�cada. S pode consistir
de pares ordenados ou não-ordenados (isto é, grafos ou digrafos) de elementos de
X, um conjunto de subconjuntos ou partições de X, etc. O importante é que, dado
uma permutação g de X, deva existir uma maneira natural de aplicar g em S. Por
47
exemplo, se (X;S) é um grafo, então aplicamos g a cada aresta em S para obter o
conjunto de arestas gS.
Uma permutação g de X é um automor�smo de (X;S) se gS = S. O grupo
de automor�smos de (X;S) é o conjunto Aut (X;S) de todos os automor�smos de
(X;S).
Seja C uma classe de objetos com estruturas num conjunto [n]. Os elementos
de C podem consistir de grafos, famílias de conjuntos, etc. Dizemos que dois objetos
rotulados C e C 0 em C são contados como o mesmo objeto não-rotulado se, e somente
se, eles são isomorfos, isto é, se existir uma permutação de Sn que mapeie a estrutura
de C na de C 0.
Consideramos então a ação de Sn na classe C de objetos rotulados (entendendo
que as permutações de Sn agem nas respectivas estruturas dos pares). Nesta ação,
objetos não rotulados correspondem às órbitas, e o estabilizador de um objeto C é
na verdade seu grupo de automor�smos; isto é, o conjunto de todas as permutações
de Sn que o �xam.
Teorema 64. (i) O número de diferentes rotulações de um objeto C 2 C é igual a
n!
jAut (C)j
(ii) Suponha que existamM objetos rotulados em objetos não rotulados, C1; : : : ; Cm
em C. EntãomXj=1
1
jAut (Cj)j=M
n!
Dem. (i) Pelo Teorema Órbita-Estabilizador temos que 8C 2 C, jOC j jSC j = jSnj =
n!. A cardinalidade da órbita representa o número de objetos rotulados de C que são
isomorfos ao objeto C. Assim desejamos saber o valor de
jOC j =n!
jSC j=
n!
jAut (C)j
48
(ii) TemosmXj=1
1
jAut (Cj)j=
mXj=1
��OCj ��e como existem m objetos não rotulados em C, temos m órbitas no total. Desta
forma, como temos M objetos rotulados no total, e as órbitas particionam C, segue
imediatamente quemXj=1
��OCj �� = jCj =M
5.4 O Lema de Burnside
Apesar do 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.
A �m de se obter a versão desejada para o número de órbitas, considere a �gura
abaixo,
49
Elementos de X
Elem
ento
s de
Ggi
xj
Figura 7 : Elementos de G versus Elementos de X
onde as linhas correspondem a elementos de G e as colunas a elementos de X.
Marca-se 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 .
Assim, o número de marcas em uma coluna j é #�Sxj�e portanto o número total
de marcas na tabela éP
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 65. Seja G um grupo agindo em X, de�nimos o Fix de g 2 G como
Fix (g) = fx 2 X : g � x = xg
Observe que Fix (g) é igual a k1 (g), o número de pontos �xos da permutação g.
50
Se somarmos o total de marcas de cada linha, obtemos todas as marcas da tabela,
isto é, Xg2G
#(Fix (g)) =Xx2X
#(Sx)
Demonstramos então o lema, fundamental em todo este estudo:
Teorema 66 (Lema de Burnside). Se G é um grupo �nito agindo em um conjunto
X, então o número de órbitas distintas é dado por
1
# (G)
Xg2G
#(Fix (g))
5.5 Aplicações do Lema de Burnside
Problema 67. 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 68. Neste problema, o conjunto X de colorações é formado pelas n! per-
mutaçõ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 de 2�n. 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 Fix (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 lema de Burnside temos então
que o número de permutações circulares de n elementos é dado por
1
n
0@n! + n�1 zerosz }| {0 + :::+ 0
1A = (n� 1)!
51
Problema 69. De quantas maneiras diferentes podemos pintar as faces de um cubo,
utilizando c cores diferentes? Calcule o número de pinturas utilizando as cores ver-
melho, preto e verde.
Solução 70. 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
8 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 ) Fix (e) = c6;
(2) Cada rotação de �2pelo eixo indicado em (a) possui 1 ciclo de comprimento 4 e
2 ciclos de comprimento 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 diferentes 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 �2indicada 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 comprimento 1. Pelas mesmas considerações feitas no item (2) acima,
concluímos pelo princípio multiplicativo que o Fix 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 3�2pelo eixo de (a) é equivalente a uma de ��
2pelo 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;
(6) Cada rotação de 2�3pelo eixo indicado em (c) possui 2 ciclos de comprimento
52
3. Portanto temos uma contribuição de 4c2;
(7) Uma rotação de 4�3é equivalente a uma de �2�
3, e por simetria temos a mesma
contribuição do item (6), isto é, 4c2.
Pelo lema de Burnside, temos então que o número de pinturas distintas das faces
do cubo utilizando c cores é
1
24
�c6 + 3c3 + 3c4 + 3c3 + 6c3 + 4c2 + 4c2
�=1
24
�c6 + 3c4 + 12c3 + 8c2
�Para 3 cores, basta substituir c = 3 no polinômio acima para obter 57 pinturas dis-
tintas.
Problema 71. Quantas moléculas orgânicas diferentes da forma
C XX
X
X
Figura 8: Molécula com C no centro e 4 ligações
existem, onde C é um átomo de carbono e cada X denota qualquer um dos 4
componentes CH3 (metil), C2H5 (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 72. Considere a �gura abaixo exibindo os dois tipos de eixo de rotação que
o tetraedro regular possui:
53
(a) (b)
Figura 9: Os 2 tipos de eixos das simetrias rotacionais do tetraedro regular
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 Fix de
cada uma elas:
(1) A identidade �xa todas as 256 colorações de X.
(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 2�3e 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 lema de Burnside obtemos que o número de moléculas distintas nas
condições do problema é igual a
1
12(256 + 128 + 48) = 36
54
Capítulo 6
O Teorema de Enumeração de Pólya
6.1 Introdução
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 + 4p3b+ 6p2b2 + 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 p3b 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.
6.2 Pesos de colorações, enumerador de estoque e inventários
As de�nições a seguir serão necessárias para a construção do Teorema de Pólya, que
fornece a função geradora contendo a informação sobre as órbitas das colorações.
55
Os símbolos algébricos p e b correspondem às cores preta e branca, respectiva-
mente, 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.
De�nição 73. Uma função peso ! no conjunto C é qualquer função ! : C ! R,
onde R é um anel comutativo contendo os racionais.
Entendendo o conjunto C como um estoque de cores que podemos utilizar para
"pintar" os elementos de D, de�nimos abaixo uma função geradora especial.
De�nição 74. O enumerador de estoque de C por peso ! é de�nido como sendo a
somaP
c2C ! (c).
Isto é, o enumerador de estoque 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.
Exemplo 75. Sejam C = fvermelho claro; vermelho escuro; azulg, ! (vermelho claro) =
r, ! (vermelho escuro) = R e ! (azul) = a. Então o enumerador de estoque (de tin-
tas, 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.
Mais à frente consideraremos o enumerador de estoque como uma série de potên-
cias formais.
Para enumerarmos órbitas de colorações por peso, necessitamos também de�nir o
peso de uma coloração.
De�nição 76. Para cada coloração f 2 X, de�nimos seu peso W (f) pela equação
W (f) =Yd2D
! (f (d))
56
O lema a seguir será utilizado na demonstração do teorema de Pólya, ele nos diz
que colorações na mesma órbita possuem o mesmo peso.
Lema 77. Sejam f1; f2 2 X. Se f1 � f2 então W (f1) =W (f2)
Dem. Como f1 � f2 então existe g 2 G tal que f2 = g � f1. Desta forma
W (f2) = W (g � f1) =Yd2D
! ((g � f1) (d))
=Yd2D
! (f1 (g � d))
=Yd2D
!�f1�g�1 (d)
��=
Yd02D
! (f1 (d0)) = W (f1)
Agora de�nimos o conceito de inventário.
De�nição 78. O inventário de S � X é de�nido porXf2S
W (f)
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). Vamos
à de�nição do inventário padrão, que será fornecido pelo Teorema de Enumeração de
Pólya.
De�nição 79. O inventário padrão FG é de�nido como sendo a soma
FG :=X�
W (f) :=Xf2R
W (f)
onde a soma é estendida sobre um sistema de representantes R para as órbitas da
ação de G em X = CD.
57
Para termos os conceitos dados acima �xados, retornamos ao exemplo do tabuleiro
2� 2.
Relembramos que D = f�1; �2; �3; �4g, o conjunto dos 4 quadrados do tabuleiro,
C = fpreto; brancog, o conjunto das cores eX = 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
e portanto
W (f10) =Yd2D
! (f10 (d)) = ! (f10 (�1))! (f10 (�2))! (f10 (�3))! (f10 (�4))
= ! (preto)! (branco)! (branco)! (preto)
= pbbp
= p2b2
O inventário de todas as 16 colorações (isto é S = X), como visto anteriormente,
é dado por Xf2X
W (f) = p4 + 4p3b+ 6p2b2 + 4pb3 + b4 = (p+ b)4 ,
enquanto que o inventário padrão é
FG =X�
W (f) = p4 + p3b+ 2p2b2 + pb3 + b4,
conforme pode ser visto na Figura 3.
58
6.3 Demonstração do Teorema de Pólya e Corolários
Teorema 80 (Teorema de Enumeração de Pólya - TEP). 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 FG é dado por
FG =X�
W (f) = Z
G;Xc2C
! (c) ;Xc2C
! (c)2 ;Xc2C
! (c)3 ; :::
!Dem. Seja N =
P(�;f)W (f) com a soma estendida a todos os pares (�; f) com
� 2 G; f 2 CD e � � f = f . Então temos
N =Xf2CD
W (f) jSf j
onde Sf é o estabilizador de f . Considere os termos W (f) jSf j enquanto f percorre
uma órbita Of0 de G em CD: cada valor deste é igual a W (f0)jGjjOf0 j
onde f0 é um
representante da órbita Of0, colorações na mesma órbita possuem o mesmo peso e
utilizamos o teorema órbita-estabilizador.
A soma de tais termos é igual a W (f0) jGj, e então se torna claro que
N = jGjX�
W (f)
Analisando a soma N por outro lado, temos que
N =X�2G
X��f=f
W (f)
Assim, relembrando a de�nição de Z (G), vemos que a prova estará completa se
mostrarmos que
X��f=f
W (f) =
Xc2C
! (c)
!k1 Xc2C
! (c)2!k2
� � � Xc2C
! (c)n!kn
59
onde � é uma permutação de tipo TC (�) = (k1; k2; : : : ; kn).
Uma aplicação f : D ! C é �xada por � se, e somente se, f é constante em cada
ciclo de � em D.
Sejam C1; C2; : : : ; Ck1 ; Ck1+1; : : : ; Ck os ciclos de � em D, onde k = k1 + � � �+ kn.
As aplicações f 2 CD �xadas por � estão em correspondência 1-a-1 com as k-uplas
(c1; : : : ; ck) de elementos em C ( a aplicação correspondente é aquela associando ci a
todos os elementos de Ci).
O peso da aplicação f correspondente a (c1; : : : ; ck) ékYi=1
! (ci)jCij e somando sobre
todas as k-uplas (c1; : : : ; ck) obtemosX��f=f
W (f) =X
c1;c2;:::;ck
! (c1)jC1j ! (c2)
jC2j � � �! (ck)jCkj
=Xc1
! (c1)jC1jXc2
! (c2)jC2j � � �
Xck
! (ck)jCkj
=Xc1
! (c1)jC1j � � �
Xck1
! (ck1)jCk1j
Xc2
! (c2)jC2j � � �
Xck2
! (ck2)jCk2j � � �
Xck
! (ck)jCkj
=Xc2C
! (c)1 � � �Xc2C
! (c)1| {z }k1
Xc2C
! (c)2 � � �Xc2C
! (c)2| {z }k2
� � �Xc2C
! (c)n � � �Xc2C
! (c)n| {z }kn
=
Xc2C
! (c)1!k1 X
c2C! (c)2
!k2� � � Xc2C
! (c)n!kn
e isto conclui a demonstração.
Corolário 81. Em particular, se todos os pesos são escolhidos como unitários, obtém-
se o número de padrões distintos, órbitas, pela fórmula
Z (G; jCj ; jCj ; jCj ; :::)
Considerando agora o enumerador de estoque como uma função geradora or-
dinária, em série de potências formais, coloca-se o peso de cada cor como ! (c) = xj,
60
e impõe-se a restrição de que existe no máximo um número �nito cj de cores com
peso xj. Então temos como enumerador de estoque a função geradora
c (x) =1Xj=0
cjxj
Assim deduz-se mais um corolário
Corolário 82. Seja X = F (D;C) o conjunto de todas as colorações do conjunto D
em C, e seja c (x) a função geradora que enumera estoque por peso, como de�nido
acima. 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
Z�G; c (x) ; c
�x2�; c�x3�; :::�
Abaixo interpretamos os coe�cientes do polinômio obtido, ao se substituir o enu-
merador de estoque 1+x no índice de ciclos de um grupo G de permutações arbitrário.
De�nição 83. Dois r-conjuntos S = fx1; : : : ; xrg e S 0 = fx01; : : : ; x0rg são chamados
de G-equivalentes, se para algum g 2 G, gS = S 0.
Corolário 84. O coe�ciente de xr em Z (G; 1 + x; 1 + x2; 1 + x3; : : :) é o número de
classes de G-equivalência de r-subconjuntos de X.
Dem. No enumerador de estoque 1 + x o termo 1 = x0 pode indicar a ausência de
um objeto em X enquanto que x = x1 indica sua presença. Portanto xr signi�ca que
r objetos distintos, formando um r-conjunto, estão presentes. E assim o corolário se
segue do TEP.
61
6.4 Aplicações
Problema 85. Obter a função geradora (inventário padrão) para o número de col-
orações de um tabuleiro de xadrez 2� 2 nas cores preto e branco.
Solução 86. Nesta solução vamos utilizar o grupo diedral, mas sabemos que para
tabuleiros 2�2 não faz diferença se considerarmos apenas as rotações, ou as re�exões
também.
1 2
3 4
Figura 10: Tabuleiro 2� 2 genérico
AquiD = f�1; �2; �3; �4g, C = fpreto; brancog, a função peso é dada por ! (branco) =
b, ! (preto) = p. O grupo de permutações de D corresponde às 8 simetrias do
quadrado, e portanto
G =
�e; (�1�2�4�3) ; (�1�4) (�2�3) ; (�1�3�4�2) ; (�1�3) (�2�4) ; (�1�2) (�3�4) ;
(�2�3) (�1) (�3) ; (�1�4) (�2) (�3)
�com índice de ciclos dado por
Z (G; x1; x2; x4) =1
8
�x41 + 2x
21x2 + 3x
22 + 2x4
�.
Portanto pelo TEP, devemos substituir x1 por b+p, x2 por b2+p2 e x4 por b4+p4
em Z (G; x1; x2; x4), obtendo o inventário padrão
FG =1
8
�(b+ p)4 + 2 (b+ p)2
�b2 + p2
�+ 3
�b2 + p2
�2+ 2
�b4 + p4
��= p4 + p3b+ 2p2b2 + pb3 + b4
como já esperávamos.
62
Problema 87. De quantas maneiras podemos colorir as faces de um cubo utilizando
as cores verde, amarelo e branco, de maneira que em cada pintura tenhamos exata-
mente 2 faces amarelas e 2 verdes? E a quantidade de pinturas contendo exatamente
1 face amarela?
Solução 88. Baseado nas considerações da Solução 70, podemos obter facilmente
a seguinte expressão para o índice de ciclos das simetrias de rotação de um cubo:
1
24
�x61 + 3x
21x22 + 6x
21x4 + 6x
32 + 8x
23
�Colocamos como peso de cada cor
! (amarelo) = a
! (verde) = v
! (branco) = b
e assim obtemos o enumerador de estoque
a+ v + b
Então, pelo TEP, temos que o inventário padrão é dado por
1
24((a+ v + b)6 + 3 (a+ v + b)2
�a2 + v2 + b2
�2+ 6 (a+ v + b)2
�a4 + v4 + b4
�+
+6�a2 + v2 + b2
�3+ 8
�a3 + v3 + b3
�2)
É conveniente usar algum software de álgebra simbólica para expandir esta soma
e obter
a6 + b6 + v6 + ab5 + a5b+ av5 + a5v + bv5 + b5v +
+2abv4 + 2ab4v + 2a4bv + 2a2b4 + 2a3b3 + 2a4b2 +
+2a2v4 + 2a3v3 + 2a4v2 + 2b2v4 + 2b3v3 + 2b4v2 +
+3ab2v3 + 3ab3v2 + 3a2bv3 + 3a2b3v + 3a3bv2 + 3a3b2v + 6a2b2v2
63
Para responder a primeira parte do problema, buscamos o coe�ciente do termo
a2v2b2, que é igual a 6.
Para a segunda pergunta, devemos agrupar todos os termos que contém a1:
a�b5 + v5 + 2bv4 + 2b4v + 3b2v3 + 3b3v2
�totalizando então 12 maneiras distintas:
Problema 89. No Problema 71, qual é o número de moléculas que contém um ou
mais átomos de hidrogênio?
Solução 90. O índice de ciclos em questão é facilmente obtido de Solução 72, sendo
dado por1
12
�x41 + 8x1x3 + 3x
22
�Designamos os pesos
! (CH3) = w1
! (C2H5) = w2
! (Cl) = w3
! (H) = 0
a cada um dos componentes do problema.
Assim nosso enumerador de estoque é
w1 + w2 + w3
que, pelas nossas considerações na seção 8.2, é a função geradora para 1 componente
CH3, 1 componente C2H5, 1 componente Cl e nenhum componente H. Desta forma
estaremos enumerando primeiro as moléculas que não possuem átomos de hidrogênio.
Pelo TEP, temos então que o inventário padrão é dado por
1
12
�(w1 + w2 + w3)
4 + 8 (w1 + w2 + w3)�w31 + w
32 + w
33
�+ 3
�w21 + w
22 + w
23
�2�
64
que ao ser expandido resulta em:
w41 + w42 + w
43 + w1w
32 + w
31w2 + w1w
33 + w
31w3 +
+w2w33 + w
32w3 + w1w2w
23 + w1w
22w3 + w
21w2w3 +
+w21w22 + w
21w
23 + w
22w
23
Portanto temos um total de 15 moléculas não contendo átomos de hidrogênio. Re-
pare 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 é interes-
sante observar que, na função geradora acima, temos apenas 1 molécula para cada
combinação dos 3 componentes CH3, C2H5 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 TEP obteríamos diretamente o número
1
12
�34 + 8 � 3 � 3 + 3 � 32
�= 15
Assim, como o número total de moléculas obtidas na Solução 72 é 36, temos
36� 15 = 21
moléculas que contém pelo menos 1 átomo de hidrogênio.
Problema 91. Qual o número de colares distintos, formados por n contas de m cores
diferentes? (Considere separadamente os casos onde apenas rotações são permitidas,
e onde rotações e inversões são permitidas).
Solução 92. Ao se considerar apenas as rotações, pelo Corolário 81 do TEP, sai
que o número é dado por1
n
Xdjn
� (d)mn=d (6.1)
onde foi utilizado o índice de ciclos de Cn.
65
Por outro lado se inversões (re�exões) também são permitidas , aplica-se o mesmo
corolário mas utilizando o índice de ciclos de D2n, e obtém-se
1
2
0@ 1n
Xdjn
� (d)mn=d +Rn (m)
1A (6.2)
onde
Rn (m) =
�m
n+12 , se n � 1 (mod 2)
12m
n2 (1 +m) , se n � 0 (mod 2)
Problema 93. 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.
Solução 94. (a) Na fórmula (6:1) da Solução 92 colocamos n = 6;m = 2 para
obter
1
6
Xdj6
� (d) 26=d =1
6
�� (1) 26 + � (2) 23 + � (3) 22 + � (6) 2
�=
1
6(64 + 8 + 8 + 4)
= 14
Portanto a resposta correta é 14 colares distintos.
66
(b) Substituímos na fórmula (6:2) da Solução 92 n = 5;m = 3 e obtemos
1
2
0@15
Xdj5
� (d) 35=d +R5 (3)
1A =1
2
�1
5
�� (1) 35 + � (5) 3
�+ 33
�
=1
2
�1
5(243 + 12) + 27
�=
1
2
�255
5+ 27
�=
1
2(78)
= 39
São 39 colares distintos como resposta para este item.
(c) Desta vez atribui-se os pesos
! (preto) = p
! (cinza) = 1
! (branco) = 1
e aplica-se o TEP, substituindo o enumerador de estoque no índice de ciclos de D10,
obtendo
1
2
0@15
Xdj5
� (d)�pd + 1d + 1d
�5=d+ (p+ 1 + 1)
�p2 + 12 + 12
�21A=
1
10
�(p+ 2)5 + 4
�p5 + 2
��+(p+ 2) (p2 + 2)
2
2
= 10p+ 12p2 + 6p3 + 2p4 + p5 + 8
Nesta função geradora busca-se o coe�ciente de p1 que é igual a 10.
Abaixo estão listados todos os colares correspondentes aos números encontrados
nesta solução:
67
Colares diferentes por rotação,contendo 6 contas nas cores
preto e branco:
Colares diferentes por rotação e inversãocontendo 5 contas nas cores preto, cinza e
branco:
Figura 11: Listagem dos colares referentes ao Problema 93
Outra aplicação é a obtenção da função geradora para o número de partições do
inteiro n em no máximo k partes.
NoCorolário 82 toma-se G = Sn, enumerador de estoque igual a 11�x e obtém-se,
68
através da função geradora para o índice de ciclos de Sn,
1Xn=0
Z
�Sn;
1
1� x;1
1� x2 ;1
1� x3 ; : : : ;1
1� xn
�zn = exp
1Xj=1
1
1� xjzj
j
!
= exp
1Xj=1
1Xk=0
xkjzj
j
!
= exp
1Xk=0
1Xj=1
�xkz�j
j
!
= exp
1Xk=0
log1
1� xkz
!
=1
1� z
1Yk=1
1
1� zxk
que fornece o resultado desejado, em vista do Teorema 18.
Problema 95. Obtenha os índices de ciclos para os tabuleiros de xadrez n � n,
considerando 2 casos para as simetrias do tabuleiro: apenas rotações e considerando
rotações e re�exões. Determine o número de colorações distintas do tabuleiro de
xadrez n� n utilizando c cores diferentes, em ambos os casos.
Solução 96. Obviamente, as simetrias do tabuleiro são as mesmas simetrias do
quadrado. Assim devemos considerar a ação do grupo de simetrias do quadrado (rota-
cionais e diedrais) no conjunto das n2 células do tabuleiro.
Denotamos o grupo de simetrias rotacionais e diedrais do tabuleiro respectivamente
por GC� e GD�.
Se uma simetria leva a região a numa região b do tabuleiro, ambas denotadas por
números na �gura, utilizamos a notação a! b.
Observe a �gura abaixo:
69
n=2k
1
3
2
4 k
1 2
34 k
k+1
n=2k+1
1
32
k
k
n=2k+1
1
n
1
32
5
(i) (ii)
(iii) (iv)
Figura 12: Casos a serem considerados para as simetrias do quadrado aplicadas ao
tabuleiro de xadrez n� n
1) e:
A identidade e determina uma permutação de n2 símbolos (células) composta ape-
nas de pontos �xos. Portanto, sua contribuição para o índice de ciclos é
e : xn2
1 ;8n 2 N
2) a1; a3:
Estas rotações correspondem aos ângulos �2e ��
2, respectivamente.
Primeiro consideramos n par, n = 2k. Observando o item (i) da �gura, vemos que
as simetrias a1 e a3 induzem, cada uma, uma permutação de n2 símbolos, composta
de k2 =�n2
�2= n2
4ciclos de comprimento 4. Isto porque a1 leva 1! 2! 4! 3! 1,
e a3 leva 1! 3! 4! 2! 1.
70
Se n = 2k+1, olhamos para a �gura (ii) e vemos que a1 e a3 induzem, cada uma,
uma permutação de n2 símbolos, composta de 1 ponto �xo e k (k + 1) = n�12
n+12=
n2�14ciclos de comprimento 4. Portanto a contribuição de a1 e a3 juntas para o índice
de ciclos é dada por
a1; a3 :
8<: 2xn2
44 , se n � 0 (mod 2)
2x11xn2�14
4 , se n � 1 (mod 2)
3) a2:
Esta rotação corresponde a um ângulo �.
Se n é par, observamos em (i) que 1 ! 4 ! 1 e 2 ! 3 ! 2. Portanto a2 induz
uma permutação de n2 símbolos, composta por n2
4+ n2
4= n2
2ciclos de comprimento
2. Assim temos que a contribuição de a2 é
a2 :
8<: xn2
22 , se n � 0 (mod 2)
x11xn2�12
2 , se n � 1 (mod 2)
De maneira análoga às análises feitas anteriormente, calculamos as seguintes con-
tribuições das re�exões:
4) p1; p2
p1; p2 :
8<: 2xn2
22 , se n � 0 (mod 2)
2xn1xn(n�1)
22 , se n � 1 (mod 2)
5) q1; q2
q1; q2 : 2xn1x
n(n�1)2
2
Assim temos os seguintes índices de ciclos:
Z (GC�;x1; x2; x4) =
8>><>>:14
�xn
2
1 + 2xn2
44 + x
n2
22
�, se n � 0 (mod 2)
14
�xn
2
1 + 2x1xn2�14
4 + x1xn2�12
2
�, se n � 1 (mod 2)
Z (GD�;x1; x2; x4) =
8>><>>:18
�xn
2
1 + 2xn2
44 + 3x
n2
22 + 2xn1x
n(n�1)2
2
�, se n � 0 (mod 2)
18
�xn
2
1 + 2x1xn2�14
4 + x1xn2�12
2 + 4xn1xn(n�1)
22
�, se n � 1 (mod 2)
71
Observando que �n2 � 14
�=
�n2
4, se n � 0 (mod 2)
n2�14, se n � 1 (mod 2)�
n2 � 12
�=
�n2
2, se n � 0 (mod 2)
n2�12, se n � 1 (mod 2)
e de�nindo
bn =1 + (�1)n�1
2=
�0, se n � 0 (mod 2)1, se n � 1 (mod 2)
cn = 2bn�1 =
�2, se n � 0 (mod 2)0, se n � 1 (mod 2)
dn = 2bn + 2 =
�2, se n � 0 (mod 2)4, se n � 1 (mod 2)
então
Z (GC�;x1; x2; x4) =1
4
xn
2
1 + 2xbn1 x
jn2�14
k4 + xbn1 x
jn2�12
k2
!
Z (GD�;x1; x2; x4) =1
8
xn
2
1 + 2xbn1 x
jn2�14
k4 + xbn1 x
jn2�12
k2 + cnx
n2
22 + dnx
n1x
n(n�1)2
2
!Pelo Corolário 81, obtemos o total de colorações do tabuleiro n� n em c cores,
substituindo
x1 = x2 = x4 = c
nos índices de ciclos respectivos.:
Z (GC�; c; c; c) =
8<:14
�cn
2+ c
n2
2 + 2cn2
4
�, se n � 0 (mod 2)
14
�cn
2+ c
n2+12 + 2c
n2+34
�, se n � 1 (mod 2)
Z (GD�; c; c; c) =
8<:18
�cn
2+ 2c
n(n+1)2 + 3c
n2
2 + 2cn2
4
�, se n � 0 (mod 2)
18
�cn
2+ 4c
n(n+1)2 + c
n2+12 + 2c
n2+34
�, se n � 1 (mod 2)
6.5 Enumerando grafos
Como o TEP enumera órbitas de funções, procedemos com uma correspondência
natural entre grafos e funções. Seja D = [p] = f1; 2; : : : ; pg, enquanto que denotamos
72
D(2) como o conjunto de todos os 2-subconjuntos de X. Então com C = f0; 1g,
as funções de D(2) em C representam grafos rotulados de ordem p. Cara função f
corresponde ao grafo G (f) com conjunto de vértices D, no qual i e j são adjacentes
se, e somente se, f (fi; jg) = 1. Portanto duas funções f e h representam o mesmo
grafo se existir uma permutação � de D tal que, sempre que i e j forem adjacentes
em G (f), então � (i) e � (j) são adjacentes em G (h). Portanto G (f) e G (h) são
isomorfos se, e somente se, para alguma permutação � do conjunto D, tivermos
f (fi; jg) = h (f� (i) ; � (j)g) ;8 fi; jg 2 D(2)
Estas observações sugerem as seguintes de�nições gerais.
Dado uma permutação � 2 Sp, corresponde uma permutação �� de D(2), de�nida
por
�� (fi; jg) = f� (i) ; � (j)g ;8 fi; jg 2 D(2)
Desta forma o grupo que estaremos trabalhando é o grupo de todas as permutações
�� correspondentes às permutações � 2 Sp. Seja S(2)p este grupo, então
S(2)p = f�� : � 2 Spg
O grupo S(2)p age no conjunto X = CD = F ([p] ; f0; 1g) da maneira usual, isto é
�� � f = f � ���1;8�� 2 S(2)p ;8f 2 X
1 2
3 4
12
34
14
13
24
23
Figura 13 : A permutação (1) (2) (34) e sua permutação induzida em S(2)4
73
Segue de um exercício 11.6.6 de [An Introduction to Combinatorics - Alan Slom-
son], que para todo p 6= 2, a aplicação � 7�! �� é um isomor�smo entre Sp e S(2)p .
Disto se segue que, para p 6= 2, S(2)p possui p! permutações. O conjunto D(2) contém�p2
�= p(p�1)
2possíveis arestas e portanto S(2)p consiste, em geral, de uma pequena
proporção de todas as permutações de D(2).
A seguir são enumerados os grá�cos de ordem p pelo número de arestas.
Teorema 97. O polinômio gp (x) que enumera grafos de ordem p pelo número de
arestas é dado por
gp (x) = Z�S(2)p ; 1 + x; 1 + x
2; : : :�,
onde o índice de ciclos de S(2)p é dado por:
Z�S(2)p
�=1
p!
Xk1+k2�2:::+kp�p=p
p!pQj=1
jkjkj!
pYj=1
xjk2j+12j+1
pYj=1
�xjx
j�12j
�k2jxj(kj2 )j
Yr<t
x(r;t)krkt[r;t]
Dem. De�nimos uma função peso ! em C = f0; 1g por ! (0) = 1, ! (1) = x. Como
já observamos anteriormente que S(2)p é um grupo atuando em X, segue o resultado
pelo TEP.
Agora vamos calcular o índice de ciclos para S(2)p . Dada uma permutação � 2 Spde tipo cíclico xk11 x
k22 � � �x
kpp , denotamos o tipo cíclico de sua induzida �� pela �echa
xk11 xk22 � � �xkpp �! TC (��) (6.3)
Para cada �, existem 2 tipos de contribuições feitas por �� para o índice desejado;
a primeira vem dos pares em D(2), nos quais ambos elementos estão no mesmo ciclo
de �, e a segunda vem dos pares de D(2), com cada um dos 2 elementos em ciclos
distintos de �.
Determinamos a primeira de tais contribuições. Seja Cj = (12 : : : j) um ciclo de
comprimento j em �. A Figura 14 abaixo mostra a permutação induzida por Cj
74
para j = 2; : : : ; 6. Observe que se j é ímpar, então Cj induzj�12ciclos do mesmo
comprimento j, isto é,
xj �! xj�12j
Por outro lado, quando j é par, encontramos
xj �! x j2xj�22j
1 212
1
23
12 23
31
1 2
4 3
12 23
41 34
13
24
1
2
3
5
4
12
23
34
51
45
13
24
35
52
41
1
2
3
6
5
4
12
23
34
61
56
45
13
24
35
62
51
46
14
2536
Figura 14 : Ciclos em Sp e as permutações induzidas em S(2)p .
75
Portanto como existem kj ciclos de comprimento j em �, os pares de elementos
contidos em ciclos comuns contribuem
xkjj �!
8<: xkj
j�12
j , se j � 1 (mod 2)�x j2xj�22j
�kj, se j � 0 (mod 2)
(6.4)
Para calcular a segunda contribuição, consideramos dois ciclos Cr e Ct em �.
Então os ciclos Cr e Ct induzem nos pares de elementos, um elemento de cada ciclo,
exatamente (r; t) ciclos de comprimento [r; t]. Em particular, quando r = t = j, eles
contribuem j ciclos de comprimento j. Portanto, quando r 6= t, temos
xkrr xktt �! x
(r;t)krkt[r;t] (6.5)
e quando r = t = j,
xkjj �! x
j(kj2 )j (6.6)
Agora multiplicando ambos os lados direitos de (6:4), (6:5) e (6:6) por todos os casos
aplicáveis, obtemos (6:3) e chegamos na expressão para o índice de ciclos de S(2)p .
Teorema 98. O número gn de grafos com n vértices, não isomorfos 2 a 2, é dado
pela fórmula
gn =X
k1+2k2+���+nkn=n
2Gk
Nk
onde a soma é tomada sobre todas as soluções não-negativas da equação
k1 + 2k2 + � � �+ nkn = n
e
Gk =1
2
nX
r;t=1
krkt (r; t)�Xj ímpar
kj
!onde (j; t) é o máximo divisor comum de j e t, e
Nk = 1k11!2k22! � � �nknn!
76
Dem. Basta substituir x = 1 na fórmula do teorema anterior para obter gn como a
soma dos coe�cientes do polinômio, assim
gn =X
k1+k2�2:::+kn�n=n
1nQj=1
jkjkj!
nYj=1
2jk2j+1nYj=1
�2j�k2j 2j(kj2 )Y
r<t
2(r;t)krkt
=X
k1+k2�2:::+kn�n=n
1nQj=1
jkjkj!2Pnj=1 jk2j+12
Pnj=1 jk2j+j(
kj2 )2
Pr<t(r;t)krkt
=X
k1+k2�2:::+kn�n=n
1nQj=1
jkjkj!2Pnj=1 jk2j+1+
Pnj=1 jk2j+j(
kj2 )+
Pr<t(r;t)krkt
Observe agora que o expoente Gk da potência de 2 acima pode ser manipulado
da seguinte forma
Gk =1
2
nXj=1
2jk2j+1 +nXj=1
�2jk2j + 2j
�kj2
��+ 2
Xj<t
(j; t) kjkt
!
=1
2
nXj=1
(2j + 1) k2j+1 �nXj=1
k2j+1 +nXj=1
2jk2j +nXj=1
2j
�kj2
�+ 2
Xj<t
(j; t) kjkt
!
=1
2
Xj ímpar
jkj �Xj ímpar
kj +Xj par
jkj +nXj=1
2jkj (kj � 1)
2+ 2
Xj<t
(j; t) kjkt
!
=1
2
nXj=1
jkj �Xj ímpar
kj +nXj=1
(j; j)�k2j � kj
�+Xj<t
(j; t) kjkt +Xj>t
(t; j) ktkj
!
=1
2
�Xj ímpar
kj +
nXj=1
(j; j) k2j +Xj<t
(j; t) kjkt +Xj>t
(j; t) kjkt
!
=1
2
nX
j;t=1
kjkt (j; t)�Xj ímpar
kj
!
E assim a demonstração do corolário é concluída.
De maneira completamente análoga, mas de�nindo outros grupos induzidos pode
se mostrar o seguinte.
Teorema 99. (i) O número dn de digrafos com n vértices, não isomorfos 2 a 2, é
77
dado pela fórmula
dn =X
k1+2k2+���+nkn=n
2Dk
Nk
onde
Dk =nX
j;t=1
kjkt (j; t)�nXj=1
kj
(ii) O número tn de torneios (digrafos completos e anti-simétricos) com n vértices,
não isomorfos 2 a 2, é dado pela fórmula
tn =X
k1+3k3+5k5+���=n
2Tk
Nk
onde
Tk =1
2
nX
j;t=1
kjkt (j; t)�nXj=1
kj
!
Dem. [5, Págs. 119-127].
6.6 Generalizações e Aplicações
Sejam D e C conjuntos �nitos, jDj = n, e sejam G e H grupos �nitos, G agindo em
D e H agindo em C. Assumimos que C e D são disjuntos. O produto direto G�H
age em X = F (D;C) da seguinte forma:
8f 2 X;8 (�; �) 2 G�H tem-se (�; �) � f = � ��f � ��1
�Para maiores detalhes ver [2, Pág. 229] ou [13, Seção 5.7].
Proposição 100. Se Z (G) e Z (H) são os índices de ciclos dos grupos G e H,
respectivamente, então o índice de ciclos do produto direto G�H é dado por
Z (G�H) = Z (G) � Z (H)
Dem. Ver [2, Pág. 253].
78
Teorema 101. (i) O número de órbitas de colorações de D a C de�nidas pela ação
acima é igual a1
H
X�2H
Z (G;m1 (�) ;m2 (�) ; : : : ;mn (�))
onde
mi (�) =Xdji
dcd (�) , i 2 [n]
(ii) Na forma diferencial, o número de órbitas é igual a
Z
�G;
@
@x1;@
@x2;@
@x3; : : :
�Z
H; exp
1Xk=1
xk
!; exp
2
1Xk=1
x2k
!; exp
3
1Xk=1
x3k
!; : : :
!calculado em
x1 = x2 = x3 = � � � = 0
Dem. (i) Ver [5, Págs. 135-137].
(ii) Ver [13, Pág. 157].
A seguir ilustramos algumas aplicações das generalizações enunciadas, começando
pelo exemplo do tabuleiro de xadrez.
Problema 102. Encontrar o número n de padrões de colorações em preto e branco
de tabuleiros de xadrez 2 � 2, considerando apenas o contraste das cores (Aplicação
encontrada em [13, Pág. 158]).
Solução 103. No exemplo dos tabuleiros 2�2, seja D = f�1; �2; �3; �4g o conjunto
dos quatro quadrados e C = fpreto; brancog o das cores preto e branco. Seja G o
grupo de rotações dos tabuleiros,
G = fe; (�1�2�4�3) ; (�1�4) (�2�3) ; (�1�3�4�2)g
estamos interessados apenas no contraste das cores preto e branco, então tomamos
H = fe; (preto branco)g
79
Então vem da forma diferencial do Teorema 101 (ii) que o número n de difer-
entes padrões de contraste é dado por
n =
�1
8
�@4
@x41+@2
@x22+ 2
@
@x4
��e2(x1+x2+x3+x4) + e2(x2+x4)
��(x1 = 0; x2 = 0; x3 = 0; x4 = 0)
=�e2x2+2x4 + 3 exp (2x1 + 2x2 + 2x3 + 2x4)
�(x1 = 0; x2 = 0; x3 = 0; x4 = 0)
= 1 + 3 = 4
como pode ser observado na Figura 3.
Problema 104. De quantas maneiras podemos distribuir 2 bolas azuis, 2 vermelhas
em 2 caixas quadradas e 1 redonda? Não importa a ordem entre as caixas nem a
ordem das bolas dentro das caixas, e caixas podem �car vazias.
Solução 105. Aqui temos D = fa1; a2; v1; v2g ; G = S2 � S2; C = fr; q1; q2g ; H =
S1 � S2Z (G) = Z (S2 � S2) = Z (S2)2 = 1
4(x21 + x2)
2, pela Proposição 100
Se � = ((1) ; (10) (20)), m1 (�) = m2 (�) = 3
Se � = ((1) ; (1020)), m1 (�) = 1;m2 (�) = 3
E pelo Teorema 101 (i) segue que o número de maneiras distintas é dado por:
1
2!� 12!2!
h�32 + 3
�2+�12 + 3
�2i=1
8(144 + 16) = 20
80
Referências
[1] A. Slomson. An Introduction to Combinatorics. Chapman and Hall, UnitedKingdom, 1991.
[2] P. J. Cameron. Combinatorics: Topics, Techniques, Algorithms. Cam-bridge University Press, United Kingdom 1994.
[3] I. Niven. Formal Power Series, American Mathematical Monthly 76 (1969)871-889.
[4] N. G. de Brujin. Pólya�s Theory of Counting, Applied Combinatorial Math-ematics 144-184. John Wiley & Sons, New York 1964.
[5] F. Harary and E. M. Palmer. Graphical Enumeration. Academic Press, NewYork 1973.
[6] G. E. Andrews, R. Askey and R. Roy. Special Functions, Encyclopedia ofMathematics and Its Applications 71. Cambridge University Press, New York1999.
[7] R. P. Stanley. Enumerative Combinatorics, Vol I, Cambridge Studies inAdvanced Mathematics 49. Cambridge University Press, New York 1997.
[8] R. P. Stanley. Enumerative Combinatorics, Vol II, Cambridge Studies inAdvanced Mathematics 62. Cambridge University Press, New York 1999.
[9] R. L. Graham, D. E. Knuth and O. Patashnik. Concrete Mathematics, 2ndEdition. Addison-Wesley Publishing Company, New York 1995.
[10] G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen,Graphen und chemische Verbindungen, Acta Math. 68, 145-254 (1937).
[11] J. P. Santos, M. P. Mello e I. T. C. Murari. Introdução à Análise Combi-natória, 3a Edição revista. Editora da Unicamp 2002.
[12] H. S. Wilf. Generatingfunctionology, Academic Press Inc, versão disponívelna web para objetivos educacionais, 1994.
http://www.math.upenn.edu/~wilf/DownldGF.html
[13] C. L. Liu. Introduction to Combinatorial Mathematics, McGraw-Hill, NewYork 1968.
81
[14] G. Pólya, R. E. Tarjan, D. R. Woods. Notes on Introductory Combina-torics, Progress in Computer Science and Applied Logic 4. Birkäuser, Boston1983.
![MA111 - Cálculo Ivalle/Teaching/MA111/Aula13.pdf · Teorema do Valor Extremo. Teorema de Fermat Teorema 1 (Teorema do Valor Extremo) Se f for contínua em um intervalo fechado [a;b],](https://img.document.onl/doc/110x75/5be4699809d3f2d7048cbed9/ma111-calculo-i-valleteachingma111aula13pdf-teorema-do-valor-extremo.jpg)
