Análise Combinatória

Análise Combinatória

(Parte 4 de 7)

47) Pedro dispõe de uma coleção de 40 bonés. Dentre eles existem, respectivamente sete, cinco e nove idênticos entre si. Deseja dispô-los em linha numa prateleira. De quantos modos distintos Pedro pode realizar esse processo?

3.3 - Permutações circulares (Assunto opcional - somente segunda etapa vestibular UFMG)

Permutações circulares é uma ferramenta intrinsecamente ligada à permutações simples. Difere dessa pelo fato de os elementos em questão estarem dispostos em fila circular, isto é, através de um circulo. Observe o exemplo: De quantos modos podemos dispor as letras da palavra PRATO em um circulo em lugares equiespaçados (as letras deverão ter a mesma distancia entre elas). ?

Primeiro devemos imaginar um círculo e em seguida as letras da palavra em questão dispostas ao redor do círculo (figura 1).

Se colocarmos o P no lugar de R, R no lugar de A, A no lugar de T, T no lugar de O e O no lugar de P, na verdade não criaremos uma nova fila circular, apesar de termos mudado todos os elementos de posição. O que ocorreu, de fato, foi apenas uma rotação entre os elementos, observe na figura 2. Dessa forma, diferentemente do que acontece em uma fila linear, em uma fila circular a simples troca de posição dos elementos pode não formar uma nova fila. Como ocorreu acima. (O que fazer então?) Para contornar essa situação devemos fixar um dos elementos de uma fila e em seguida permutar o restante de maneira idêntica a uma fila comum. Observe na figura 3 acima. Com esse processo garantimos a não ocorrência de simples rotações e contamos todas as filas circulares com esses elementos. Já que ao fixarmos um elemento, “desmantelamos” a fila circular e criamos outra que se comporta como

FIGURA 1

FIGURA 2

P fixado

FIGURA 3

Prof. Gerson Henrique 25 uma fila linear. Finalmente, podemos dispor essas letras em uma fila circular de 4! maneiras. Uma vez que fixamos o P e permutamos os elementos restantes como se estivéssemos formando uma fila comum.

Note que 4! é justamente (5 -1)! 5 é a quantidade de elementos envolvidos na questão menos 1 que é o elemento fixado ou travado, para garantir a contagem de todas as permutações circulares.

Veja esses novos exemplos:

equivale a (10 -1)!

1) De quantos modos podemos dispor dez crianças em uma roda de ciranda? Ciranda é uma brincadeira em que as crianças são dispostas em uma fila circular. Assim para Garantir que simplesmente façamos uma rotação com as crianças devemos fixar uma delas. Em seguida permutamos as nove restantes como se tivemos dispondo-as em uma fila comum. Assim podemos obter 9! rodas de ciranda distintas que 2) De quantos modos podemos dispor circularmente 30 objetos diferentes em uma fila? A resposta a essa altura deve ser imediata. (30 -1)! maneiras distintas.

Para generalizar se possuímos n elementos distintos para dispormos em uma fila circular e de forma eqüidistante podemos realizar esse processo de (n – 1)! maneiras distintas. Simbolizamos por (PC)n. Dessa forma (PC)n = (n – 1)!

Exercícios Resolvidos

1) De quantos modos podemos dispor n crianças em uma roda de ciranda? A resposta deve ser imediata (n – 1)! maneiras.

2) De quantos modos podemos formar uma roda de ciranda com 6 crianças de modo Joãozinho e Mariazinha nunca fiquem juntos?

Já que essas duas crianças não podem ficar juntas, primeiro permutaremos circularmente as demais que são um total de quatro crianças (Chamaremos essas quatro de crianças 1,2,3 e 4) e em seguida introduziremos Joãozinho e Mariazinha garantindo que eles não fiquem juntos. Mas é simples garantir que eles não fiquem juntos. Basta colocarmos cada um nos espaços entre duas crianças acima e nunca colocar Joãozinho e Mariazinha no mesmo espaço.

aqui aqui a qui a qui

Prof. Gerson Henrique 26

Podemos dispor circularmente as crianças 1,2,3 e 4 de (4 – 1)! = 3! = 6 maneiras e seguidas contamos as maneiras de dispor Joãozinho e Mariazinha de 4 x 3 = 12 maneiras. Para finalizar podemos dispor essas seis crianças com Joãozinho e Mariazinha nunca juntos de

