Simetria em Análise Combinatória: Contar por Classes de Equivalência

O que é simetria na contagem: a ideia de “mesmo resultado”

Em muitos problemas, diferentes descrições levam ao mesmo objeto ou ao mesmo padrão. Isso acontece porque existe uma transformação que “mexe” na representação, mas não muda a estrutura do que estamos contando. Essas transformações formam uma ação sobre o conjunto de resultados, e os resultados se agrupam em classes de equivalência (ou órbitas): cada classe reúne todas as representações que são iguais “por simetria”.

Contar por classes de equivalência reduz trabalho porque, em vez de contar cada representação separadamente e depois lidar com duplicidades, você conta quantas classes existem e quantos elementos há em cada classe (ou usa um método que já incorpora isso).

Quando duas configurações são equivalentes?

• Rotações: girar um objeto circular (mesa, colar, arranjo em roda) e obter a mesma configuração.
• Reflexões: espelhar (virar) e obter a mesma configuração (faz sentido em colares/braceletes; nem sempre faz sentido em mesas com lugares fixos numerados).
• Permutação de rótulos: trocar nomes/cores que desempenham o mesmo papel no problema (por exemplo, “time A” e “time B” quando são indistinguíveis).
• Equiprobabilidade por simetria: eventos que, por invariância do experimento, têm a mesma probabilidade (ex.: “quem fica à esquerda de quem” em uma fila aleatória).

Checklist prático: como identificar e usar simetria sem duplicar contagens

Passo a passo

1. Defina o que é um resultado (o objeto final). Ex.: “arranjo em uma mesa circular” ou “padrão de cores em um colar”.
2. Liste transformações que não mudam o resultado. Ex.: rotações; reflexões; renomear rótulos equivalentes.
3. Verifique se a transformação é válida no contexto. Ex.: em uma mesa com cadeiras numeradas, rotação não é simetria; em uma mesa sem numeração, rotação é.
4. Decida a estratégia:
   • Fixar um representante (quebrar a simetria): “fixe uma pessoa na posição 1” para eliminar rotações.
   • Contar por classes: conte classes e tamanhos; cuidado com classes de tamanhos diferentes.
   • Usar equiprobabilidade: compare eventos simétricos para obter probabilidades sem contar tudo.
5. Valide com uma checagem: “contagem total = soma (tamanho da classe) × (número de classes)” quando os tamanhos são uniformes, ou “contagem total = soma dos tamanhos das classes” no geral.

Arranjos circulares: rotações e o truque de fixar um elemento

Em arranjos em roda, a rotação pode gerar duplicidade: a mesma disposição pode ser descrita começando por cadeiras diferentes. A forma mais prática de evitar isso é fixar um elemento como referência.

Exemplo 1 (contagem): pessoas em uma mesa circular

Problema. Quantas maneiras diferentes existem de sentar 6 pessoas em uma mesa circular sem lugares numerados?

Simetria. Rotacionar todos ao mesmo tempo não muda quem está ao lado de quem; logo, rotações geram equivalência.

Continue em nosso aplicativo e ...

• Ouça o áudio com a tela desligada
• Ganhe Certificado após a conclusão
• + de 5000 cursos para você explorar!

ou continue lendo abaixo...

Baixar o aplicativo

Passo a passo (quebrando a simetria).

1. Escolha uma pessoa (por exemplo, Ana) e fixe Ana em uma cadeira de referência.
2. Arranje as outras 5 pessoas nas 5 cadeiras restantes.

Logo, o número de arranjos circulares é 5!.

Validação por “contagem total vs classes”

Se as cadeiras fossem numeradas, haveria 6! arranjos lineares. Em uma mesa sem numeração, cada arranjo circular corresponde a 6 arranjos lineares (um para cada rotação possível). Assim:

nº de classes (arranjos circulares) = 6! / 6 = 5!

Aqui os tamanhos das classes são todos iguais a 6 porque, com pessoas distintas, nenhuma rotação (exceto a identidade) mantém o arranjo igual.

Reflexão: quando “virar” conta como o mesmo?

Reflexão é uma simetria adicional quando o objeto não tem “frente e verso” distinguíveis. Em colares/braceletes, frequentemente uma reflexão produz o mesmo desenho físico. Em mesas, isso depende do que o problema considera “o mesmo”: se você pode levantar a mesa e girar/espelhar sem distinguir orientação, reflexões podem ser equivalências; se há um palco, uma parede de referência, ou cadeiras fixas, talvez não.

Exemplo 2 (colares): padrões com 2 cores e reflexões

