01.análise.combinatória.ok

2º ANO – ISAM 1PROFº.: ULISSES MARÇAL DE CARVALHO

ANÁLISE COMBINATÓRIA

Por Ulisses Marçal de CarvalhoI - INTRODUÇÃO:

A análise Combinatória é a área da Matemática que trata, basicamente, de dois tipos de problemas:

i) PROBLEMAS DE CONTAGEMii) PROBLEMAS DE EXISTÊNCIA

II - PRINCÍPIOS FUNDAMENTAIS DA CONTAGEM:

Temos dois princípios a considerar:

i) PRINCÍPIO ADITIVOii) PRINCÍPIO MULTIPLICATIVO

1.1 - PRINCÍPIO ADITIVO:

- Se A e B são dois conjuntos disjuntos ( ) com, respectivamente, p e q

elementos, então:

EXEMPLOS:

Ex1: Suponha que tenham entrado em cartaz 3 filmes e 2 peças de teatro e que Fernando tenha dinheiro para assistir a apenas 1 evento. Quantos são os programas que Fernando pode fazer?

Comentários: Tomamos como conjunto A = {F1; F2; F3} e B = {P1; P2}.Se ele tem direito de assistir apenas 1 evento, temos para o primeiro conjunto 3 possibilidades e para o segundo, 2 possibilidades. Portanto, ao todo serão 3 + 2 = 5 possibilidades de assistir a um programa diferente.

Ex2.: Numa confeitaria há 5 sabores de picolés e 3 sabores de salgados. Suponha que Maria só tenha permissão para tomar um picolé ou comer um salgado. Quantos são os possíveis pedidos que Maria pode fazer?

Comentários: Podemos identificar os conjuntos da seguinte maneira:A = {P1, P2, P3, P4, P5}B = {S1, S2, S3}Ou Maria escolhe um sabor de picolé dentre os 5 ou 1 tipo de salgado dentre os 3. Portanto Maria pode fazer: A B = 5 + 3 = 8 pedidos diferentes.

1.2 - PRINCÍPIO MULTIPLICATIVO:

- Se um evento A pode ocorrer de m maneiras diferentes e, se para cada uma dessas m maneiras possíveis de A ocorrer, um outro evento B pode ocorrer de n

VESTIBULAR 2006PSS/PRISE


maneiras diferentes, então o número de maneiras de ocorrer o evento A seguido do evento B é: m . n.

EXEMPLOS:

Ex3.: Suponha que, do ex1, Fernando tenha dinheiro para assistir a um filme e a uma peça de teatro, quantos são os programas que ele pode fazer no sábado?COMENTÁRIOS: Podemos tomar como vento A a escolha do filme (que são 3) e como evento B a escolha da peça de teatro (que são 2). Portanto Fernando pode escolher um filme e uma peça, isto é: 3. 2 = 6.

Ex4.: Suponha que Lúcia vá a confeitaria com Maria e possa tomar um picolé e comer um salgado. Quantos pedidos diferentes Lúcia pode fazer?COMENTÁRIOS: Podemos tomar como evento A à escolha do picolé (que são 5) e como evento B a escolha do salgado (que são 3). Portanto, Lúcia pode fazer: 5. 3 = 15 pedidos diferentes.

1.3 - APLICAÇÕES DOS PRINCÍPIOS ADITIVO E MULTIPLICATIVO:

Vejamos alguns exemplos para ilustrar as aplicações de tais princípios:

Exemplo 1: Um marceneiro tem 20 modelos de cadeiras e 5 modelos de mesa. De quantas maneiras podemos formar um conjunto de 1 mesa com 4 cadeiras iguais?

Exemplo 2: O professor Clenilson mostrou-me 5 livros diferentes de matemática e 7 livros diferentes de física e permitiu-me escolher um de cada. De quantas maneiras esta escolha pode ser feita?Comentários:

Exemplo 3: De quantas maneiras podemos dar 2 prêmios a uma classe com 40 alunos, de modo que os prêmios não sejam dados a um mesmo aluno (a):Comentários: O 1º prêmio pode ser dado a qualquer um dos 40 alunos. O 2º prêmio poderá ser dado a qualquer um dos 39 alunos restantes. Portanto:



Exemplo 4: De quantas maneiras podemos dar 2 prêmios a uma classe com 40 alunos, se é permitido que ambos sejam dados a um mesmo aluno?Comentários: O primeiro prêmio pode ser dado de 40 maneiras e o segundo pode ser dado também de 40 maneiras. Portanto:

