(a) Probar que \left|S_{n}\right|=n !.
(b) Achar em S_{3} e S_{4} elementos a tais que a=a^{-1} e a^{3}=e.

Passo 1

Vou deixar bem claro o que o problema pede e quais informações temos.
  • Pedido (a): Provar que \left|S_{n}\right|=n!.
  • Pedido (b): Em S_{3} e em S_{4}, achar elementos a tais que a=a^{-1} e achar elementos a tais que a^{3}=e.
Informações relevantes dadas (implícitas no enunciado):
  • S_{n} é o grupo simétrico sobre o conjunto \{1,2,\dots,n\}, isto é, o conjunto de todas as bijeções de \{1,\dots,n\} sobre si mesmo, com composição como operação.
  • e denota a permutação identidade.
  • O problema pede exemplos concretos em S_{3} e em S_{4}.

Passo 2

Entender o que é contar permutações (a ideia para (a)) — explicação passo a passo.
Uma permutação de \{1,\dots,n\} é uma função bijetora que assigna a cada elemento i um valor a(i) distinto entre 1,\dots,n. Para construir uma permutação podemos escolher, em sequência, as imagens dos elementos:
  • Para 1 n escolhas possíveis para a(1).
  • Depois de escolher a(1), para 2 restam n-1 valores disponíveis para a(2) (porque não podemos repetir o valor já usado por a(1)).
  • Seguindo, para 3 restam n-2 escolhas, e assim por diante, até para n restar exatamente 1 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) é
n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1 = n!.

Passo 3

Dar uma prova por indução (opcional, para reforçar) — ainda para (a).
Base: para n=1, S_{1} contém apenas a identidade, então \left|S_{1}\right|=1=1!.
Passo indutivo: suponha \left|S_{n-1}\right|=(n-1)!. Para formar uma permutação em S_{n} considere a imagem de n. Se fixarmos a(n)=k com k\in\{1,\dots,n\}, então restam permutar os n-1 elementos restantes de forma bijetora entre os n-1 valores não iguais a k; pelo passo indutivo existem (n-1)! tais permutações para cada escolha de k. Como k tem n possibilidades, obtém-se \left|S_{n}\right|=n\cdot (n-1)! = n!.
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 (1\\\ 2\\\ 3) representa a permutação que envia 1\mapsto2, 2\mapsto3, 3\mapsto1 e fixa os demais pontos.
  • O inverso de um ciclo (a_1\\ a_2\\ \dots\\ a_k) é (a_k\\ \dots\\ a_2\\ a_1) (ou seja, reverter a ordem): aplicar o ciclo seguido do seu inverso retorna a identidade.
  • Uma transposição (i\\ j) (um ciclo de comprimento 2) é seu próprio inverso, porque (i\\ j)^2=e. Em geral, uma permutação a satisfaz a=a^{-1} se, e somente se, a^2=e; diz-se então que a é uma involução (ordem 1 ou 2).
  • Uma permutação satisfaz a^3=e se a ordem de a divide 3, isto é, a ordem é 1 ou 3. Ciclos de comprimento 3 (3-ciclos) têm ordem 3: por exemplo (a\\ b\\ c)^3=e e (a\\ b\\ c)\neq 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 (1\\\ 2)(3\\\ 4), tem ordem 2 e é seu próprio inverso.

Passo 5

Agora tratar S_{3}. Lista completa de elementos e classificação por tipos.
Elementos de S_{3} (em notação de ciclos):
  • e (identidade).
  • Três transposições: (1\\\ 2), (1\\\ 3), (2\\\ 3). Cada uma troca dois elementos e fixa o terceiro.
  • Dois 3-ciclos: (1\\\ 2\\\ 3) e (1\\\ 3\\\ 2). Note que (1\\\ 3\\\ 2)=(1\\\ 2\\\ 3)^{-1}.
Agora, os pedidos em S_{3}:
  • Elementos a tais que a=a^{-1}. São exatamente as involuções e a identidade. Em S_{3} isso dá:
    e,\quad (1\\\ 2),\quad (1\\\ 3),\quad (2\\\ 3).
    Explicação curta: cada transposição satisfaz (i\\ j)^2=e, logo (i\\ j)=(i\\ j)^{-1}.
  • Elementos a tais que a^{3}=e. São os elementos cuja ordem divide 3: a identidade e os 3-ciclos. Em S_{3} isso dá:
    e,\quad (1\\\ 2\\\ 3),\quad (1\\\ 3\\\ 2).
    Verificação: (1\\\ 2\\\ 3)^3=e e (1\\\ 3\\\ 2)^3=e.

Passo 6