Problema. Um colar tem 6 contas, cada conta é preta (P) ou branca (B). Queremos contar padrões “físicos” considerando que rotações não mudam o colar. Se o colar puder ser virado, reflexões também não mudam. Como a simetria muda a contagem?

Ideia. “Só rotações” (colar rígido) e “rotações + reflexões” (bracelete) geram classes diferentes: o segundo caso agrupa mais representações, então o número de classes tende a ser menor.

Alerta importante. Nem todas as classes têm o mesmo tamanho quando há repetição de cores: alguns padrões são mais simétricos e ficam invariantes sob certas rotações/reflexões. Nesses casos, dividir por 6 (ou por 12) pode falhar.

Como proceder na prática. Para padrões com repetição, uma abordagem segura é: (i) listar tipos de simetria do padrão, (ii) contar quantas sequências lineares geram o mesmo padrão físico, (iii) somar por classes. Em problemas de probabilidade, muitas vezes você não precisa contar todas as classes; basta comparar eventos simétricos ou usar um representante fixo quando a simetria é uniforme.

Equiprobabilidade por simetria: probabilidades sem contagem pesada

Em probabilidade, simetria frequentemente permite afirmar que vários resultados têm a mesma chance. Isso transforma um problema em “quantos casos favoráveis existem dentro de um conjunto de casos igualmente prováveis?”.

Exemplo 3 (fila): ordem relativa de duas pessoas

Problema. Em uma fila aleatória com 10 pessoas distintas, qual a probabilidade de Ana estar antes de Bruno?

Simetria. Para qualquer fila, se você trocar apenas as posições de Ana e Bruno, obtém uma fila igualmente provável. Metade das filas tem Ana antes de Bruno e metade tem Bruno antes de Ana.

Resposta. 1/2.

Validação por contagem total vs soma de classes. Considere classes de equivalência formadas por pares de filas que diferem apenas pela troca de Ana e Bruno. Cada classe tem tamanho 2, e exatamente 1 fila em cada classe é favorável. Logo, a probabilidade é 1/2.

Exemplo 4 (fila): quem é o primeiro entre três?

Problema. Em uma fila aleatória, qual a probabilidade de Carla ser a primeira entre {Carla, Diego, Elisa}?

Simetria. As 3 pessoas são simétricas: nenhuma tem vantagem. Entre as três, cada uma tem a mesma chance de ser a primeira.

Resposta. 1/3.

Mesas circulares em probabilidade: padrões de vizinhança

Em mesas circulares, eventos sobre “quem senta ao lado de quem” são naturais. A simetria de rotação permite fixar uma pessoa e trabalhar com as posições relativas.

Exemplo 5 (mesa circular): probabilidade de duas pessoas ficarem juntas

Problema. 8 pessoas sentam ao acaso em uma mesa circular sem lugares numerados. Qual a probabilidade de Ana e Bruno ficarem lado a lado?

Passo a passo (fixar para eliminar rotações).

1. Fixe Ana em uma posição de referência.
2. Agora existem 7 lugares restantes para Bruno, todos igualmente prováveis.
3. Dos 7 lugares, 2 são vizinhos de Ana (à esquerda e à direita).

Probabilidade. 2/7.

Validação por contagem total vs favoráveis. Total de arranjos circulares: 7!. Favoráveis: fixe Ana; coloque Bruno em um dos 2 vizinhos; arranje os outros 6: 2·6!. Então (2·6!)/(7!) = 2/7.

Exemplo 6 (mesa circular): três pessoas consecutivas

Problema. 9 pessoas sentam em mesa circular. Qual a probabilidade de {A, B, C} ocuparem três cadeiras consecutivas (em alguma ordem)?

Passo a passo.

1. Fixe A para remover rotações.
2. Para que A, B, C sejam consecutivos, o trio deve ocupar um bloco de 3 cadeiras consecutivas que inclua A. Em torno de A, há exatamente 2 blocos de tamanho 3 que incluem A: (esquerda, A, direita) não é bloco; os blocos são {A e duas à direita} ou {A e duas à esquerda}.
3. Escolha qual bloco: 2 opções.
4. Dentro do bloco, arranje A, B, C: 3! maneiras, mas A já está fixo em uma cadeira específica do bloco, então restam 2! para B e C.
5. Arranje as outras 6 pessoas nas 6 cadeiras restantes: 6!.

Favoráveis. 2 · 2! · 6!. Total. 8! (pois fixamos A). Assim:

P = (2 · 2! · 6!) / 8! = 4 / 56 = 1/14

Checagem de simetria. Fixar A é válido porque rotações não mudam o evento “serem consecutivos” e todas as rotações são equiprováveis.