Exemplo 5: Um amigo mostrou-me 5 livros de Matemática, 7 livros de Física e 10 livros de Química e pediu-me para escolher 2 livros com a condição de que eles não fossem da mesma matéria. De quantas maneiras eu posso escolhê-los?Comentários: Posso fazer a seguinte escolha:(a) Matemática e física: 5. 7 = 35 maneiras;(b) Matemática e química: 5. 10 = 50 maneiras;(c) Física e química: 7. 10 = 70 maneiras.Como as escolhas só podem ocorrer dentre uma das possibilidades (a), (b) ou (c), então: 35 + 50 + 70 = 155 maneiras de fazer estas escolhas.Exemplo 6:De quantas maneiras 2 pessoas podem estacionar seus carros numa garagem com 6 vagas?

Comentários:

Exemplo 7: Quantos são os anagramas de 2 letras diferentes que podemos formar com um alfabeto de 23 letras?

Exemplo 8: De quantas maneiras podemos escolher 1 consoante e 1 vogal de alfabeto formado por 18 consoantes e 5 vogais?



Exemplo 9: Quantos são os anagramas de 2 letras formados por uma vogal e uma consoante escolhidas dentre 18 consoantes e 5 vogais?

Exemplo 10: Há 12 moças e 10 rapazes, onde 5 deles (3moças e 2 rapazes) são irmãos e os restantes não possuem parentesco. Quantos são os casamentos possíveis?Comentários: a) Considerando as moças (3) que possuem irmãos (2), há: 3. 8 = 24 casamentos possíveis.b) Considerando as moças (9) que não possuem irmãos (10), há: 9. 10 = 90 casamento possíveis.Portanto, há 24 + 90 = 114 casamentos possíveis.

Exemplo 11: Com os algarismos 2, 3, 4, 5, 6 e 8, quantos números ímpares de:a) 4 algarismos podemos formar?b) 4 algarismos distintos podemos formar?

Comentários: Um número é ímpar quando termina em 1, 3, 5, 7 e 9. Assim:

Exemplo 12: Em uma biblioteca existem 7 portas. Calcule o número de modos de essa biblioteca estar aberta (o que acontece se pelo menos uma porta estiver aberta).

Comentários: Logo, 128 são o total de possibilidades, estando todas as portas abertas ou 1 aberta e as demais fechadas ou 2 abertas e as demais fechadas ou etc.... Ou todas fechadas, ou seja: 128 – 1 = 127 possibilidades de estar aberta.

Exemplo 13: Com as letras do alfabeto latino (26) e os algarismos do sistema decimal (10), calcule o número de placas com (imaginando que pode haver placas com 4 algarismos iguais a zero):a) 2 letras seguidas de 4 algarismos;b) 3 letras seguidas de 4 algarismos.Comentários:



Exemplo 14: Calcule o número de:a) Divisores naturais de 600;b) Divisores inteiros de 600.

Comentários: 600 = 23. 3. 52 (Todo divisor natural de 600 é da forma 2m. 3n. 5p), com m assumindo os valores 0, 1, 2 ou 3; n assumindo 0 ou 1 e p assumindo 0, 1 ou 2.2m. 3n. 5p (m + 1). (n + 1). (p + 1)a) 600 = 23. 3. 52 = (3 + 1). (1 + 1). (2 + 1) = 4.2.3 = 24 divisores naturais de 600.b) Inteiros diferentes de zero 24. 2 = 48 divisores inteiros de 600.

Exemplo 15: Um restaurante oferece no cardápio 2 saladas distintas, 4 tipos de carne, 5 variedades de bebidas e 3 sobremesas diferentes. Uma pessoa deseja comer uma salada, uma carne, uma bebida e uma sobremesa. De quantas maneiras ela pode fazer o pedido.

Exemplo 16: Os números de telefones de uma cidade têm 8 algarismos. Determine a quantidade máxima de telefone a serem instalados, sabendo que os números não devem começar com zero.

FATORIAL:Chama-se fatorial de um inteiro não negativo n ( ), o inteiro que se indica por

, e tal que:

Exemplos:a) 0! = 1 b) 1! = 1 c) 2! = 2.1 = 2d) 3! = 3.2! = 3.2.1! = 3.2.1 = 6 e) 4! = 4.3! f) 5! = 5.4! g) 6! = 6.5! h) 7! = 7.6!



