Aula 05 - Permutações Circulares

Prévia do material em texto

1
 
 
Aula 5 
 
 
PERMUTAÇÕES CIRCULARES 
 
 
Objetivos 
Reconhecer uma permutação circular. 
Calcular o número de permutações circulares. 
 
 
Exemplo 1 
 
 Quantas rodas de ciranda podem ser formadas com 3 crianças? 
 
 Denominemos as crianças de A, B e C. Com as 3 crianças podemos formar 3! filas 
ou permutações lineares, a saber 
ABC ACB BAC BCA CAB CBA 
 
 Suponhamos que em cada uma das disposições acima, as crianças dêem as mãos 
para formar uma roda de ciranda. 
 
 Observemos que as disposições das crianças nas filas ABC, CAB e BCA formam a 
mesma roda. 
 
 
 
 O mesmo acontece com as outras três filas que correspondem a uma outra roda. 
 
 
 
 Portanto, considerando equivalentes as disposições que possam coincidir por uma 
simples rotação, temos somente 2 rodas de ciranda distintas. 
 
 
 Nas permutações simples importam os lugares que os elementos ocupam. 
Nas permutações circulares importa apenas a posição relativa dos elementos entre 
si. 
A 
B 
C 
C A 
B 
B 
C 
A 
A 
A 
A 
B B 
B 
C 
C 
C 
Fundação CECIERJ Maria de Fatima Soares da Silva
 2
 
 
 
 Permutação circular é uma ordenação sem início ou fim de n elementos. 
Notaremos por (PC)n . 
 
Exemplo 2 
 
 Quantas rodas de ciranda podem ser formadas com n crianças? 
 
 Uma roda, com n crianças, pode ser aberta de n modos diferentes para se formar 
uma fila, ou seja, n filas formarão a mesma roda. 
 
 Como existem n! filas possíveis, por uma regra de 3 simples, 
 n filas - 1 roda 
 n! filas - (PC)n rodas 
obtemos 
(PC)n = n
n! = (n- 1)! rodas possíveis. 
 
 
Exemplo 3 
 
 De quantas maneiras podemos dispor 3 meninos e 3 meninas numa roda de 
ciranda de modo que um menino não fique ao lado de outro menino? 
 
1ª solução 
 Determinemos, inicialmente, o número de permutações lineares com as 6 crianças 
de modo que se alterne meninos e meninas. 
 
 Começando com um menino, temos 3 possibilidades; ao seu lado teremos que 
colocar uma menina tendo portanto 3 possibilidades. Na terceira posição terá que ser um 
menino, tendo 2 possibilidades, na quarta posição uma menina, tendo 2 possibilidades e 
nas quinta e sexta posições temos somente uma possibilidade para cada. 
 
O A O A O A 
↑ ↑ ↑ ↑ ↑ ↑ 
3 3 2 2 1 1 
 
Portanto, há 3.3.2.2.1.1 = 36 permutações lineares começando com um menino. 
 
 Começando com uma menina, temos 3 possibilidades; ao seu lado teremos que 
colocar um menino tendo portanto 3 possibilidades. Na terceira posição terá que ser uma 
menina, tendo 2 possibilidades, na quarta posição um menino, tendo 2 possibilidades e 
nas quinta e sexta posições temos somente uma possibilidade para cada. 
 
A O A O A O 
↑ ↑ ↑ ↑ ↑ ↑ 
3 3 2 2 1 1 
 
Há também 36 permutações lineares começando com uma menina. 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 3
 
 
 
No total temos 72 permutações lineares. 
 
 Como 6 permutações lineares correspondem a uma permutação circular, temos 
6
72 = 12 permutações circulares 
 
2ª solução 
 Podemos, inicialmente, dispor os 3 meninos em uma roda. Isto pode ser feito de 
(PC)3 = (3-1)! =2! maneiras. 
 
 Temos 3 possibilidades de colocar a primeira menina entre 2 meninos em cada uma 
das 2 rodas anteriores. Para colocarmos a 2ª menina restam duas possibilidades e a 3ª 
delas só uma possibilidade. 
 
 Pelo princípio multiplicativo temos 2!.3.2.1 = 12 permutações circulares, ou seja, 12 
rodas distintas. 
 O 
 → . ← 
 
 O . . O 
 ↑ 
 
 
Exemplo 4 
 
 De quantos modos 9 crianças podem brincar de roda de modo que três 
determinadas crianças fiquem sempre juntas? 
 
 Vamos considerar as 3 crianças que devem ficar juntas como sendo um só 
elemento. Representemos por C uma criança. 
 C 
 C C 
 C C 
 C C 
 C C 
 