Permutação de rótulos: quando trocar nomes não muda o problema

Às vezes, o que importa é a estrutura (por exemplo, “quantos de cada tipo”), e não qual rótulo específico ficou em qual lugar. Se os rótulos são intercambiáveis, você pode agrupar resultados que diferem apenas por uma permutação desses rótulos.

Exemplo 7 (probabilidade): dois times indistinguíveis em uma fila

Problema. Em uma fila de 6 pessoas, 3 usam camisa vermelha e 3 usam camisa azul. Suponha que pessoas da mesma cor são indistinguíveis para o evento analisado (só importa a sequência de cores). Qual a probabilidade de a fila alternar cores (VAVAVA ou AVAVAV)?

Simetria de rótulos. Trocar “vermelho” por “azul” não muda a estrutura “alternante”; os dois padrões são equivalentes por permutação de rótulos.

Contagem por classes (sequências de cores). O espaço amostral, em termos de sequências de cores com 3 V e 3 A, tem tamanho 20 (número de sequências distintas de cores). Favoráveis: exatamente 2 sequências alternantes. Então:

P = 2/20 = 1/10

Validação por total vs soma de classes. Aqui cada “classe” é uma sequência de cores; dentro de cada classe há várias filas de pessoas distintas, mas como o experimento relevante foi definido no nível das cores, a contagem correta é no nível das classes (sequências).

Comparando resultados “iguais por simetria”: reduzir o número de casos a analisar

Mesmo quando você não está contando o total, simetria ajuda a reduzir análise: em vez de estudar muitos casos, você estuda um representante por classe.

Exemplo 8 (mesa circular): padrões de adjacência equivalentes

Problema. Em uma mesa circular com 7 pessoas, você quer a probabilidade de que Ana tenha exatamente 1 dos seus 2 vizinhos pertencendo ao grupo G (um subconjunto fixo de pessoas). Em vez de analisar “Ana senta em qual cadeira?”, use simetria.

Uso da simetria. Fixe Ana. Agora só importa quais pessoas ocupam as duas cadeiras vizinhas. Todas as escolhas de dois vizinhos (ordenados esquerda/direita) são equiprováveis entre as 6 pessoas restantes.

Estratégia. Conte pares (esquerda, direita) com exatamente um membro em G e outro fora de G. Se |G|=k e Ana não está em G, então há k escolhas para o vizinho em G e 6-k para o outro, e 2 ordens (G à esquerda ou à direita): favoráveis 2·k·(6-k). Total de pares ordenados: 6·5. Logo:

P = (2·k·(6-k)) / (30)

Esse tipo de argumento evita analisar 7 rotações possíveis e múltiplas posições absolutas.

Quando “dividir pelo número de simetrias” funciona (e quando não)

Uma tentação comum é: “se há m rotações, divida por m”. Isso funciona quando todas as classes têm o mesmo tamanho sob a ação considerada. Em arranjos circulares com pessoas todas distintas, as classes sob rotação têm tamanho exatamente n. Já em padrões com repetição (como colares com cores repetidas), algumas configurações podem ser invariantes por rotações/reflexões e geram classes menores, quebrando a divisão simples.

Mini-teste para evitar erro

• Se os elementos são todos distintos e a simetria é apenas rotação: classes tendem a ter tamanho uniforme.
• Se há repetição/indistinguibilidade (cores repetidas, padrões periódicos): suspeite de classes de tamanhos diferentes.
• Se incluir reflexão: mais chances de haver invariâncias (padrões palindrômicos no círculo), então redobre o cuidado.

Exemplo completo com “contagem total vs soma de classes”: pares em uma mesa circular

Problema. 6 pessoas sentam em mesa circular sem lugares numerados. Considere o evento E: “Ana está exatamente em frente de Bruno” (assuma mesa com 6 lugares igualmente espaçados, então ‘em frente’ faz sentido). Calcule P(E) e valide por duas formas.

Método 1: simetria direta (fixar e contar posições)

1. Fixe Ana.
2. Há exatamente 1 lugar “em frente” a Ana.
3. Bruno tem 5 lugares possíveis restantes, todos equiprováveis.

P(E)=1/5.

Método 2: contagem total vs favoráveis

Total de arranjos circulares: 5! (fixe Ana). Favoráveis: fixe Ana; coloque Bruno no lugar oposto (1 jeito); arranje os outros 4: 4!. Então:

P(E) = 4! / 5! = 1/5

As duas abordagens coincidem porque a simetria garante equiprobabilidade das posições relativas de Bruno em relação a Ana.