Permutação Circular e Permutações Caóticas

Prévia do material em texto

ANÁLISE COMBINATÓRIA
AULA 3- PERMUTAÇÃO CIRCULAR
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
Conteúdo Programático desta aula
. Permutações Circulares
Definição. Notação. Fórmula.Exercícios.
. Permutações Caóticas
Definição.Notação.Fórmula.Exercícios. 
. Princípio das Gavetas de Dirichlet
Exercícios.
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
PERMUTAÇÕES CIRCULARES
DEFINIÇÃO
Permutações Circulares são as realizadas em torno de um
círculo e contadas sempre no mesmo sentido, a partir de um
mesmo elemento.
NOTAÇÃO
que se lê: “permutações circulares de m elementos”
FÓRMULA
O número das permutações circulares de m elementos
distintos é dado por:
( )mPC
( ) )!1( −= mPC m
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
EXERCÍCIOS:
1.De quantas formas distintas oito pessoas podem se sentar
em volta de uma mesa circular?
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
2. Com algumas crianças podemos formar setecentos e vinte
rodas de ciranda. Quantas crianças fazem parte dessa
brincadeira?
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
3. Um grupo de nove pessoas vai se sentar ao redor de uma
mesa redonda. Sendo esse grupo composto por cinco
mulheres e quatro homens de quantos modos isso pode ser
feito de forma que as pessoas de mesmo sexo permaneçam
juntas?
SOLUÇAO:
Como as pessoas de mesmo sexo devem permanecer
juntas, podemos considerar como se tivéssemos dois blocos
distintos: um de homens e outro de mulheres. Assim, fazendo
a permutação circular deles, temos:
Observe que é evidente que só há uma maneira de se
organizar dois elementos de forma circular.
1!1)!12()( 2 ==−=PC
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
Note porém que a ordem dos componentes de mesmo
sexo pode mudar e, essa alteração, não se dá de forma
circular pois estamos trocando a ordem dos elementos no
mesmo grupo.
Daí:
.para as mulheres, temos:
.para os homens, temos:
Logo, pelo Princípio Multiplicativo, temos:
modos diferentes
maneirasP 1201.2.3.4.5!55 ===
maneirasP 241.2.3.4!44 ===
288024.120.1..)( 452 ==PPPC
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
4. Seis pessoas estão sentadas ao redor de uma mesa
redonda. Determine o número de maneiras diferentes que
elas podem trocar de lugar entre si de modo que pelo menos
uma delas termine com pelo menos um de seus vizinhos
sentado em outra posição.
SOLUÇÃO
Temos disposições
possíveis após as trocas de posição.
Só há uma única situação em que a condição do
enunciado não é satisfeita,ou seja, aquela em que as pessoas
se sentam nos mesmo lugares.
Logo, há 120–1=119 maneiras possíveis.
1201.2.3.4.5!5)!16()( 6 ===−=PC
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
5. A diretoria de um clube é composta por um presidente, um
vice-presidente e cinco membros do conselho deliberativo. De
quantos modos diferentes eles podem se reunir em torno de
uma mesa redonda de modo que o presidente e o vice-
presidente permaneçam sempre juntos?
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
PERMUTAÇÕES CAÓTICAS
DEFINIÇÃO
Uma permutação de n elementos é chamada de caótica
(ou “desarranjo”) quando nenhum deles se encontra na
posição original.
Ex.: Lembrando que elementos de conjuntos não obedecem
a uma ordenação mas os de permutações obedecem e
considerando as permutações dos elementos do conjunto
{1,2,3}, temos:
{1,2,3} , {1,3,2} , {2,1,3} , {2,3,1} , {3,1,2} e {3,2,1}.
Dentre essas permutações, as duas {2,3,1} e {3,1,2} são
caóticas.
NOTAÇÃO
que se lê: “permutações caóticas de n elementos”nD
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
FÓRMULA
, onde
é o número de permutações caóticas.
Podemos também usar a fórmula , onde
representa o inteiro mais próximo de x e o número “e” é
aproximadamente igual a 2,72.
( ) 





−++−+−+−=
!
1
1...
!5
1
!4
1
!3
1
!2
1
!1
1
1!
n
nD
n
n
nD






=
e
n
Dn
!
 x
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
EXEMPLO
Quantos são os anagramas da palavra LUGAR em que
nenhuma das letras esteja na posição ocupada originalmente?
SOLUÇÃO:
Temos que determinar o número de permutações caóticas
de 5 elementos (LUGAR – 5 letras => n=5)
Daí:
anagramas.4444
120
152060
.120
120
1
24
1
6
1
2
1
!.5
!5
1
!4
1
!3
1
!2
1
!1
1
1!.5
5
5
==




 −+−
=
=





−+−=





−+−+−=
D
D
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
Poderíamos também ter usado a fórmula .
Daí, para n=5 e e=2,72 , temos:
anagramas.






=
e
n
Dn
!
  4411,44
72,2
120
72,2
!5
55 ==





=





= DD
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
PRINCÍPIO DAS GAVETAS DE DIRICHLET
Se “n” objetos forem colocados em, no máximo,
“n-1” gavetas, então pelo menos uma delas conterá pelo
menos dois objetos.
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
EXEMPLOS
1.Um saco contém 25 bolas brancas, 18 bolas verdes e 11
bolas pretas, todas iguais em tamanho e peso. Qual o número
mínimo de bolas que você deve retirar desse saco para, sem
observar, ter certeza de ter retirado uma bola branca?
SOLUÇÃO:
Note que existe a possibilidade de você extrair todas as
bolas verdes e pretas antes de extrair uma branca. Logo você
deverá extrair 18+11+1= 30 bolas para ter certeza de que
extraiu uma bola branca.
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
2. Qual o número mínimo de pessoas que devemos ter em um
grupo para garantirmos que duas delas tenham nascido num
mesmo dia da semana?
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
3. Qual o número mínimo de escoteiros que devemos ter em
um grupo de modo que possamos garantir que cinco deles
tenham nascidos num mesmo mês?
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
Na aula de hoje estudamos:
. As permutações circulares.
. As permutações caóticas.
. O princípio das gavetas de Dirichlet.
. Exercícios