Agora tratar S_{4}. Explicar os tipos de permutações relevantes e depois dar exemplos.
Tipos de permutações em S_{4} que nos interessam:
  • Transposições (ciclos de comprimento 2): há \binom{4}{2}=6 delas, por exemplo (1\\\ 2), (1\\\ 3), (1\\\ 4), (2\\\ 3), (2\\\ 4), (3\\\ 4). Todas são involuções (auto-inversas).
  • Produto de duas transposições disjuntas (tipo (i\\ j)(k\\ \ell)): há 3 tais (escolher a partição em dois pares disjuntos), por exemplo (1\\\ 2)(3\\\ 4), (1\\\ 3)(2\\\ 4), (1\\\ 4)(2\\\ 3). Cada uma tem ordem 2 e é auto-inversa.
  • 3-ciclos: para escolher um 3-ciclo escolhe-se um subconjunto de 3 elementos dentre 4 ( \binom{4}{3}=4 escolhas) e, para cada subconjunto, há 2 3-ciclos não idênticos (um é o inverso do outro), dando no total 8 3-ciclos. Exemplos: (1\\\ 2\\\ 3), (1\\\ 3\\\ 2), (1\\\ 2\\\ 4), (1\\\ 4\\\ 2), etc. Estes têm ordem 3.
Agora os pedidos em S_{4}:
  • Elementos a tais que a=a^{-1}. São as involuções (ordem 1 ou 2): a identidade, todas as transposições e todos os produtos de duas transposições disjuntas. Exemplos listados:
    e, \quad (1\\\ 2),\\ (1\\\ 3),\\ (1\\\ 4),\\ (2\\\ 3),\\ (2\\\ 4),\\ (3\\\ 4), \quad (1\\\ 2)(3\\\ 4),\\ (1\\\ 3)(2\\\ 4),\\ (1\\\ 4)(2\\\ 3).
    (No total: 1 + 6 + 3 = 10 elementos com a=a^{-1} em S_{4}.)
  • Elementos a tais que a^{3}=e. São os elementos de ordem 1 ou 3: a identidade e todos os 3-ciclos (oitos deles). Exemplos:
    e,\quad (1\\\ 2\\\ 3),\\ (1\\\ 3\\\ 2),\\ (1\\\ 2\\\ 4),\\ (1\\\ 4\\\ 2),\\ (1\\\ 3\\\ 4),\\ (1\\\ 4\\\ 3),\\ (2\\\ 3\\\ 4),\\ (2\\\ 4\\\ 3).
    (No total: 1+8=9 elementos com a^3=e em S_{4}.)

Passo 7

Mostrar rapidamente por que os exemplos satisfazem as propriedades (garantia didática).
  • Para qualquer transposição (i\\ j) tem-se
    (i\\ j)^2 = e,
    porque trocar i com j duas vezes retorna cada elemento ao lugar. Assim (i\\ j)^{-1}=(i\\ j).
  • Para qualquer produto de duas transposições disjuntas, por exemplo (1\\\ 2)(3\\\ 4), as duas transposições agem em pares diferentes e cada uma tem quadrado e; como são disjuntas, o quadrado do produto é o produto dos quadrados, logo \big((1\\\ 2)(3\\\ 4)\big)^2 = e. Portanto tais produtos são auto-inversos.
  • Para um 3-ciclo (a\\ b\\ c) vale
    (a\\ b\\ c)^3 = e,
    porque aplicando três vezes a rotação a\to b\to c\to a retorna tudo ao lugar. O inverso de (a\\ b\\ c) é (a\\ c\\ b)=(a\\ b\\ c)^2, que é diferente de (a\\ b\\ c) se o ciclo é não trivial.

Resposta

(a) \left|S_{n}\right|=n!.
(b) Em S_{3}:
  • Elementos com a=a^{-1}: e,\\ (1\\\ 2),\\ (1\\\ 3),\\ (2\\\ 3).
  • Elementos com a^{3}=e: e,\\ (1\\\ 2\\\ 3),\\ (1\\\ 3\\\ 2).
Em S_{4}:
  • Elementos com a=a^{-1}:
    e,\\ (1\\\ 2),\\ (1\\\ 3),\\ (1\\\ 4),\\ (2\\\ 3),\\ (2\\\ 4),\\ (3\\\ 4),\\ (1\\\ 2)(3\\\ 4),\\ (1\\\ 3)(2\\\ 4),\\ (1\\\ 4)(2\\\ 3).
  • Elementos com a^{3}=e:
    e,\\ (1\\\ 2\\\ 3),\\ (1\\\ 3\\\ 2),\\ (1\\\ 2\\\ 4),\\ (1\\\ 4\\\ 2),\\ (1\\\ 3\\\ 4),\\ (1\\\ 4\\\ 3),\\ (2\\\ 3\\\ 4),\\ (2\\\ 4\\\ 3).

Exercícios relacionados