Generalizando, temos: n! = n(n-1). n(n-2). ... .3.2.1 n! = n(n-1)!

Exemplo 2: Calcular

Exemplo 3: Resolva a equação (x+3)!+(x+2)! = 8(x+1)!

Exemplo 4: Simplifique a expressão

Exemplo 5: Resolva a equação (n-4)! = 120



Obs.: Os problemas de A.C. podem ser classificados em três grandes categorias, segundo a forma como se organizam as categorias:

- ARRANJOA. C. = - PERMUTAÇÃO - COMBINAÇÃO

2. ARRANJO E COMBINAÇÃO SIMPLES:

Vamos estudar dois tipos de agrupamentos que podem ser formados dispondo-se se certo número de elementos: Os arranjos simples e as combinações simples (a palavra “simples” significa que em cada agrupamento formado não haverá repetições de elementos). Assim: - Consideremos 4 moças: Maria (M), Cecília (C), Andréia (A) e Beatriz (B).

(i) Escolhendo 3 das 4 moças e formando comissões, temos:

(ii) Escolhendo 3 das 4 moças e colocando-as em fila, temos:

2.1 - CRITÉRIOS PARA DIFERENCIAR ARRANJO DE COMBINAÇÃO:

Quando tentamos resolver um problema de A. C., deparamos com a seguinte questão: “Os agrupamentos mencionados nos problemas são arranjos ou combinação?” Para eliminar essa dúvida, vamos agir da seguinte maneira: -



Construímos um dos agrupamentos sugeridos pelo problema e, a seguir, mudamos a ordem de apresentação dos elementos desse agrupamento.

I - Se com essa mudança na ordem dos elementos obtivermos um agrupamento DIFERENTE do original, então esse agrupamento é um “ARRANJO”

II - Se com essa mudança na ordem obtivermos um agrupamento IGUAL ao original, então esse agrupamento é uma “COMBINAÇÃO”.

2.2 - ARRANJO SIMPLES:

Arranjo simples de n elementos de um conjunto E tomados p a p, é todo agrupamento formado por p elementos distintos escolhidos entre os n elementos dados.Indica-se o número desses arranjos simples de n elementos tomados p a p, por:

2.2.1 - CÁLCULO DO NÚMERO DE ARRANJO SIMPLES DE n ELEMENTOS TOMADOS p A p:

Sejam I = {a1, a2, a3,..., an) um conjunto formados por n elementos e seja p um número natural não-nulo. O número de arranjo simples dos n elementos de I tomados p a p, isto é, An,p, pode ser calculado pelo PFC:

Exemplo 01: O quadrangular final de um torneio mundial de basquete é disputado por quatro seleções: Brasil (B), Cuba (C), Rússia (R) e EUA (E). De quantas maneiras distintas podemos ter os três primeiros colocados? Comentários: Um possível resultado seria (B, R, C). Se trocarmos a ordem desses elementos, por exemplo, (C, B, R), obteríamos um resultado diferente: (B, R, C)≠(C, B, R). Dessa forma, cada resultado do torneio é um arranjo das quatro equipes tomadas três a três.



Exemplo 02: A senha de um cartão telefônico é formada por duas letras distintas seguida por uma seqüência de três algarismos distintos. Quantas senhas poderiam ser confeccionadas?Comentários: Como importa a ordem em que são escolhidas as letras, então: Pelo PFC, o número de senhas que podem ser confeccionadas é:

2.2.2 – ARRANJO COM REPETIÇÃO:

Seja E um conjunto com n elementos distintos e considere p elementos escolhidos neste conjunto em uma ordem determinada. Cada uma de tais escolhas é denominada um arranjo com repetição de n elementos tomados p a p. Acontece que existem n possibilidades para a colocação de cada elemento, logo, o número total de arranjos com repetição de n elementos escolhidos p a p é dado por:

Todos os elementos podem aparecer repetidos em um grupo de p elementos.

Exemplos:

Ex1.: Quantos números de 4 algarismos podemos formar com os algarismos: 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9Comentários: Ar (10,4) = 104 = 10.000 algarismos

Ex2.: Quantas palavras de 3 letras podemos formar com as 26 letras do nosso alfabeto?Comentários: Ar (26,3) = 263 = 17.576 palavras.

Ex3.: Quantas placas são possíveis em nosso sistema de trânsito, se em todas devem aparecer 3 letras seguidas de 4 números?Comentários: Ar (26,3) x Ar (10,4) = 17576 x 10000 = 175.760.000 placas.



