Seja
um ciclo de tamanho
.
(a) Prove que se
é uma permutação qualquer, então
é um ciclo de tamanho
.
(b) Seja
um ciclo de tamanho
. Prove que existe uma permutação
tal que
.
(a) Prove que se
(b) Seja
Passo 1
O enunciado define um ciclo
e pede duas coisas:
(a) mostrar que para toda permutação vale
e pede duas coisas:
(a) mostrar que para toda permutação
que é outro ciclo de tamanho
;
(b) dado qualquer ciclo de tamanho
, construir
tal que
.
Vamos usar a definição de conjugação e a ação de permutações sobre elementos.
(b) dado qualquer ciclo
Vamos usar a definição de conjugação e a ação de permutações sobre elementos.
Passo 2
Mostramos a fórmula de conjugação. Para todo
no conjunto subjacente,
Agora, se
não está em
, então
não está em
, logo
e assim
Se
para algum
, então
e
(com
). Logo
o que mostra que a ação de
sobre cada
segue exatamente o ciclo
.
Passo 3
Como
só move os pontos
no mesmo “giro” de
, concluímos que
é de fato um ciclo de tamanho
.
Passo 4
Para (b), seja
outro ciclo de tamanho
. Definimos
primeiro em
por
e estendemos
arbitrariamente a uma bijeção de todo o conjunto, por exemplo mapeando elementos fora de
para os que faltam em
.
Passo 5
Pelo passo anterior, para cada
temos
com
, e elementos fora de
ficam fixos. Portanto
como queríamos.
Resposta
(a) Já está demonstrado que
que é um ciclo de tamanho
.
(b) Dada , basta definir
e estendê-la a uma bijeção, obtendo
.
(b) Dada