(4 – 1)! x 4 x 3 = 6 x 4 x 3 = 72 maneiras distintas

Para você resolver

48) Com algumas crianças podemos formar setecentos e vinte rodas de ciranda. Quantas crianças fazem parte dessa brincadeira?

49) De quantas maneiras podemos dispor 7 objetos (O1,O2,03,...,07) circularmente e eqüidistantes entre si de modo que:

a) O1 e O2 nunca fiquem juntos.

b) O1 e O2 fiquem sempre juntos.

c) O1 e O2 sempre permaneçam juntos e O1 a esquerda de O2.

d) O1, O2 e O3 sempre permaneçam juntos.

e) O1, O2 e O3 permaneçam juntos e O2 sempre entre O1 e O3. f) a soma dos índices de dois elementos consecutivos sempre resulte em oito, quando possível.

50) (IMPA) – Quantos dados diferentes de seis faces existem se a soma das faces opostas deve ser 7?

51) De quantos modos podemos dispor 5 meninas e 6 meninos em uma roda de ciranda de modo que as meninas sempre fiquem juntas? 52) Uma roda Gigante é constituída de 15 acentos duplos. Assim sendo de quantos modos podemos dispor 15 casais nesse Brinquedo de modo que sempre cada casal permaneça junto?

4 - Arranjos simples

A ferramenta arranjos simples é utilizada quando desejamos formar filas com p elementos escolhidos a partir de um grupo de m elementos, com p ≤ m. Se, por exemplo, de um grupo de oito (8) pessoas, devemos dispor cinco (5) delas em fila. De quantos modos podemos realizar tal processo?

Já sabemos pelo principio multiplicativo ou principio fundamental da contagem que podemos formar:

Desse modo obtemos 8 x 7 x 6 x 5 x 4 = 6720 filas com cinco pessoas escolhidas dentre oito.

Podemos concluir dessa maneira que Arranjos é uma aplicação do principio multiplicativo para formar filas quando for necessário escolher alguns elementos de um grupo para formar tal Fila. Simbolizaremos o resultado desse exemplo como A8,5 ( Arranjo 8 elementos tomados 5 a 5), isto é, formamos uma fila com cinco elementos selecionados de um grupo de oito. Também podemos encontrar o símbolo de arranjo como 85A.

Observe esse novo exemplo. De um grupo de 20 pessoas deseja-se formar uma fila com 5 delas. Quantas filas distintas podemos formar?

8 x 7 x 6 x 5 x 4

Prof. Gerson Henrique 27

A resposta é A20,5 = 20 x 19 x 18 x 17 x 16. Observe que realizamos o produto de 20 até 16. Desse modo o produto contém cinco números consecutivos, pois é o número de posições da fila.

Seguindo esse raciocínio A7,3 = 7 x 6 x 5, já que devemos realizar o produto de 7 pelos seus antecessores. Devemos usar três números que é o número de posições da fila em questão. Da mesma forma

A100,4 = 100 x 9 x 98 x 97, pois temos de escolher dentre 100 elementos 4 para serem dispostos em fila.

Esse resultado também pode ser reescrito em função dos valores 100 e 4, observe:

Note que esse resultado é idêntico a A100,4 = 100 x 9 x 98 x 97. Essa nova representação desse valor é motivada a aparecer apenas para efeito de generalização, isto é, para se obter uma fórmula geral para arranjos.

Da mesma Forma A1000,100 = 1000 x 9 x 998 x 997 xx 903 x 902 x 901 ou )!1001000(

Para generalizar, se desejarmos dispor p elementos em fila escolhidos dentre de m elementos, com p ≤ m, podemos realizar esse processo de )!pm( !mA p,m −

= maneiras distintas.

Exercícios resolvidos

1) Quantos números de três dígitos distintos escolhidos entre 1, 2, 3, 4, 5, 6 e 7, podemos formar?

Resolução: Em outras palavras queremos formar uma fila de três algarismos escolhidos de um grupo de sete algarismos.

Podemos então formar A7,3 filas distintas ou efetuando os cálculos obtemos:

=− =números distintos.

Verifique que o resultado obtido acima também pode ser encontrado utilizando-se o teorema fundamental da contagem.

2) Quantas filas com quatro pessoas podemos formar a partir de um grupo de seis pessoas?

