Grátis 111 pág.
- Denunciar
Pré-visualização | Página 7 de 9
a um mesmo time. Quantos times podem ser for- mados? [ No total de times ] = [ No de times com A e sem B I ] + [ No de times com B e sem A II ] + [ No de times sem A e sem B III ] I C(10,4) = 10!4!·6! = 210 Os times com A e sem B devem ter mais 4 pessoas das 10 restantes do grupo (10 porque A e B estão fora e 4 porque A é uma das 5 pessoas). II C(10,4) = 10!4!·6! = 210 Idem ao anterior. III C(10,5) = 10!5!·5! = 252 Os times que não contêm A e B devem ter 5 pessoas das 10 restantes do grupo. No total de times = 210 + 210 + 252 = 672 UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 77 Combinação Exemplo 32 Este problema também pode ser resolvido de outra forma: [ No total de times ] = No de times com5 pessoas I − [ No de times comA e com B II ] I C(12,5) = 12!5!·7! = 792 Total de times com 5 pessoas. II C(10,3) = 10!3!·7! = 120 Os times que contêm A e B devem ter mais 3 pessoas das 10 restantes do grupo. No total de times = 792− 120 = 672 UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 78 Expressões “pelo menos” e “no máximo” • Seja um conjunto S com 5 elementos. • O que significa escolher subconjuntos com – “pelo menos” 3 elementos de S, e – “no máximo” 2 elementos de S? • “Pelo menos” 3 elementos de S: – Significa escolher subconjuntos com 3, 4 ou 5 elementos. • “No máximo” 2 elementos de S: – Significa escolher subconjuntos com 0, 1 ou 2 elementos. UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 79 Combinação Exemplo 33 Suponha que o grupo de 12 pessoas seja formado por 5 homens e 7 mulheres. Quantos times de 5 pessoas podem ser formados com 3 homens e 2 mulheres? [ No total de times ] = [ No de times com 3 homens I ] × [ No de times com 2 mulheres II ] I C(5,3) = 5!2!·3! = 10 Total de times com 3 homens. II C(7,2) = 7!2!·5! = 21 Total de times com 2 mulheres. No total de times = 10× 21 = 210 Note que o princípio da multiplicação deve ser aplicado já que temos possibilidades diferentes para formação dos times. UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 80 Combinação Exemplo 34 Suponha o mesmo grupo anterior. Quantos times de 5 pessoas podem ser formados com pelo menos um homem? [ No total de times ] = No de times com5 pessoas I − [ No de times comnenhum homem II ] I C(12,5) = 12!5!·7! = 792 Total de times com 5 pessoas incluindo homens e mulheres. II C(7,5) = 7!5!·2! = 21 O total de times com nenhum homem é exatamente a quantidade de times formados ape- nas por mulheres. No total de times = 792− 21 = 771 UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 81 Combinação Exemplo 34 Este problema também pode ser resolvido de outra forma:( 5 1 ) · ( 7 4 ) + {Times com 1 homem e 4 mulheres}( 5 2 ) · ( 7 3 ) + {Times com 2 homens e 3 mulheres}( 5 3 ) · ( 7 2 ) + {Times com 3 homens e 2 mulheres}( 5 4 ) · ( 7 1 ) + {Times com 4 homens e 1 mulher}( 5 5 ) · ( 7 0 ) {Times com 5 homens e nenhuma mulher} UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 82 Combinação Exemplo 35 Suponha o mesmo grupo anterior. Quantos times de 5 pessoas podem ser formados com no máximo um homem? [ No total de times ] = [ No de times com nenhum homem I ] + [ No de times com um homem II ] I C(7,5) = 7!5!·2! = 21 O total de times com nenhum homem é exatamente a quantidade de times formados ape- nas por mulheres. II C(5,1) · C(7,4) = 5!1!·4! · 7!4!·3! = 5 · 35 = 175 O total de times com um homem e quatro mulheres. No total de times = 21 + 175 = 196 UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 83 Combinação Exemplo 36 Numa escola, há 10 professores de Matemática e 15 de Portu- guês. Pretende-se formar, com esses professores, uma comissão de sete mem- bros. Quantas comissões distintas podem ser formadas com, pelo menos, um professor de Matemática? [ No total de comissões ] = No de comissões com7 pessoas I − N o de comissões com nenhum professor de Matemática II I C(25,7) = 25!7!·18! = 2 043 500 Total de comissões com 7 pessoas incluindo professores de Matemática e Português. II C(15,7) = 15!7!·8! = 25 740 O total de comissões com nenhum professor de Matemática é exatamente a quantidade de comissões formadas apenas por professores de Português. No total de comissões = 2 043 500− 25 740 = 2 017 760 UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 84 Combinação Exemplo 36 Este problema também pode ser resolvido de outra forma:( 10 1 ) · ( 15 6 ) + {Comissões com 1 professor de Matemática e 6 professores de Português}( 10 2 ) · ( 15 5 ) + {Comissões com 2 professores de Matemática e 5 professores de Português}( 10 3 ) · ( 15 4 ) + {Comissões com 3 professores de Matemática e 4 professores de Português}( 10 4 ) · ( 15 3 ) + {Comissões com 4 professores de Matemática e 3 professores de Português}( 10 5 ) · ( 15 2 ) + {Comissões com 5 professores de Matemática e 2 professores de Português}( 10 6 ) · ( 15 1 ) + {Comissões com 6 professores de Matemática e 1 professor de Português}( 10 7 ) · ( 15 0 ) {Comissões com 7 professores de Matemática e nenhum professor de Português} UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 85 Combinação Exemplo 37 Suponha o mesmo grupo anterior. Quantas comissões distintas podem ser formadas com, pelo menos, dois professores de Matemática e, pelo menos, três professores de Português? Ü Por que o raciocínio abaixo está errado? N o de comissões com 2 professores de Ma- temática I × No de comissões com 3 professores de Por- tuguês II × No de comissões com 2 professores dentre os restantes de Ma- temática e/ou Portu- guês III I C(10,2) = 10! 2!·8! = 45 No de comissões com 2 professores de Matemática. II C(15,3) = 15! 3!·12! = 455 No de comissões com 3 professores de Português. III C(20,2) = 20! 2!·18! = 190 No de comissões com 2 professores dentre os restantes de Matemática e/ou Português. Note que ficam 20 professores dos 25 do grupo, já que 5 foram escolhidos. No total de comissões = 45 · 455 · 190 = 3 890 250 UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 86 Combinação Exemplo 37 (continuação) O raciocínio foi: I No de comissões com 2 professores de Matemática × II No de comissões com 3 professores de Português × III No de comissões com 2 professores dentre os restantes de Matemática e/ou Português Um cenário da proposição anterior pode ser representado pelos seguintes conjuntos: II C D E F G H I J d e f g h i j k l m n oa b c A B Professores de Matemática I Professores de Matemática e III Português Professores de Português Neste cenário, temos no conjunto I os elemen- tos A e B, no conjunto II os elementos a, b e c, e no conjunto III os elementos restantes. Note que podemos escolher os professores de Matemática C e D como os elementos do con- junto III. No entanto, existe outro cenário onde teremos no conjunto I os professores C e D e os pro- fessores A e B como os outros dois elementos do conjunto III. Se os elementos do conjunto II não mudaram então as comissões resultantes nos dois cenários acima são idênticas e, assim, estamos contando duas vezes a mesma comis- são. UFMG/ICEx/DCC MD · Ana´lise Combinato´ria 87 Combinação Exemplo 37 (continuação) Este problema pode ser resolvido da seguinte forma: II A B C D E F G H I J Professores de Matemática I a b c d e f g h i j k l m n o Professores de Português {Comissões com 4 professores de Matemática e 3 professores de Português}( 10 4 ) · ( 15 3 ) + {Comissões com 3 professores de Matemática e 4 professores de