Análise Combinatória

Prévia do material em texto

Análise Combinatória Versão: segundo semestre de 2001
Marcelo Eustáquio Soares de Lima Júnio 
(marcelo@bhvest.com) 1
Análise Análise 
CombinatóriaCombinatória
Capítulo ???Capítulo ???
MarceloMarcelo EustáquioEustáquio
lima@lima@dccdcc.ufmg..ufmg.brbr
1. Introdução:1. Introdução:
A Análise Combinatória visa desenvolver 
métodos que permitam contar o número 
de elementos de um conjunto, sendo estes 
elementos agrupamentos formadosagrupamentos formados sob 
certas condições.
Notação:
#A = Número de elementos de A
2. Exemplo:2. Exemplo:
Quantos são os resultados do lançamento de 
um dado e uma moeda ?
Lançamento da moeda:Lançamento da moeda: cara e coroa
Lançamento do dado:Lançamento do dado: 1, 2, 3, 4, 5, 6
Possibilidades de resultado:
(cara, 1); (coroa, 1); (cara, 2); (coroa, 2); 
(cara, 3); (coroa, 3); (cara, 4); (coroa, 4); 
(cara, 5); (coroa, 5); (cara, 6); (coroa, 6)
3. Princípio Fundamental 3. Princípio Fundamental 
de Contagem:de Contagem:
Lema: Lema: 
Consideremos os conjuntos AA e BB, onde #A = m#A = m
e #B = n#B = n. Então podemos formar m.nm.n pares 
ordenados (a,b) onde a a ÎÎÎÎ AA e b b ÎÎÎÎ BB. 
Observação: Observação: 
No exemplo anterior, era 66 as possibilidades do 
lançamento do dado e 22 as da moeda, logo são 
6.2 = 126.2 = 12 resultados diferentes do lançamento do 
dado e da moeda.
4. Exemplo:4. Exemplo:
Temos três cidades, A, B e C. O nº de estradas 
que ligam A a B é 5 e o nº de estradas que ligam 
B a C é 4. Partimos de A e, passando por B, de 
quantas maneiras podemos chegar até C ?
AA BB CC
#AB = 5
#BC = 4
#AC = 5.4 = 20 maneiras
5. Exemplo:5. Exemplo:
Temos 5 bolas, 7 petecas e 8 pipas para distribuir 
entre dois meninos. Todos os objetos devem ser 
distribuídos, mas não há necessidade de que a 
distribuição seja equânime. Quantas são as 
maneiras de se fazer essa divisão ?
1º1º 2º2º 3º3º
66 88 99xx xx ==
432 432 
maneirasmaneiras
Análise Combinatória Versão: segundo semestre de 2001
Marcelo Eustáquio Soares de Lima Júnio 
(marcelo@bhvest.com) 2
6. Exemplo 6. Exemplo (Questão 20)(Questão 20)::
Usando a primeira letra de cada um dos seguintes 
países: Brasil, Argentina, Uruguai e Paraguai, 
todas as possibilidades de criação de siglas 
diferentes são em número de:
A)A) 6
B)B) 12
C) C) 18
D) D) 24
E) E) 36
1º1º 2º2º 3º3º 4º4º
44 33 22 11xx xx xx == 24 siglas24 siglas
Nº de letras = 4 (B, A, P, U) para 
serem distribuídas em 4 posições.
7. Exemplo 7. Exemplo (Questão 21)(Questão 21)::
Um restaurante oferece no cardápio 2 saladas diferentes, 
4 tipos de pratos de carne, 5 variedades de bebidas e 3 
sobremesas diferentes. Uma pessoa deseja uma salada, 
um prato de carne, uma bebida e uma sobremesa. De 
quantas maneiras poderá fazer o seu pedido ?
1º1º
SaladaSalada
2º2º
CarneCarne
3º3º
BebidaBebida
4º4º
SobreSobre
22 44 55 33xx xx xx ==
120 120 
escolhasescolhas
8. Exemplo:8. Exemplo:
Uma prova consta de 20 testes do tipo 
verdadeiroverdadeiro e falsofalso. De quantas formas uma 
pessoa poderá responder aos 20 testes ?
1º1º 2º2º 20º20º
22 22 22xx xx xx ==
222020 (ou) (ou) 
1.048.576 1.048.576 
formasformas
......
......
......
......
Para cada teste, são duas 
possibilidades ( V ou F)
9. Exemplo:9. Exemplo:
Em um computador digital, um bitbit é um dos algarismos 
0 0 ou 11, e uma palavra palavra é uma sucessão de bitsbits. Qual o 
número de palavras distintas de 32 bits 32 bits ?
1º1º 2º2º 32º32º
22 22 22xx xx xx ==
223232 (ou) (ou) 
4.294.967.296 4.294.967.296 
formasformas
......
......
......
......
Para cada bit, temos duas 
possibilidades ( 0 ou 1)
10. Exemplo 10. Exemplo (Questão 8)(Questão 8)::
Numa cidades, os telefones têm 7 algarismos, 
sendo que os três primeiros constituem o prefixo 
da cidade. Os telefones terminados em 10 são 
reservados para as farmácias e os que têm os dois 
últimos algarismos iguais, para os médicos e 
hospitais. Qual a quantidade de telefones 
disponíveis na cidade ?
Solução Solução (Questão 8)(Questão 8)::
1º1º 2º2º 3º3º 4º4º
1010 1010 1010 1010xx xx xx
= 10.000 telefones= 10.000 telefones
5º5º 6º6º 7º7º
11 11 11xx xx xx
Observação: Os três primeiros dígitos Observação: Os três primeiros dígitos 
constituem o prefixo da cidade.constituem o prefixo da cidade.
Análise Combinatória Versão: segundo semestre de 2001
Marcelo Eustáquio Soares de Lima Júnio 
(marcelo@bhvest.com) 3
3º3º
1010 1010 11 11xx xx xx
= 100 telefones para farmácias= 100 telefones para farmácias
4º4º
11 11 11xx xx xx
3º3º
1010 1010 1010 11xx xx xx
= 1.000 telefones para médicos e hospitais= 1.000 telefones para médicos e hospitais
4º4º
1º1º
(x)(x)
2º2º
(Idem)(Idem)
11 11 11xx xx xx
1º1º
(1)(1)
2º2º
(0)(0)
Total de telefones disponíveis Total de telefones disponíveis 
= 10.000 = 10.000 –– 1.000 1.000 –– 100100
= 8.900= 8.900
Total de telefones disponíveis = Total de telefones disponíveis = 
Total de Telefones Total de Telefones –– Telefones Farmácias Telefones Farmácias ––
Telefones de Médicos e Hospitais Telefones de Médicos e Hospitais 
11. Exemplo:11. Exemplo:
Num campeonato de futebol, participam 22 times. 
Quantos resultados são possíveis para os três 
primeiros lugares ?
1º1º 2º2º 3º3º
2222 2121 2020xx xx ==
9.420 9.420 
resultadosresultados
12. Exemplo:12. Exemplo:
Utilizando os algarismos 1, 2, 3, 6, 7 e 8, determine:
B) B) Quantos nº de 3 algarismos distintos podemos formar ?
A) A) Quantos nº de 3 algarismos podemos formar ?
1º1º 2º2º 3º3º
66 66 66xx xx ==
216 216 
númerosnúmeros
1º1º 2º2º 3º3º
66 55 44xx xx ==
120 120 
númerosnúmeros
13. Exemplo 13. Exemplo (Questão 5)(Questão 5)::
Com os dígitos 1, 2, 3, 4, 5 e 6 são formados números 
de 4 dígitos distintos. Dentre eles, qual a 
quantidade que são divisíveis por 5 ? 
4º4º
1º1º
( 5 )( 5 )
55 44 33 11xx xx xx ==
120 120 
númerosnúmeros
3º3º
2º2º
excetoexceto
o ( 5 )o ( 5 )
14. Exemplo 14. Exemplo (Questão 14)(Questão 14)::
Quantos números de 4 algarismos distintos existem 
entre 2000 e 5000 ?
3º3º 4º4º
33 99 88 77xx xx xx ==
15121512
númerosnúmeros
2º2º
1º1º
(2, 3, 4)(2, 3, 4)
Nas posições 2, 3 e 4, a única restrição se dá 
com relação à não repetição do algarismo 
usado na primeira posição.
Análise Combinatória Versão: segundo semestre de 2001
Marcelo Eustáquio Soares de Lima Júnio 
(marcelo@bhvest.com) 4
15. Fatorial:15. Fatorial:
Seja nn um número natural, n n ³³³³ 22. Define-se o 
fatorial de n, que indicamos por n!n!, como o 
produto dos números naturais consecutivos 
nn, nn--11, nn--22, ..., 22 e 11 , isto é:
n! = n.(nn! = n.(n--1).(n1).(n--2).(n2).(n--3) ... 2.13) ... 2.1
Exemplo:Exemplo:
2! = 2.1 = 2
3! = 3.2.1 = 6
4! = 4.3.2.1 = 24
5! = 5.4.3.2.1 = 120
Fatorial:Fatorial:
Propriedade Fundamental:Propriedade Fundamental:
n! = n.(nn! = n.(n--1)! , 1)! , 
para n para n ÎÎÎÎ N, n N, n ³³³³ 33
Exemplo:Exemplo:
4! = 4.3.2.1 = 4.3! 
5! = 5.4.3.2.1 = 5.4!
Fatorial:Fatorial:
Importante:Importante:
Como extensão da definição Como extensão da definição 
de fatorial, demonstrade fatorial, demonstra--se se 
que:que:
0! = 1
1! = 1
Permutações:Permutações:
É o resultado da troca (ou permutaçãopermutação) das 
posições dos elementos de um determinado 
agrupamento.
Exemplo:Exemplo:
Algumas permutações das letras da palavra PATO:PATO:
TOPA
TAPO
APTO
Cada uma dessas permutações é chamada 
de AnagramaAnagrama.
Permutações:Permutações:
O número de Permutações que um 
agrupamento com nn elementos possui é
n!n!
PPnn = n! = n.(n= n! = n.(n--1).(n1).(n--2).(n2).(n--3) ... 2.13) ... 2.1
16. Exemplo:16. Exemplo:
Com relação à palavra TEORIA, determine:
A) A) Quantosanagramas existem ?
1º1º 2º2º 3º3º
66 55 44xx xx xx
4º4º 5º5º 6º6º
33 22 11xx xx
==
720 720 
anagramasanagramas
Análise Combinatória Versão: segundo semestre de 2001
Marcelo Eustáquio Soares de Lima Júnio 
(marcelo@bhvest.com) 5
B) B) Quantos anagramas começam por T ?
1º 1º 
letra Tletra T
2º2º 3º3º
11 55 44xx xx xx
4º4º 5º5º 6º6º
33 22 11xx xx
==
120 120 
anagramasanagramas
C) C) Quantos anagramas começam por T e terminam por A ?
1º 1º 
letra Tletra T
3º3º 4º4º
11 44 33xx xx xx
5º5º 6º6º
2º 2º 
letra Aletra A
22 11 11xx xx
==
24 24 
anagramasanagramas
D) D) Quantos anagramas começam por vogal ?
1º 1º 
E,O,I,AE,O,I,A 2º2º 3º3º
44 55 44xx xx xx
4º4º 5º5º 6º 6º 
33 22 11xx xx
==
480 480 
anagramasanagramas
E) E) Quantos anagramas têm as vogais juntas ?
1º 1º 2º2º 3º3º
33 22 11xx xx
==
O conjunto tem três elementos: as 
vogais vogais e as letras TT e RR
6 permutações das 6 permutações das 
consoantes e conjunto de consoantes e conjunto de 
vogaisvogais
1º 1º 2º2º 3º3º
44 33 22xx xx xx
24 permutações 24 permutações 
das vogaisdas vogais
4º4º
11
==
6 x 24 = 144 anagramas6 x 24 = 144 anagramas
17. Observação:17. Observação:
De todos os exemplos anteriores, todos eles têm 
uma particularidade: a permutação (troca) de dois 
ou mais elementos de posição altera o 
agrupamento formado.
ArranjoArranjo
18. Outro exemplo:18. Outro exemplo:
Considere todos os subconjuntos de P = {a,b,c,d,e,f}, 
com 4 elementos. 
Solução:Solução:
Escolha dos 4 elementos para a formação do 
subconjunto:
1º1º 2º2º 3º3º 4º4º
66 55 44 33xx xx xx ==
360 360 
escolhasescolhas
Análise Combinatória Versão: segundo semestre de 2001
Marcelo Eustáquio Soares de Lima Júnio 
(marcelo@bhvest.com) 6
Considerando o subconjunto {a, b, c, d}, notamos que 
se trocado a posição de seus elementos, temos que o 
agrupamento não ficou modificadonão ficou modificado, como 
aconteceria nos agrupamentos do tipo ArranjoArranjo.
São P4 = 4! = 24 permutações para cada 
escolha que não alteram o agrupamento 
formado.
Logo, o número de subconjuntos é dado por:
15
24
360
ºN ==
19. Observação:19. Observação:
No exemplo an ter io r , a permutação ( t roca) de do is 
ou mais e lementos de pos ição não a l te ra o 
ag rupamen to fo rmado .
CombinaçãoCombinação
20. Arranjo x Combinação:20. Arranjo x Combinação:
A ordem dos 
e lementos não é 
importante, não é 
re levante.
CombinaçãoCombinaçãoArranjoArranjo
A ordem dos 
e lementos é 
importante, é 
re levante.
Pr inc íp io Fundamenta l 
de Con tagem )!pn(!p
!n
C p,n -
=
21. Exemplo:21. Exemplo:
Quantos p rodu tos podemos ob te r se tomarmos 4 
fa tores d is t in tos entre os números 2, 3 , 5 , 7 , 
11 , 13, 17, 19 e 23 ?
Devemos encon t ra r o número de 
escolhas de 4 e lementos 4 e lementos d e u m 
total de 9 e lementos9 e lementos .
C 9 , 4 = 126 produtos126 produtos
!5!4
!9
C 4,9 ×
=
22. Exemplo 22. Exemplo (Questão 30)(Questão 30) ::
F o r m a m -se comissões de t rês p ro fessores esco lh idos 
en t re os se te de uma esco la . O número de comissões 
d is t in tas que podem, ass im ser fo rmado é :
A)A) 3 5
B) B) 4 5
C)C) 210
D)D) 343
E)E) 7!
Devemos encon t ra r o número de 
escolhas de 3 e lementos 3 e lementos d e u m 
total de 7 e lementos7 e lementos .
C 7 , 3 = 3 5 c o m i s s õ e s3 5 c o m i s s õ e s
Letra (A)Letra (A)
A)A) 3 5
!4!3
!7
C 3,7 ×
=
23. Exemplo 23. Exemplo (Questão 15)(Questão 15) ::
Em um grupo de 10 p ro fessores , 3 são de Matemát i ca . 
Qua l o número de comissões de 6 pro fessores , das 
qua is pe lo menos um é p ro fessor de Matemát ica ?
Nº de comissões = XX tt –– XX 00 onde
XX tt = número to ta l de comissões
XX 00 = número de comissões sem p ro fesso r de Ma temát i ca
X t = C10,6 = 210
X 0 = C 7,6 = 7
R e s pR e s p.:.: 210 – 7 = 203 comissões203 comissões
Análise Combinatória Versão: segundo semestre de 2001
Marcelo Eustáquio Soares de Lima Júnio 
(marcelo@bhvest.com) 7
ExemploExemplo (Questão 23)(Questão 23) ::
Um campeonato de fu tebo l é d ispu tado por 20 equ ipes , 
de aco rdo com o esquema segu in te : 
1) F o r m a m -se 4 g rupos de 5 equ ipes cada . Em cada 
grupo, as equ ipes jogam ent re s i . Obtêm- se ass im o 
campeão de cada g rupo .
2) Os 4 campeões jogam en t re s i , su rg indo da í o 
campeão .
O número to ta l de jogos d ispu tados é :
A) A) 2 0
B)B) 2 4
C)C) 4 0
D) D) 4 6
E) E) 190
F o r m a m -se 4 g rupos de 5 equ ipes cada . Em cada 
grupo, as equ ipes jogam ent re s i . Obtêm- se ass im o 
campeão de cada g rupo .
Os 4 campeões jogam en t re s i , su rg indo da í o campeão.
C 5,2 = 10 Þ NN ºº de jogos = 4 x 10 = 40de jogos = 4 x 10 = 40
C 4,2 = 6 Þ NNºº de jogos = 6de jogos = 6
Na pr imei ra fase da compet ição, 
acon teceram 40 jogos e , na segunda fase , 
6 jogos. Por tanto , o número to ta l de jogos 
d isputados é 40 + 6 = 46 .
( letra D)(letra D)
ExemploExemplo (Questão 16)(Questão 16) ::
Numa p rova de 12 ques tões , um a luno deve esco lhe r 10 
para reso lver . O número de esco lhas d i fe ren tes que 
e le pode fazer é :
A) A) 144
B)B) 120
C)C) 7 2
D) D) 6 6
E) E) 132
C 1 2 , 1 0 = 66 produtos66 produtos
!2!10
!12
C 1 0,1 2 ×
=
Exemplo Exemplo (Questão 25)(Questão 25) ::
Em uma reun ião soc ia l em que hav iam n pessoas , cada 
uma saudou as ou t ras com um aper to de mão. 
Sabendo- se que houve ao todo 66 aper tos de mão, 
podemos a f i rmar que :
A) A) n é n ú m e r o p r i m o
B)B) n é número ímpa r
C)C) n é d i v i so r de 100
D) D) n é d i v i so r de 125
E) E) n é múl t ip lo de 6
Solução Solução (Questão 25)(Questão 25) ::
C n, 2 = 66 Þ n = 12 pessoasn = 12 pessoas
)!2n(2
)!2n()1n(n
)!2n(!2
!n
C 2,n -×
-×-×=
-×
=
2
)1n(n -×=
66=
0132nn
2 =--Þ
12n =\
)convémN ã o(11n -=\