Resolução: Podemos formar A6,4 filas. Deixaremos os cálculos para você resolver.

3) Um grupo de pessoas é formado por cinco homens e três mulheres. Deseja-se formar filas com 5 dessas pessoas de modo que as três mulheres ocupem sempre as três primeiras posições. Assim, de todas as filas possíveis, quantas obedecem essa restrição?

Resolução: Para iniciar vamos dispor as três mulheres nas três primeiras posições da fila e em seguida dispomos dois dos cinco homens nas duas últimas posições.

Na primeira ação podemos dispor as três mulheres de 3,3A maneiras. Na segunda ação devemos dispor dois homens escolhidos dentre cinco, nas duas últimas posições, temos 2,5Amaneiras. Finalmente devemos multiplicar os resultados parciais para obter:

=⋅=−⋅− =⋅A filas possíveis obedecendo a restrição dada.

Prof. Gerson Henrique 28

Para você resolver

53) Roberta quer presentear Júlia e Natália. Resolveu, após investigar os gostos pessoas de suas duas amigas, que o presente de cada uma seria DVD,s de música. Na loja especializada há de 10 opções para adquirir os dois presentes. Sabendo disso, de quantos modos diferentes Roberta pode presentear Júlia e Natália?

54) Junior é uma criança que possui oito brinquedos diferentes. Deseja brincar com cinco deles a cada dia, e com um deles a cada momento, isto é, ele não deseja brincar com dois ou mais ao mesmo tempo. Considerando essas informações responda: a) De quantos modos diferentes Junior pode brincar com seus brinquedos, de acordo com as condições impostas acima? b) Se Junior brinca de Segunda a sexta feira e brincou pela primeira vez numa quarta feira, em que dia da semana ele brincara pela antepenúltima vez sem que a seqüência de brinquedos se repita? c) Quantos anos, aproximadamente, ele brincará com seqüências de brinquedos diferentes?

5) De quantas formas pode-se formar uma seqüência com 9 elementos distintos tomados a partir de 12?

57) Resolva a equação 60Ap,5=. 58) Quantos são os arranjos de 8 elementos tomados de 3 a 3?

59) Calcule o valor de n na equação 20A2,n=.

60) Numa maratona em que participam x atletas 80% terminam completam a prova. Se podemos formar o pódio com os três primeiros colocados de 336 maneiras distintas, qual o valor de x?

61) (FJP) Pode-se permutar m objetos de 24 maneiras diferentes. Suponha que se pretenda arranjar esses m objetos dois a dois. Nesse caso, de quantas maneiras diferentes esses m objetos poderão ser arranjados? a) 10 b) 12 c) 14 d) 16

5 – Combinações

5.1 – Combinações Simples

Combinação simples é uma ferramenta combinatória utilizada quando desejamos contar as possibilidades de formação de um subgrupo de elementos a partir de um grupo dado. Em outras palavras se possuirmos um Conjunto de elementos, desejamos contar as possibilidades de formação de um subconjunto formado a partir do conjunto dado. É crucial nessa altura notar que quando formamos um subconjunto a partir de um conjunto dado, não estamos formando filas. Dessa maneira, quando se ver diante de um problema desse tipo, não devemos utilizar qualquer ferramenta que forme ordem entre os elementos em questão. Se por ventura forem formadas filas e não grupos (conjuntos) haverá uma contagem excessiva. Por exemplo, formar um grupo de duas pessoas utilizando Pedro, João e Ana é diferente de formar filas com duas dessas pessoas. Com as essas três pessoas podemos formar 6 filas diferentes com duas delas, observe:

Prof. Gerson Henrique 29

De forma diferente, para formar um grupo devemos simplesmente agrupar duas pessoas. Desse modo a ordem entre os elementos é irrelevante. Estas duas filas distintas (JOÃOPEDRO\) e (PEDROJOÃO\) formam o mesmo grupo. Dessa maneira se possuímos 3 pessoas e desejamos formar grupos de 2 pessoas teremos apenas 3 grupos possíveis, já que os pares (ANAPEDRO\e PEDROANA\); e os pares (ANAJOÃO\ e JOÃOANA\) também formam um único grupo. Assim ao realizar a contagem dos grupos ( 3 ) contamos primeiro as filas possíveis ( 6 ) que é uma resposta incorreta e em seguida dividimos o resultado por 2, já que contamos cada grupo duas vezes de forma equivocada, por isso corrigimos esse erro para se chegar a resposta correta (3).