Teríamos permutação circular de 7 elementos, obtendo (7–1)! = 6! rodas possíveis; 
mas as crianças que ficam juntas podem permutar entre si de 3! maneiras dentro de cada 
uma das 6! rodas. 
 
 Logo, temos 6!.3! = 4320 rodas possíveis. 
 
 
Exemplo 5 
 
De quantos modos distintos posso dispor 6 casais em torno de uma mesa 
circular de modo que um determinado homem sente-se ao lado de sua esposa e 
duas outras determinadas esposas precisam sentar-se uma ao lado da outra? 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 4
 
 
 
Sejam H1 e M1 as pessoas que formarão o casal que se sentarão juntos e M2 e M3 
as mulheres que precisam se sentar juntas. 
H1 M1 
. . 
. . 
 . .M2 
 . .M3 
. . 
. . 
H1 e M1 formam um “elemento” mas que podem permutar entre si na mesa, o 
mesmo acontecendo com M2 e M3. 
 
Temos então 10 “elementos” em permutação circular; logo, obtemos 
 
2.2.(PC)10 = = 4.9! = 1.451.520 permutações circulares. 
 
 
 
Exemplo 6 
 
De quantos modos distintos posso dispor 6 casais em torno de uma mesa 
circular de modo que cada homem sente-se ao lado de sua esposa e haja dois 
casais determinados cujas esposas precisam sentar-se uma ao lado da outra? 
 
876
MH 
876
HM 
 
⎩⎨
⎧
M
H
 
⎪⎪⎭
⎪⎪⎬
⎫
H
M
M
H
 
⎩⎨
⎧
M
H
 
⎪⎪⎭
⎪⎪⎬
⎫
H
M
M
H
 
 
 ⎩⎨
⎧
M
H
 ⎭⎬
⎫
M
H
 ⎩⎨
⎧
M
H
 ⎭⎬
⎫
M
H
 
 
As quatro pessoas que formam os 2 casais cujas esposas precisam sentar-se 
juntas são consideradas como “um elemento” e cada um dos outros 4 casais também 
como um elemento. Temos então 5 elementos em permutação circular, totalizando (PC)5 
= 4! = 24 permutações. 
 
 Mas, cada um dos 5 “elementos’ anteriores também podem permutar em cada uma 
das 24 permutações circulares. Logo, temos 2.2.2.2.2.24 = 768 permutações circulares. 
 
 
Esteja atento ao enunciado de cada questão, pois um pequeno detalhe 
modifica o problema. Compare os exemplos 5 e 6. 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 5
 
 
Exemplo 7 
 
De quantas maneiras distintas podemos dispor 3 homens, 2 mulheres e 4 
crianças em torno de uma mesa circular de modo que as crianças fiquem juntas e 
um homem não se sente ao lado de outro homem? 
 
 Como as crianças deverão ficar juntas, elas serão consideradas como um único 
elemento. 
 
 
1ª solução 
 Como um homem não pode se sentar ao lado de outro homem, entre dois homens 
poderemos ter ou o grupo de crianças ou uma mulher. 
 Para ocupar a primeira posição na permutação linear podemos ter um dos 3 
homens ou uma das duas mulheres ou o grupo de crianças, no total de 6 possibilidades. 
 
 Para ocupar a segunda posição temos somente 3 possibilidades, pois se na 1ª 
posição foi ocupada por um homem, na segunda posição só podemos ter uma das 2 
mulheresou o grupo de crianças, no total de 3 possibilidades ou vice-versa. 
 
 Para as demais posições, a ordem já está determinada pela primeira; logo, 
_ _ _ _ _ _ 
↓ ↓ ↓ ↓ ↓ ↓ 
6 3 2 2 1 1 
Pelo princípio multiplicativo temos 6.3.2.2.1.1 = 72 permutações lineares. 
 
Mas, as crianças também podem permutar entre si de 4!=24 maneiras em cada 
uma das 72 permutações lineares, totalizando 24.72 = 1728 permutações lineares. 
 
Como 6 permutações lineares correspondem a 1 permutação circular temos 1728
6
= 
= 288 permutações circulares. 
 
 
2ª solução 
 
 Como um homem não pode se sentar ao lado de outro homem, entre dois homens 
poderemos ter ou o grupo de crianças ou uma mulher. 
 
 Na permutação linear, começando por um homem, temos 3 possibilidades. Na 2ª 
posição temos 3 possibilidades que pode ser uma das 2 mulheres ou o grupo de crianças. 
Na 3ª posição um homem, com 2 possibilidades e assim por diante: 
 
H M ou C H M ou C H M ou C 
 ↓ ↓ ↓ ↓ ↓ ↓ 
 3 3 2 2 1 1 
 
