7. contagem,permutação, combinações

Prévia do material em texto

Princípio Fundamental da Contagem
23/11/2013 09:26:48 Bryan Mariano Martinez Alves 1
Princípios da contagem
23/11/2013 09:26:52 Bryan Mariano Martinez Alves 2
Pode-se usar esse princípio para obter o número de formas
em que dois mais eventos podem ocorrer em sequência.
O Princípio Fundamental da Contagem
Se um evento pode ocorrer de 𝑚 maneiras e um segundo
evento de n maneiras, o número de maneiras em que os
dois eventos podem ocorrer em sequência é 𝑚 ∙ 𝑛. Essa
regra pode ser estendida para um número qualquer de
eventos que ocorram em sequência.
Princípios da contagem
23/11/2013 09:26:52 Bryan Mariano Martinez Alves 3
EXEMPLO
Você está comprando um novo carro. Usando as
informações a seguir (fabricantes, tamanho e cores) diga
de quantas maneiras diferentes podem-se selecionar um
fabricante, um tamanho e uma cor. E faça um digrama de
arvore
Fabricante: Ford, GM, Chrysler
Tamanho do carro: pequeno, médio
Cores: branco (B), vermelho (V), preto (P),
verde (Vd)
Princípios da contagem
23/11/2013 09:26:52 Bryan Mariano Martinez Alves 4
SOLUÇÃO
Fabricante: Ford, GM, Chrysler
Tamanho do carro: pequeno, médio
Cores: branco (B), vermelho (V), preto (P),
verde (Vd)
Há três opções de fabricantes, dois de tamanho e quatro de
cor. Assim, o número de maneiras para selecionar um
fabricante, um tamanho de carro e uma cor é
3 ∙ 2 ∙ 4 = 24maneiras.
Um diagrama de árvore pode ajudá-lo a ver por que
existem 24 opções.
Princípios da contagem
23/11/2013 09:26:52 Bryan Mariano Martinez Alves 5
SOLUÇÃO
Fabricante: Ford, GM, Chrysler
Tamanho do carro: pequeno, médio
Cores: branco (B), vermelho (V), preto (P),
verde (Vd)
Diagrama de árvore para selecionar carros
Exemplo
O código de acesso do sistema de segurança de um carro
consiste em quatro dígitos, cada um entre 0 e 9. Quantos
códigos de acesso são possíveis se
1.cada dígito pode ser usado somente uma vez e não
repetido?
2.cada dígito pode ser repetido?
Princípios da contagem
23/11/2013 09:26:52 Bryan Mariano Martinez Alves 6
SOLUÇÃO
1.cada dígito pode ser usado somente uma vez e não
repetido?
Uma vez que cada dígito pode ser usado somente uma vez,
existem dez opções para o primeiro dígito, nove para o
segundo, oito para o terceiro e sete para o quarto. Usando o
Princípio Fundamental da Contagem, você pode con¬cluir
que existem
10 ∙ 9 ∙ 8 ∙ 7 = 5.040 códigos de acesso possíveis.
Princípios da contagem
23/11/2013 09:26:52 Bryan Mariano Martinez Alves 7
SOLUÇÃO
2.cada dígito pode ser repetido?
Uma vez que cada dígito pode ser repetido, existem dez
opções para cada um dos quatro dígitos. Assim, existem
10 ∙ 10 ∙ 10 ∙ 10 = 104 = 10.000 códigos de acesso
possíveis.
Princípios da contagem
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 8
É a determinação do número de maneiras em que 𝑛 objetos
podem ser arranjados em ordem ou uma permutação
Definição
Uma permutação é um arranjo ordenado de objetos. O
número de permutações diferentes de 𝑛 objetos diferentes
é 𝑛!.
A expressão n! é lida como n fatorial e definida da seguinte
maneira:
𝑛 = 𝑛 ∙ (𝑛 − 1)!
Permutações
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 9
Exemplo
0! = 1
1! = 1
2! = 2 ∙ 1 = 2
3! = 3 ∙ 2 ∙ 1 = 6
4! = 4 ∙ 3 ∙ 2 ∙ 1 = 24
5! = 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 120
A fila inicial para um time de futebol tem 11 jogadores. De
quantas maneiras diferentes pode-se definir a ordem dos
jogadores?
Permutações
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 10
Exemplo
A fila inicial para um time de futebol tem 11 jogadores. De
quantas maneiras diferentes pode-se definir a ordem dos
jogadores?
SOLUÇÃO
Número de permutações é 11!
11! = 11 ∙ 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1
= 39.916.800
Assim, há 39.916.800 maneiras diferentes de ordenar os
jogadores.
Permutações
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 11
Suponha que você queira escolher alguns objetos em um
grupo e colocá-los em ordem. Essa ordenação é chamada
permutação de 𝒏 objetos tomando 𝒓 a cada vez.
Permutação de 𝒏 objetos tomando 𝒓 a cada vez
𝒏𝑷𝒓 =𝒏 𝑷𝒓 =
𝒏!
𝒏 − 𝒓 !
𝒐𝒏𝒅𝒆 𝒓 ≤ 𝒏
Exemplo
Quarenta e três carros de corrida começaram o Cuiabá 500
de 2013. De quantas maneiras os carros podem terminar
em primeiro lugar, em segundo e em terceiro?
Permutações
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 12
Exemplo
Quarenta e três carros de corrida começaram o Cuiabá 500
de 2013. De quantas maneiras os carros podem terminar
em primeiro lugar, em segundo e em terceiro?
SOLUÇÃO
Uma vez que há 43 carros e a ordem é importante, o
número de maneiras em que os carros podem terminar em
primeiro, segundo e terceiro é
𝒏𝑷𝒓 =𝒏 𝑷𝒓 =
𝒏!
𝒏 − 𝒓 !
𝒐𝒏𝒅𝒆 𝒓 ≤ 𝒏
Permutações
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 13
SOLUÇÃO
Uma vez que há 43 carros e a ordem é importante, o
número de maneiras em que os carros podem terminar em
primeiro, segundo e terceiro é
𝟒𝟑𝑷𝟑 =𝟒𝟑 𝑷𝟑 =
𝟒𝟑!
𝟒𝟑 − 𝟑 !
𝟒𝟑𝑷𝟑 =
𝟒𝟑!
𝟒𝟎!
𝟒𝟑𝑷𝟑 = 𝟒𝟑 ∙ 𝟒𝟐 ∙ 𝟒𝟏
𝟒𝟑𝑷𝟑 = 74.046
Permutações
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 14
O número de permutações distinguíveis de 𝑛 objetos,
sendo 𝑛1 de um tipo, 𝑛2 de outro tipo, e assim por diante, é
𝑛!
𝑛1! ∙ 𝑛2! ∙ 𝑛3!⋯𝑛𝑘!
, 𝑜𝑛𝑑𝑒 𝑛1 + 𝑛2 + 𝑛3 +⋯+ 𝑛𝑘 = 𝑛
Exemplo
Um empreiteiro planeja realizar uma obra. A obra consiste
em seis casas de um pavimento, quatro casas com dois
pavimentos e duas casas em dois níveis. De quantas
maneiras distinguíveis as casas podem ser arranjadas?
Permutações distinguíveis
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 15
SOLUÇÃO
Há doze casas na obra, seis das quais de um tipo (um
pavimento), quatro de outro tipo (dois pavimentos) e duas de
um terceiro tipo (em dois níveis). Assim, há
12!
6! ∙ 4! ∙ 2!
12 ∙ 11 ∙ 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6!
6! ∙ 4! ∙ 2!
12∙11∙10∙9∙8∙7
4!∙2!
= 13.860
13.860maneiras distinguíveis de arranjar as casas na obra.
Permutações distinguíveis
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 16
O número de maneiras de escolher 𝑟 objetos dentre n
objetos, não importando a ordem, é chamado de número de
combinações de n objetos tomando r a cada vez.
Combinações de n objetos tomando r a cada vez.
É uma seleção de 𝑟 objetos de um grupo de 𝑛 objetos, sem
que tenha importância a ordem denotada por 𝑛𝐶𝑟 . O
número de combinações de objetos selecionados em um
grupo de n objetos é
𝑛𝐶𝑟 =
𝑛!
𝑛 − 𝑟 ! 𝑟!
Combinações 
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 17
Exemplo
Um departamento de transporte estadual planeja desenvolver
uma nova seção de uma estrada interestadual e recebe r::
postas para o projeto. O Estado planeja contratar quatro das
companhias que fizeram ofertas. Quantas combinações
diferentes das quatros companhias podem ser selecionadas a
partir das 16 que fizeram propostas?
SOLUÇÃO
Uma vez que a ordem não é importante, 𝑛𝐶𝑟 =
𝑛!
𝑛−𝑟 !𝑟!
Combinações 
23/11/2013 09:26:53 Bryan Mariano Martinez Alves 18
SOLUÇÃO
16𝐶4 =
16!
16 − 4 ! 4!
=
16!
12! 4!
=
16 ∙ 15 ∙ 14 ∙ 13 ∙ 12!
12! 4!
=
16 ∙ 15 ∙ 14 ∙ 13
4!
=1.820
Combinações 
23/11/2013 09:26:48 Bryan Mariano Martinez Alves 19