AULA 03 – PERMUTAÇÃO CIRCULAR

Prévia do material em texto

ANÁLISE COMBINÁTORIA
AULA 03 – PERMUTAÇÃO CIRCULAR 
OBJETIVOS- 1- Reconhecer Permutações Circulares; 2- Relacionar Permutações Circulares com permutações simples.
INTRODUÇÃO Nesta aula, estudaremos Permutações Simples e com Elementos Repetidos aprendendo a diferenciar uma da outra. Abordaremos essas duas técnicas de contagem nas variadas situações problema. Aprenderemos quando devemos optar por esses métodos de contagem.
Caro aluno! Vamos seguir com o nosso curso de Análise Combinatória. Na aula passada, vimos as permutações simples e com elementos repetidos. Hoje, abordaremos as permutações circulares. Porém, antes do conceito propriamente dito, vamos a um exemplo para facilitar nosso entendimento.
Premissa 
Agora, vamos a nossa pergunta principal: De quantas maneiras distintas os presidentes desses países podem se sentar à mesa? RESPOSTA: À primeira vista, parece um problema bastante complicado, porém, você constatará que não é. Estamos diante de uma Permutação Circular.
Vamos pensar do seguinte modo...
Partindo de A, no sentido horário, temos a seguinte ordem: ABCDE Partindo de B, temos: BCDEA Partindo de C, temos: CDEAB De D , ficamos com : DEABC Por fim , saído de e , ficamos com: EABCD
ATENÇÃO ! Se nós tivéssemos organizando esses presidentes em uma fila indiana, teríamos 5 permutações distintas. Porém, como estão sentados a uma mesa redonda, essas 5 permutações, na verdade, correspondem a 1 única permutação circular desses 5 elementos distintos.
Primeiro passo 
Até aqui, tudo bem, não? Então vamos adiante! Já estamos chegando ao final de nosso exemplo. Com a comparação anterior, conseguimos estabelecer um paralelo entre as permutações em linha, ou fila indiana, com as permutações circulares. Basta pensarmos em uma regra de três simples. Veja ao lado...
	Permutações simples em linha ou fila indiana de 5 elementos distintos
	Permutações circulares de 5 elementos distintos
	1
x
	5
5!
Segundo passo Vamos então generalizar esse raciocínio, ou seja, vamos pensar no caso de n pessoas que devem se sentar a uma mesa circular. Isso corresponde a uma permutação circular de n elementos distintos. Seguiremos alguns passos para o nosso raciocínio: 01 - Vimos que 1 permutação circular de 5 elementos distintos pode ser vista a partir de seus 5 elementos, correspondendo a 5 permutações simples desses mesmos 5 elementos distintos.  
02- Logo, se tomarmos n elementos distintos, em um dispositivo circular, teremos n pontos de partida para visualizar a ordem em que estão dispostos. Porém, todas essas n maneiras correspondem a somente uma no ponto de vista circular.
03- Assim, podemos realizar novamente a nossa regra de três básica:
	1
	n
	x
	n!