Pelo princípio multiplicativo temos 36 permutações lineares. 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 6
 
 
Poderemos também começar por uma mulher ou grupo de crianças, no total de 3 
possibilidades, a seguir, um homem, com 3 possibilidades, e assim em diante 
 
M ou C H M ou C H M ou C H 
 ↓ ↓ ↓ ↓ ↓ ↓ 
 3 3 2 2 1 1 
 
Pelo princípio multiplicativo temos 36 permutações lineares 
 
Mas, as crianças também podem permutar entre si de 4! maneiras em cada uma 
das 2.36=72 permutações lineares anteriores, totalizando 24.72 = 1728 permutações 
lineares. 
 
Como 6 permutações lineares correspondem a 1 permutação circular temos 
1728
6
 = 288 permutações circulares 
 
3ª solução 
 
 Colocando os 3 homens numa mesa circular, temos (PC)3 = 2! = 2 permutações 
circulares. 
 
A primeira mulher tem 3 maneiras de se sentar entre dois homens em cada uma 
das 2 permutações circulares anteriores, totalizando 2.3 = 6 permutações circulares 
distintas. 
 
 .H 
 → . . ← 
 H . . H 
 . 
 ↑ 
 
Uma vez colocada a primeira mulher, tem-se 2 maneiras de se colocar a 2ª mulher 
em cada uma das 6 permutações, totalizando 6.2 = 12 permutações circulares. 
 
Já tendo sido colocadas as mulheres e os homens, o grupo de crianças só pode ser 
colocado de uma única maneira na mesa circular em cada uma das 12 permutações. 
Mas, as crianças podem permutar entre si de 4! maneiras. 
 
Total = 4! . (PC)3 . 3. 2.1 = 288 permutações circulares. 
 
H 
. 
M ou C . . M ou C 
 
H . . H 
 
. M ou C 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 7
 
 
Exemplo 8 
 
Quantos colares podem ser formados com 7 contas diferentes? 
Como um colar é um objeto circular, poderíamos pensar que temos 
(PC)7 = 6! = 720 permutações circulares 
e, portanto, 720 colares diferentes. 
Mas, observe as disposições abaixo. 
 I II 
 
 A disposição I é obtida de II por rebatimento, constituindo, portanto, o mesmo colar. 
Na realidade, temos somente 
2
720 = 360 colares diferentes. 
 
 
 
 
Exercícios propostos 
 
 1) Quantas rodas de ciranda podem ser formadas com 8 pessoas? R.: 5040 
 
 2) De quantos modos distintos 7 crianças podem brincar de roda de modo que duas delas 
fiquem sempre juntas? R.: 240 
 
3) De quantos modos podemos formar uma roda de ciranda com 7 crianças de modo que 
duas determinadas crianças não fiquem juntas? R.: 480 
 
4) De quantos modos 5 mulheres e 6 homens podem formar uma roda de ciranda de 
modo que as mulheres permaneçam juntas? R.: 86400 
 
5) De quantos modos 8 casais podem formar uma roda de ciranda de modo que cada 
homem permaneça ao lado de sua mulher? R.: 1.290.240 
 
6) De quantos modos 8 casais podem formar uma roda de ciranda de modo que cada 
homem permaneça ao lado de sua mulher e que pessoas do mesmo sexo não fiquem 
juntas? R.: 10080 
 
7) De quantas maneiras distintas podemos dispor 5 meninos e 5 meninas numa roda de 
ciranda de modo que um determinado menino só fique ao lado de menina? R.: 100.800 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 8
 
 
8) (UERJ) Um grupo constituído por 4 mulheres e 4 homens deve ocupar as 8 cadeiras 
dispostas ao redor de uma mesa circular. O grupo deve ser acomodado de modo que 
cada homem sente entre 2 mulheres. 
 João e Maria estão nesse grupo de pessoas; entretanto, por motivos de ordem 
estritamente pessoal, não podem sentar-se lado a lado. Duas acomodações das pessoas 
ao redor da mesa são consideradas diferentes quando pelo menos uma das pessoas não 
tem o mesmo vizinho à direita nas duas acomodações. 
 Determine o número de diferentes acomodações possíveis dessas 8 pessoas ao 
redor da mesa circular. R.: 72 
 
9) De quantas maneiras distintas podemos dispor 4 homens e 6 mulheres em torno de 
uma mesa circular de modo que 3 quaisquer mulheres fiquem sempre juntas e um homem 
não se sente ao lado de outro homem? R.: 17280 
 
10) Uma pulseira será formada usando-se 10 pequenas peças distintas. 
a) Quantas pulseiras distintas poderão ser formadas? R.: 
2
!9 
b) Quantas pulseiras distintas poderão ser formadas se a pulseira tiver um fecho? R.: 
2
!10 
Fundação CECIERJ Maria de Fatima Soares da Silva