(a) Probar que
!.
(b) Achar em
e
elementos
tais que
e
.
(b) Achar em
Passo 1
Vou deixar bem claro o que o problema pede e quais informações temos.
- Pedido (a): Provar que
. - Pedido (b): Em
e em , achar elementos tais que e achar elementos tais que .
Informações relevantes dadas (implícitas no enunciado):
-
é o grupo simétrico sobre o conjunto , isto é, o conjunto de todas as bijeções de sobre si mesmo, com composição como operação. -
denota a permutação identidade. - O problema pede exemplos concretos em
e em .
Passo 2
Entender o que é contar permutações (a ideia para (a)) — explicação passo a passo.
Uma permutação de
é uma função bijetora que assigna a cada elemento
um valor
distinto entre
. Para construir uma permutação podemos escolher, em sequência, as imagens dos elementos:
- Para
há escolhas possíveis para . - Depois de escolher
, para restam valores disponíveis para (porque não podemos repetir o valor já usado por ). - Seguindo, para
restam escolhas, e assim por diante, até para restar exatamente escolha.
Isso usa a regra do produto (princípio fundamental da contagem): quando uma construção se faz por etapas independentes, o número total de construções é o produto do número de escolhas em cada etapa.
Portanto o número total de bijeções (permutações) é
Passo 3
Dar uma prova por indução (opcional, para reforçar) — ainda para (a).
Base: para
,
contém apenas a identidade, então
.
Passo indutivo: suponha
. Para formar uma permutação em
considere a imagem de
. Se fixarmos
com
, então restam permutar os
elementos restantes de forma bijetora entre os
valores não iguais a
; pelo passo indutivo existem
tais permutações para cada escolha de
. Como
tem
possibilidades, obtém-se
.
Assim (a) está provado.
Passo 4
Conceitos necessários para (b): notação cíclica, inverso, ordem de uma permutação, e consequências.
- Uma permutação pode ser escrita em notação de ciclos, por exemplo
representa a permutação que envia , , e fixa os demais pontos. - O inverso de um ciclo
é (ou seja, reverter a ordem): aplicar o ciclo seguido do seu inverso retorna a identidade. - Uma transposição
(um ciclo de comprimento ) é seu próprio inverso, porque . Em geral, uma permutação satisfaz se, e somente se, ; diz-se então que é uma involução (ordem ou ). - Uma permutação satisfaz
se a ordem de divide , isto é, a ordem é ou . Ciclos de comprimento (3-ciclos) têm ordem : por exemplo e .
Além disso:
- Ciclos disjuntos comutam e o inverso de uma permutação é obtido invertendo cada ciclo individualmente.
- Produto de duas transposições disjuntas, por exemplo
, tem ordem e é seu próprio inverso.
Passo 5
Agora tratar
. Lista completa de elementos e classificação por tipos.
Elementos de
(em notação de ciclos):
-
(identidade). - Três transposições:
, , . Cada uma troca dois elementos e fixa o terceiro. - Dois 3-ciclos:
e . Note que .
Agora, os pedidos em
:
-
Elementos
tais que . São exatamente as involuções e a identidade. Em isso dá: Explicação curta: cada transposição satisfaz, logo . -
Elementos
tais que . São os elementos cuja ordem divide : a identidade e os 3-ciclos. Em isso dá: Verificação:e .
Passo 6
Agora tratar
. Explicar os tipos de permutações relevantes e depois dar exemplos.
Tipos de permutações em
que nos interessam:
- Transposições (ciclos de comprimento
): há delas, por exemplo , , , , , . Todas são involuções (auto-inversas). - Produto de duas transposições disjuntas (tipo
): há tais (escolher a partição em dois pares disjuntos), por exemplo , , . Cada uma tem ordem e é auto-inversa. - 3-ciclos: para escolher um 3-ciclo escolhe-se um subconjunto de
elementos dentre ( escolhas) e, para cada subconjunto, há 3-ciclos não idênticos (um é o inverso do outro), dando no total 3-ciclos. Exemplos: , , , , etc. Estes têm ordem .
Agora os pedidos em
:
-
Elementos
tais que . São as involuções (ordem ou ): a identidade, todas as transposições e todos os produtos de duas transposições disjuntas. Exemplos listados: (No total:elementos com em .) -
Elementos
tais que . São os elementos de ordem ou : a identidade e todos os 3-ciclos (oitos deles). Exemplos: (No total:elementos com em .)
Passo 7
Mostrar rapidamente por que os exemplos satisfazem as propriedades (garantia didática).
-
Para qualquer transposição
tem-se porque trocarcom duas vezes retorna cada elemento ao lugar. Assim . -
Para qualquer produto de duas transposições disjuntas, por exemplo
, as duas transposições agem em pares diferentes e cada uma tem quadrado ; como são disjuntas, o quadrado do produto é o produto dos quadrados, logo . Portanto tais produtos são auto-inversos. -
Para um 3-ciclo
vale porque aplicando três vezes a rotaçãoretorna tudo ao lugar. O inverso de é , que é diferente de se o ciclo é não trivial.
Resposta
(a)
.
(b) Em
:
- Elementos com
: . - Elementos com
: .
Em
:
- Elementos com
:
. - Elementos com
:
.