Aula 03 Permutação Circular

Prévia do material em texto

ANÁLISE COMBINATÓRIA
AULA 3- PERMUTAÇÃO CIRCULAR
Tema da Apresentação
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.
Tema da Apresentação
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:
 
Tema da Apresentação
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?
 
Tema da Apresentação
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?
 
Tema da Apresentação
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.
Tema da Apresentação
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
 
Tema da Apresentação
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.
Tema da Apresentação
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?
Tema da Apresentação
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”
Tema da Apresentação
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. 
 
Tema da Apresentação
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.
Tema da Apresentação
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.
 
Tema da Apresentação
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.
Tema da Apresentação
PERMUTAÇÃO CIRCULAR– AULA 3
ANÁLISE COMBINATÓRIA
EXEMPLOS
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. 
 
Tema da Apresentação
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?
Tema da Apresentação
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?
Tema da Apresentação
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
Tema da Apresentação