Imagine agora que desejamos a partir de um grupo de 4 pessoas {P1, P2, P3, P4}, escolher 3 para formamos uma comissão.

Comissão sem qualquer hierarquia é sinônimo de grupo. Desse modo, como no exemplo anterior, vamos primeiro formar as filas possíveis e em seguida corrigir o resultado para obtermos a resposta correta, observe:

Pelo princípio multiplicativo temos 4x3x2 = 24 filas distintas, o que se verifica acima. No entanto não estamos interessados nas filas e sim nos grupos de três pessoas. Cada grupo tal como { 321;;P} apareceram nas filas

321P\P\P;231P\P\P; 312P\P\P; 132P\P\P; 213P\P\P; 123P\P\P.

desse modo cada grupo foi contado indevidamente seis vezes. Assim para acharmos a resposta correta devemos dividir a quantidade de filas (24) por 6, para obter 4 grupos.

Vamos, em seguida, considerar um outro exemplo:

A partir de um grupo de sete pessoas {Adriana, Bruno, Carol, David, Eduardo, Flávio, Gustavo} desejamos formar um subgrupo com quatro delas. De quantas formas podemos formar esse subgrupo?

Resolução: Primeiro note que subgrupo de pessoas não é sinônimo de fila com pessoas. Numa fila a ordem é relevante, num subgrupo irrelevante. No entanto para se obter a resposta vamos supor, de inicio, que estamos formando uma fila com as 7 pessoas. Uma vez formada a fila, selecionaremos os quatro primeiros indivíduos dessa fila para ter o grupo de quatro pessoas que queremos selecionar. Obteremos 7! filas distintas. Observe a ilustração:

Fila ⇒ AdrianaBruno Carol David Eduardo Flávio Gustavo,

Prof. Gerson Henrique 30

A seqüência formada acima é uma das filas possíveis. Assim como vamos sempre selecionar os quatro primeiros de cada fila, teríamos, nesse exemplo, formado o grupo {Adriana, Bruno, Carol, David}. Mas uma outra fila diferente, tal como:

Adriana Carol Bruno David Eduardo Flávio Gustavo

formaria nas quatro primeiras posições o mesmo grupo {Adriana, Bruno, Carol, David}. Repare que da primeira para a segunda fila Bruno e Carol trocaram de posição, o que não mudou a formação do grupo. Desse modo podemos notar que toda vez que tomarmos uma fila em que Adriana, Carol, Bruno e David estiverem nas quatro primeiras posições formaremos um único grupo. Desse modo não é verdadeiro que a quantidade de conjuntos das quatro primeiras pessoas de uma fila de sete é igual a quantidade de filas formada por sete pessoas. E mais, a quantidade de filas é maior que a quantidade de conjuntos. Assim ao obtermos 7! achamos um resultado incorreto. Pois a contagem foi excessiva. Mas nem tudo está perdido. 7! não é nossa resposta, porém ela pode ser corrigida para se chegar a resposta correta. Nosso erro inicial foi formar uma fila ao invés de um conjunto, assim, nesse momento devemos “desmantelar” a fila. Isto é, contamos excessivamente o conjunto {Adriana, Carol, Bruno, David} toda vez que formamos uma fila com essas pessoas nas quatro primeiras posições e as demais pessoas nas outras posições. O número de maneiras de dispor quatro pessoas em fila é 4!, e as demais (3 pessoas) é 3!. Assim para desmantelar a fila devemos dividir 7! por 4!⋅⋅⋅⋅3!. Desse modo a resposta será

.Observe:

AdrianaBruno Carol David Eduardo Flávio Gustavo

Esse resultado !3!4

⋅ será simbolizado por 47C ou 7,4C, ou ainda

7 lê-se: “combinação de 7 elementos tomados

4 a 4”. Assim fica !3!4

7 ⋅ =C, fazendo as contas obtemos

=⋅ =Cgrupos distintos.

Esse processo no qual lançamos mão nos exemplos acima é muito usado em problemas de contagem. Primeiro contamos excessivamente de forma intencional para em seguida dividimos a resposta para se chegar a resposta correta.

Para generalizar a idéia de formação de grupos a partir de outro grupo dado, vamos observar os resultados do exemplo anterior.

(Parte 4 de 7)

Comentários