04- Finalizando os nossos cálculos:
X = = = (n – 1)!
05 - Por fim, a permutação circular de n elementos distintos pode ser escrita como (n-1)!
X = = = (n – 1)!
Comentário: Espero que tenha compreendido o nosso exemplo. Não foi difícil!
Definição Agora vamos a nossa definição:
A permutação circular de n elementos distintos, designada por PCn, é dada por:
PCn=(n – 1) !
Vejamos outros exemplos para intensificar a nossa definição. Começando por um bem simples.
EXEMPLOS 
01- De quantas formas distintas 7 pessoas podem se sentar em volta de uma mesa circular? Resolução 1: Como já vimos, a permutação circular de 7 elementos distintos é : PC7=( 7 -1 )! = 6! = 720 Logo, há 720 formas desse sentar em volta dessa mesa.
02- Em uma brincadeira de ciranda, isto é, jogo em que as pessoas dão as mãos e formam uma roda, é possível formar 120 disposições distintas com as pessoas que estão participando. Qual é o número de participantes dessa brincadeira? Resolução 2: Para permutação circular, sabemos que PCn = ( n -1 )! - Temos que PCn= 120 – Então, 120= (n-1)! Temos também que 5! = 120. – Portanto, 5! = (n -1)! . Logo, n=6 – O número de participantes é 6 
03- Quatro mulheres e três homens vão se sentar ao redor de uma mesa redonda. De quantas disposições diferentes isso pode ser feito, se pessoas do mesmo sexo devem permanecer juntas?
Resolução 3:( salvo) 
Sabemos que as pessoas do mesmo sexo devem permanecer juntas. Assim, podemos pensar em 2 blocos distintos: um de homens e outro de mulheres. Dessa forma, realizamos a permutação circular deles: PC2= (2-1)! = 1! =
1. Isso é bem óbvio, não?! Só há uma maneira de organizarmos 2 elementos de maneira circular.
Porém, a ordem entre os componentes de mesmo sexo pode mudar. Note que esta alteração não se dá de forma circular, pois estamos trocando a ordem dos elementos no mesmo grupo. Logo, para o grupo de mulheres, temos uma permutação simples de 4 elementos, a saber: P4 = 4! =4.3.2.1 = 24 maneiras de se organizar as mulheres. Por sua vez, o raciocínio é exatamente o mesmo para os homens: é uma permutação circular de 3 elementos distintos. Assim: P3 = 3! = 3.2.1 = 6. Por fim, pelo princípio multiplicativo, temos: PC2.P4.P3 = 1!.4!.3! = 24.6= 144.Logo, há 144 formas de se realizar disposições. Note que o conceito de permutação circular é bastante simples. Devemos tê-lo em mente de forma a empregar a técnica adequada. Isso está relacionado à interpretação do problema a ser resolvido. Outro aspecto muito importante e útil é a observação do emprego de outros conceitos já aprendidos. No exemplo anterior, observamos a utilização da permutação simples aliada à permutação circular. Isso é bastante comum. 
04- Uma família é composta por 7 pessoas, dentre elas, o pai, a mãe e os 5 filhos. Quando vão a um restaurante, sempre ocupam uma mesa redonda. Em quantas disposições distintas essa família pode ocupar os assentos em torno da mesa, de modo que o pai e a mãe sempre permaneçam juntos?
Resolução 04 – (salvo) Como os pais devem permanecer juntos, podemos pensar em um bloco formado por eles. Como temos 6 elementos, estamos diante de uma permutação circular de 6 elementos: PC6 = (6-1)! = 5! = 120. Todavia, temos também as possibilidades de reorganizar os integrantes do bloco. Para o bloco composto pelos pais, como são 2 elementos, temos a permutação simples: P2 = 2! = 2.1 = 2 maneiras. Como já vimos antes, pelo Princípio Multiplicativo, o total de disposições diferentes será: PC6.P2 = (6-1)!.2! = 2.1.5.4.3.2.1 = 240. Logo, temos 240 disposições distintas.
05- Uma família é composta por 6 pessoas: o pai, a mãe, e os 4 filhos. Quando vão a um restaurante, sempre ocupam uma mesa redonda. Em quantas disposições distintas essa família pode ocupar os assentos em torno da mesa, de forma que os pais fiquem sempre juntos e os dois filhos briguentos separados?
Resolução 05- ( salvo) Trata-se de um problema em que devemos pensar de forma análoga ao exemplo anterior, porém trabalharemos com a noção de complemento, que foi vista em aulas anteriores. Pensaremos em 2 grupos: 1 grupo formado pelos pais e outro formado pelos filhos briguentos. Vamos raciocinar que queremos que os pais fiquem juntos (o problema já nos dá essa informação) e que os filhos briguentos também permaneçam juntos. Vamos ao esquema que facilita a nossa compreensão:
Através da visualização, temos 4 elementos que permutarão ao redor da mesa. Logo, temos uma permutação circular de 4 elementos: PC4 = (4-1)! = 3! = 3.2.1 = 6. Poderemos também, além da permutação circular, alterar a ordem dos elementos dentro dos grupos formados. Para o grupo dos pais, formado por 2 pessoas, temos a permutação simples de 2 elementos, assim como para o grupo dos filhos briguentos. Então, temos duas permutações: 2.P2 = 2. 2! = 2.2 = 4.
Pelo Princípio Multiplicativo, temos que o total dessa hipótese é: PC4.P2.P2 = (4-1)!.2!.2! = 6.4 = 24. Agora, pensaremos apenas na restrição de que os pais da família devam permanecer juntos. Ficamos com o seguinte esquema:
Dessa forma, fica claro que temos 5 elementos que estarão permutando entre si de forma circular. Ou seja: PC5 = (5-1)! = 4! = 4.3.2.1 = 24. Ainda, temos a permutação entre o grupo dos pais: P2 = 2! = 2. Pelo Princípio Multiplicativo, ficamos: PC5.P2 = 4!.2! = 48 formas. Devemos pensar na noção de complemento: se na primeira hipótese os filhos briguentos estavam juntos e na segunda não houve restrição para a organização dos filhos, temos que a diferença dessas hipóteses representa justamente o que o problema nos pede: pais juntos e filhos briguentos separados um do outro. Por fim, temos que: : PC5.P2 - PC4.P2.P2 = (4!.2!) - [(4-1)!.2!.2!] = 48-24 = 24 disposições Logo, há 24 disposições diferentes de se sentar ao redor da mesa.
PERMUTAÇÕES CAÓTICAS
Vamos aproveitar o momento para introduzir as Permutações caóticas, já que o conceito de permutações circulares foi fácil, não?
Vamos formar todas as permutações possíveis com os elementos do conjunto {1,2,3}. Devemos lembrar que elementos de conjuntos não obedecem a uma ordenação , mas as permutações sim .
Vamos lá? (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Aqui estão todas as permutações possíveis com esses 3 elementos.
Quantas dessas são caóticas? Basta observar e chegaremos que a resposta é 2. São elas: (2,3,1) e (3,1,2). Vamos pensar agora em quantas permutações caóticas temos com os elementos do conjunto {1,2,3,4}. Com um pouco de trabalho e paciência, podemos verificar que a resposta é 9. São elas: 2143, 3142, 4123, 3412, 4312, 2413, 2341, 3421, 4321.
Agora vamos aos exemplos?
1- Suponha N(A) = n. Quantas são as funções f: A→A para as quais f(x)=x não possui solução?
RESOLUÇÃO 1- Quando tomamos o primeiro elemento do conjunto A, ele poderá ter como imagem qualquer elemento do conjunto A, exceto ele mesmo; portanto, poderá ter (n-1) possibilidades de imagem. Quando tomarmos o segundo elemento, novamente temos (n-1) possibilidades de imagem para esse elemento. Esse raciocínio é aplicado até o último elemento, onde teremos também (n-1) possibilidades de imagem. Pelo Princípio multiplicativo, teremos: (n-1)(n-1)(n-1)....(n-1)=(n-1)n Devemos ter sempre em mente todas as técnicas de contagem que já aprendemos.
2- Suponha N(A) = n. Quantas são as funções f: A→ A bijetoras para as quais a equação f(x) = x não possui solução?
RESOLUÇÃO 2-
3- Determine o número de permutações caóticas de (1,2,3,4,5,6,7,8,9,10), nas quais os números 1, 2, 3, 4, 5 ocupam, em alguma ordem, os cinco primeiros lugares. 
RESOLUÇÃO 3 - Devemos atentar para o fato de que o problema nos pede permutações caóticas; portanto, nenhum elemento pode ocupar sua posição de origem. Daí, os elementos 1,2,3,4,5 devem ser arrumados caoticamente nos cinco primeiros lugares, e os elementos 6,7,8,9,10 devem ser arrumados caoticamente nos cinco últimos. Temos como resposta :D5x D5 =1936. Devemos fazer o cálculo para nos familiarizar com a fórmula.
 Principio de Dirichlet 
Como estamos aprendendo com esse curso de combinatório, não? Que tal avançaremos ainda mais?Um princípio bastante útil e bem interessante é o chamado “Princípio de Dirichlet”. Vejamos o que ele nos diz:
“Se n objetos forem colocados em, no máximo, (n-1) gavetas, então pelo menos uma das gavetas conterá ao menos dois objetos”.
Esse princípio é bastante simples.
Vamos pensar juntos.
↓
Quantas pessoas devem ter em uma sala de aula para garantirmos que, no mínimo, 2 delas nasceram no mesmo dia da semana? Imagine que a 1ª pessoa tenha nascido em um domingo, a 2ª na segunda-feira, a 3ª na terça-feira, a 4ª pessoa na quarta-feira e assim por diante. É claro que a 8ª pessoa irá coincidir com alguma das outras. Logo, o número mínimo que precisamos ter são 8 pessoas. Devemos observar que poderíamos ter mais de 2 pessoas que nasceram em um domingo. É exatamente por esse fato que o princípio fala em “pelo menos uma delas conterá dois objetos”.
EXEMPLOS 
Fácil, não? Esse princípio resolve uma série de problemas. Então vamos aos exemplos:
01- Qual é o número mínimo de pessoas que deve haver em um grupo para que se possa garantir que, nesse grupo, existam pelo menos 5 pessoas nascidas no mesmo mês?
RESPOSTA: Pensemos da seguinte forma: Para garantirmos que, no mínimo, 2 nasceram no mesmo mês, precisamos de 13 pessoas (exatamente 12 + 1). Para asseguramos que, pelo menos 3, nasceram no mesmo mês, precisamos de 25 pessoas (exatamente 2 x 12 + 1). Então, podemos inferir que para 5 pessoas no mesmo mês, temos: 4x12+1 = 49 pessoas.
02- Quantas pessoas devem ter, no mínimo, em uma sala, de modo que possamos garantir que 4 delas tenham nascido em um mesmo mês?
RESPOSTA: Essa foi fácil demais, não? Para garantirmos tal fato será necessário que tenhamos: 3 x 12 +1=37 pessoas.
03 - Uma caixa contém 100 bolas de cores distintas. Destas, 30 são vermelhas, 30 são verdes, 30 são azuis e 10 são pretas. Qual o menor número de bolas que devemos tirar da caixa, sem ver suas cores, para termos a certeza de que a caixa contém, pelo menos, 10 bolas da mesma cor?
RESPOSTA: Se tirarmos 5 bolas, pelos menos 2 terão a mesma cor, não? Claro que sim. E se tirarmos 9 bolas? Pelo menos 3 terão a mesma cor. 
Vamos fazer uma generalização? 5 = 4 x 1 + 1, 9 = 4 x 2 +1. Então, para pelo menos n bolas, teremos: 4x (n-1)+1. Portanto, se estamos pedindo pelo menos 10, teremos como resposta: 4 x(10-1)+1=37 bolas.
04 - Célia guarda suas blusas, em uma única gaveta, em seu quarto. Nela encontram-se 7 blusas azuis, 9 amarelas, 1 preta, 3 verdes e 3 vermelhas. Uma noite, no escuro, Célia abre a gaveta e pega algumas blusas. Qual o número mínimo de blusas que ela deve pegar para ter a certeza de ter, dentre as blusas, 2 da mesma cor?
RESPOSTA : Esse também foi muito fácil, não? Depois que pegamos o jeito não erramos mais. A reposta é clara: 6 blusas.
SINTESE DA AULA Nesta aula, você: Aprendeu o conceito de Permutação Circular, o de Permutação Caótica e o Princípio de Dirichlet; Analisou e compreendeu a importância desses conceitos como ferramentas valiosas na resolução de problemas de contagem.