2.2.3 – ARRANJO CONDICIONADO:

Todos os elementos aparecem em cada grupo de p elementos, mas existe uma condição que deve ser satisfeita acerca de alguns elementos. O arranjo condicional é dado por:

Ex1.: Quantos arranjos dos elementos A, B, C, D, E, F e G tomados 4 a 4, começam com duas letras dentre A, B e C?Comentários: n = 7; p = 4; n1= 3; p1= 2. Ac (7,4) = A (3,2). A (7 - 3, 4 - 2) = 72

2.3 - PERMUTAÇÕES SIMPLES:

Permutação de n elementos de um conjunto E tomados n a n, é todo agrupamento formado por n elementos distintos escolhidos entre os n elementos dados.Indica-se o número dessas permutações de n elementos tomados n a n, por: Pn é dado por:

Obs.: Notemos que a permutação é um caso particular de arranjo, pois, dado um conjunto com n elementos distintos, selecionamos exatamente n elementos para formar a seqüência ordenada.

Exemplo 01: Quantos são os anagramas da palavra AMOR?Comentários: Um anagrama da palavra AMOR é qualquer permutação das letras A, M, O, R de modo que se forme uma palavra com ou sem sentido.P4 = 4! P4 = 4.3.2.1 = 24

Exemplo 02: De quantas maneiras cinco pessoas, A, B, C, D e E, podem ser disposta em fila indiana.Comentários: Cada maneira de compor a fila é uma permutação das cinco pessoas, pois, qualquer fila obtida é uma seqüência ordenada na qual aparecem sempre as cinco pessoas.Assim, o resultado procurado é: P5 = 5! = 120.

Exemplo 03.: De quantas maneiras diferentes 5 pessoas podem formar uma fila indiana?Comentários: O número de maneiras é igual ao número de permutações simples desses cinco elementos, isto é:

P5 = 5! = 120.



Exemplo 04: De quantas maneiras distintas podemos dispor, numa mesma prateleira de uma estante, quatro livros de Matemática e três livros de Física, de modo que livros de mesma matéria permaneçam juntos?

Exemplo 04: Com a palavra MARTELO:

a) Quantos anagramas podemos formar? Resp.: P7 = 7! = 5040 anagramas diferentes.b) Quantos anagramas começam com M?

c) Quantos anagramas começam por M e terminam por O?

d) Quantos anagramas começam por vogal?

e) Quantos anagramas terminam por consoante?

f) Quantos anagramas começam por vogal e terminam por consoantes?

g) Quantos anagramas começam por vogal ou terminam por consoantes?

h) Quantos anagramas apresentam com as letras M,A e R juntas e nessa ordem?



i)Quantos anagramas apresentam com as letras M, A e R juntas?ii)Comentários: Nesse caso, um bloco composto pelas letras M, A e R podem ter:

2.3.1 – PERMUTAÇÃO COM ELEMENTOS REPETIDOS:

Vimos que o número de permutações de n elementos é dado por:

Podemos estender esse conceito para o caso do conjunto apresenta n elementos, em que um deles se repete n1 vezes, outro n2 vezes,..., outro nk vezes. O número de permutações entre os n elementos é dado por:

Exemplos:Ex1.: Qual é o número de anagramas que podemos formar com a palavra OSSOS?

Comentários: A palavra apresenta um total de cinco letras, com três S e dois O.

Assim:

Ex2.: Quantos são os anagramas das seguintes palavras:a) ANA

b) ADAGA

c) GARRAFA

d) ULISSES

e) MATEMÁTICA



2.3.2 – PERMUTAÇÃO CIRCULAR (PC):

É quando os elementos do agrupamento são dispostos em torno de um círculo. Se o agrupamento fundamental possui n elementos distintos, então o número de permutações circulares que podem ser feitas com esses n elementos é dado pela fórmula:

Exemplos:Ex1.: De quantos modos distintos podemos dispor 3 pessoas em torno de uma mesa circular?Comentários: A primeira vista, parece que basta escolher uma ordem para as 3 pessoas (A, B, C), o que pode ser feito de 3! = 6 maneiras distintas. Entretanto, é importante ressaltar que quando dispomos elementos em um círculo, as disposições que podem coincidir por rotação são consideradas equivalentes. Assim, das 3! = 6 posições supostamente possíveis, temos apenas 3 diferentes:

