Permutação Circular e Aplicações

Prévia do material em texto

Análise Combinatória, Probabilidades e Aplicações
Curso de Verão 2024 - IME/USP
Análise Combinatória:
Permutação circular
Permutação circular
Tipo de permutação que considera equivalentes disposições que coincidem por rotação. O número de
maneiras de se permutar, de maneira circular, n objetos colocados lado a lado em uma circunferência
é
(PC)n = (n− 1)!
Vamos entender a fórmula através do exemplo:
Exemplo 1: De quantas maneiras podemos formar uma roda com 4 crianças?
Solução 1: Pela equivalência por rotação, gostaŕıamos de contar apenas 1 de cada 4 combinações
consideradas na permutação simples. Por exemplo, gostaŕıamos de considerar as 4 permutações abaixo
como iguais:
Portanto, a resposta é P4
4 = 4!
4 = 3! = (PC)4
Solução 2:
Como o que importa é a posição relativa das crianças, há uma forma de colocar a primeira e a
segunda criança na roda. Há duas formas de colocar a terceira criança na roda: a direita da primeira
(e esquerda da segunda) ou a esquerda da primeira (e direita da segunda). Há três formas de colocar
a quarta criança na roda: a direita da primeira, a esquerda da primeira, ou oposta à primeira (entre
a segunda e a teceira). Portanto, a resposta é 1 ∗ 2 ∗ 3 = (PC)4
Exemplo 2: Há 7 crianças, contando com Ana e Bernardo. De quantas maneiras podemos formar
uma roda de ciranda:
(a) sem restrições?
(b) sendo que Bernardo fica exatamente a direita de Ana?
(c) sendo que Bernardo fica ao lado de Ana (esquerda ou direita)?
Solução (a): (PC)7 = 6! = 720. Obtido diretamente pela fórmula vista anteriormente.
1
Solução (b):
Primeira solução: Pensando inicialmente em uma FILA: consideramos Ana e Bernardo como
um ”bloco”; permutamos 6 coisas: as 5 crianças restantes e o bloco com Ana e Bernardo; o resul-
tado seria P6 = 6!. Nesse caso, cada configuração que gostaŕıamos foi contada 6 vezes (exemplo:
AB12345,1AB2345,12AB345,1234AB5,1234AB5,12345AB). Portanto, a resposta é 6!
6 = 5! = 120
Segunda solução: Permutamos, de maneira circular, as 5 outras crianças. Há (PC)5 = 4! maneiras
de fazer isso. Com 5 crianças na roda, há 5 espaços (vide figura abaixo) para colocar a dupla Ana e
Bernardo
Portanto, a resposta é 4! ∗ 5 = 5! = 120
Solução (c): Para cada configuração considerada em (b), temos 2! = 2 configurações em (c), já que
Ana pode estar tanto à esquerda quanto à direita de Bernardo. Portanto, a resposta é 120 ∗ 2! = 240
Exemplo 2: De quantos modos 5 meninas e 5 meninos podem formar uma roda de ciranda de
modo que meninos e meninas fiquem intercalados?
Resposta:
Solução 1: Há 2.(5!)2 modos de organizar uma FILA de modo que as meninas e os meninos se
intercalem (permute os 5 meninos nas posições 1,3,5,7,9 e as 5 meninas nas posições 2,4,6,8,10, além
da permutação dos 5 meninos nas posições 2,4,6,8,10 e as 5 meninas nas posições 1,3,5,7,9). A cada
10 configurações obtidas em fila, gostaŕıamos de contar apenas 1 por conta das equivalências obtidas
pelo formato circular. Portanto, a resposta é 2.(5!)2/10 = 2880
Solução 2: Há (PC)5 = 4! maneiras de permutar os 5 meninos em roda. Dessa maneira, aparecerão
5 espaços entre os meninos para serem preenchidos pelas 5 meninas de uma das P5 = 5! maneiras (a
permutação considerada aqui já não é mais circular, pois, fixados os meninos, a posição das meninas
não é coincidente por rotação). Portanto, a resposta é (PC)5P5 = 4!5! = 2880.
2