*20. Nessa questão faça o seguinte:
a) Determine todos os 2 -ciclos e os 3 -ciclos de
. [Dica: existem seis 2 -ciclos e oito 3-ciclos.]
*b) Se
, descreva uma fórmula para calcular o número de
-ciclos em
. [Dica: use o fato de que existem
maneiras de representar um
-ciclo.]
a) Determine todos os 2 -ciclos e os 3 -ciclos de
*b) Se
Passo 1
O enunciado pede duas coisas:
- (a) Em
determinar todos os -ciclos e todos os -ciclos. (Foi dada a dica: existem seis -ciclos e oito -ciclos.) - (b) Para
, descrever uma fórmula que calcula o número de -ciclos em . (Foi dada a dica: use que existem maneiras de representar um -ciclo.)
Informações relevantes que vamos usar:
- Um
-ciclo é uma permutação que move exatamente elementos em um ciclo e deixa os outros fixos. - Diferentes representações cíclicas que são rotações uma da outra representam a mesma permutação (por exemplo
). - No problema (a) trabalharemos com
; no (b) queremos uma fórmula em função de e .
Passo 2
O que é um
-ciclo e como representá-lo (aula curta e intuitiva).
- Um
-ciclo usa exatamente elementos distintos e envia . Escrevemos isso como . - Observação sobre representações: qualquer rotação cíclica da tupla dá a mesma permutação. Ou seja,
Existem exatamente
formas de escrever o mesmo
-ciclo por rotações.
- Consequência prática para contagem: ao contar sequências ordenadas de
elementos que formam um ciclo, devemos dividir por para não contar múltiplas representações da mesma permutação.
Passo 3
Contagem e lista dos
-ciclos em
(transposições).
- Um
-ciclo troca dois elementos e fixa os outros. Em escolhemos 2 elementos dentre 4, o número de escolhas é . - As seis transposições (colocadas em notação cíclica) são:
- Explicação didática: cada transposição é única porque trocar
com é diferente de trocar com se ; não há problema de representação múltipla aqui porque já é a mesma escrita (apenas uma forma de representar).
Passo 4
Contagem e lista dos
-ciclos em
.
- Para um
-ciclo escolhemos 3 elementos dentre 4: escolhas de subconjunto. - Para cada subconjunto de 3 elementos, quantos
-ciclos distintos existem? Uma permutação cíclica de 3 elementos tem ordens, mas cada ciclo é representado de maneiras por rotação, então o número distinto por subconjunto é . (Equivalente: .) - Portanto o total é
. - Listando-os de forma sistemática (cada subconjunto dá dois ciclos):
- Dica prática para a prova: para listar sem repetição, escolha subconjuntos em ordem lexicográfica e, para cada subconjunto
com , escreva e .
Passo 5
Derivação geral da fórmula para o número de
-ciclos em
.
Método 1 (ordenando e dividindo pelas rotações):
Método 1 (ordenando e dividindo pelas rotações):
- Primeiro conte sequências ordenadas de
elementos distintos escolhidos dentre . Isso é
- Cada
-ciclo é representado por dessas sequências (as rotações), então dividimos por . Assim obtemos
Método 2 (escolhendo subconjunto e contando ciclos distintos):
- Escolha um conjunto de
elementos: maneiras. - Para cada conjunto, o número de ciclos distintos é
(porque entre as permutações ordenadas, as rotações representam o mesmo ciclo, restando ciclos). - Multiplicando,
- Essas duas expressões são equivalentes; de fato
Passo 6
Verificações rápidas e interpretações (úteis para prova).
- Caso
: a fórmula dá , que é o número de transposições — faz sentido. - Caso
: a fórmula dá , o clássico número de ciclos que usam todos os elementos (n-ciclos). - Lembre-se sempre do motivo da divisão por
: evitar contar rotações equivalentes do mesmo ciclo.
Passo 7
Resumo curto e dica final para a prova (ânimo).
- Para listar ciclos no exame, escolha subconjuntos ordenados (por exemplo começando pelo menor elemento) e gere as
permutações-ciclo por subconjunto; isso evita repetições e confusão. - Você está indo bem; respira, faz com calma cada escolha de subconjunto e logo pega o jeito de listar rápido.
Resposta
(a) Os
-ciclos em
são
.
Os -ciclos em
são
.
Os
(b) O número de
-ciclos em
(para
) é