Portanto, o número de maneiras que as 3 pessoas podem ser disposta em torno de uma mesa circular é igual a: (PC)3 = (3 – 1)! = 2! = 2.

2.4 - COMBINAÇÕES SIMPLES:

Dado um conjunto E com n elementos distintos, chama-se combinação dos n elementos de E, tomados p a p, a qualquer subconjunto de E formados por p elementos.



2.4.1 – CÁLCULO DO NÚMERO DE COMBINAÇÕES:

Considere o seguinte problema: Uma classe é formada por 10 alunos. Deseja-se formar uma comissão de três alunos para representação discente na escola. De quantas maneiras podemos fazer tal escolha?Comentários: Calculemos, inicialmente, o número de triplas ordenadas de alunos: A10, 3 = 720 seqüências ordenadas.

Suponhamos que A, B e C estejam entre os 10 alunos da classe. Essas 720 possibilidades incluem, entre outras, os seguintes arranjos: (A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A) Veja que, nessa ordem, os seis arranjos acima passam a ser “equivalentes entre si”, correspondendo a uma única combinação {A, B, C}, pois determinam sempre a mesma comissão. Dessa forma, aos seis arranjos correspondem uma combinação; então, para os 720

arranjos, teremos x combinações:

Resolvendo a proporção acima, vem:

Isto é: x = 120 comissões.De modo geral, qualquer permutação de uma determinada seqüência ordenada dá origem a uma única combinação.Genericamente, o número de combinações de n elementos distintos, tomados p a p, que se indica por Cn,p, é dado por:

Assim, temos:

Exemplo 01: Uma pizzaria oferece 15 diferentes sabores de pizza a seus clientes.a) De quantas maneiras uma família pode escolher três desses sabores?b) Suponha, agora, que uma família sempre opta por mussarela. Como poderão ser escolhidos os outros sabores?Comentários:(a) Escolher as pizzas {P1, P2, P3} é o mesmo que escolher {P3, P1, P2}. Assim, cada possível escolha é uma combinação da 15 pizzas tomadas 3 a 3.



(b) Como um dos sabores já foi definido, os outros dois sabores são escolhidos entre os 14 restantes. Dessa forma, o número de possibilidades é dado por:

Exemplo 02: Uma classe tem 15 alunos, sendo 9 meninos e 6 meninas.a) Quantas comissões de dois meninos e duas meninas podem ser formadas?b) Quantas comissões de quatro pessoas têm pelo menos um menino?Comentários: (a) Como a ordem não importa, o número de maneiras de escolher os meninos é C9, 2 e o número de maneiras de escolher as meninas é C6, 2.Pelo PFC, temos: C9, 2 X C6, 2 = 36 x 15 = 540 Comissões.(b) O número total de comissões de quatro pessoas sem restrições é: C15, 4 e número de comissões onde não aparecem meninos é C6, 4.Dessa forma, a diferença: C15, 4 - C6, 4 = 1365 – 15 = 1350.Fornece o número de comissões onde há pelo menos um menino. Exemplo 03: Marcam-se cinco pontos sobre uma reta r. Sobre outra reta s, paralela a r, marcam-se mais quatro pontos. Quantos triângulos podem ser formados com vértices em três quaisquer desses pontos?Comentários:

1º caso:

2º caso:

Dessa forma, o número total de triângulos que podem ser construídos é: 40 + 30 = 70.

2.4.2 – COMBINAÇÕES COM REPETIÇÃO:

Considere n elementos distintos e ordenados. Escolha p elementos um após o outro e ordene estes elementos na mesma ordem que os elementos dados. O resultado é chamado uma combinação com repetição de n elementos tomados p a p, dado por:

Ex1.: Determinar o número de combinações com 4 elementos tomados com repetição de 7 livros.Comentários: Cr (7,4) = C(7+4-1,4) = C(10,4) = 210.



2.4.3 – PROPRIEDADES DAS COMBINAÇÕES:

O segundo número, indicado por p é conhecido como a TAXA que define a quantidade de elementos de cada escolha.

2.4.4 – TAXA COMPLEMENTAR:

C(n, p) = C(n, n-p)

Exemplo: C(12,10) = (12,2) = 66

2.4.5 – RELAÇÃO DO TRIÂNGULO DE PASCAL:

C(n, p) = C(n - 1, p) + C(n - 1, p - 1)

Exemplo: C(12,10) = C(11,10) + C(11, 9) = 11 + 55 = 66


Documents

01.análise.combinatória.ok