View
225
Download
0
Embed Size (px)
Citation preview
Princípios de Contagem
Sumário
• Princípio da Multiplicação
• Princípio da Adição
• Princípio da Inclusão e Exclusão
• Princípio das Casas de Pombo
Motivação
• Um problema de contagem envolve determinar o número de elementos em um conjunto finito ou o número de combinações possíveis em um dado contexto.
‣ dimensionar capacidades/limites (em problemas de alocação de recursos)
Princípio da Multiplicação
• Se existem n1 resultados possíveis para um evento e n2 resultados possíveis para um segundo evento, então existem n1 ⋅ n2 resultados possíveis para a seqüência dos dois eventos.
‣ o princípio pode ser estendido a uma seqüência com qualquer número finito de eventos
‣ verificar a ocorrência de eventos sucessivos
Exemplo 1
• Se um homem tem 4 ternos, 8 camisas e 5 gravatas, de quantas maneiras diferentes ele pode se vestir?
Exemplo 2
• A última parte de um número de telefone contém 4 dígitos. Quantos códigos numéricos de 4 dígitos existem?
Exemplo 3
• Quantos códigos numéricos de 4 dígitos existem, se um mesmo dígito não puder ser repetido?
Seja |C| a cardinalidade de um conjunto C.
Pelo princípio da multiplicação podemos determinar que:
Se A e B são conjuntos finitos,então | A x B | = |A| ⋅ |B|
Exemplo 4
Princípio da Adição
• Se A e B são eventos disjuntos com n1 e n2 resultados possíveis, respectivamente, então o número total de possibilidades para o evento “A ou B” é n1 + n2.
‣ pode ser estendido a qualquer número finito de eventos disjuntos
Exemplo 1
• Um consumidor deseja comprar um veículo em uma concessionária. A concessionária tem 7 automóveis sedã e 8 automóveis “hatch” em estoque. Quantas escolhas possíveis o consumidor tem?
Pelo princípio da adição podemos determinar que:
Se A e B são conjuntos finitos disjuntos,então | A ∪ B | = |A| + |B|.
Se A e B são conjuntos finitos,então | A - B | = |A| - |A ∩ B|.
Exemplo 2
Exercício 1
• Quantos números de 4 dígitos começam com 4 ou 5?
Exercício 2
• Se uma mulher tem 7 blusas, 5 saias e 9 vestidos, de quantas maneiras ela pode se vestir?
Exercício 3
• Quantos inteiros de 3 dígitos são pares?
Exercício 4
• Quantos sufixos de telefone (4 dígitos) existem com pelo menos 1 dígito repetido?
Árvores de Decisão
• Árvores de decisão são representações gráficas das possibilidades de um evento baseado em uma série de escolhas.
Exemplo 1
• Considere o evento de lançar 3 vezes uma moeda. Quais as possíveis seqüências de cara ou coroa podem ser obtidas?
Exemplo 2
• Desenhe uma árvore de decisão para encontrar o número de cadeias binárias de comprimento 3 que não têm zeros consecutivos.
• Por que o princípio da multiplicação não se aplica no exemplo anterior?
‣ Embora o problema consista em eventos sucessivos, o número de resultados possíveis de cada evento não é constante (o número de resultados em um evento depende do resultado do evento anterior).
Resumo
• O princípio da multiplicação é usado para contar o número de resultados possíveis para uma seqüência de eventos, cada um com um número finito de possibilidades.
• O princípio da adição é usado para contar o número de resultados possíveis para eventos disjuntos.
Resumo
• Os princípios da adição e multiplicação podem ser usados juntos.
• As árvores de decisão podem ser usadas para contar o número de resultados possíveis para uma seqüência de eventos onde o número de resultados possíveis não é constante (mas depende do resultado do evento precedente)
Princípio de Inclusão e Exclusão
Sejam A e B subconjuntos de um conjunto universo S.
| A ∪ B | = | A | + | B | - | A ∩ B |
• O princípio pode ser estendido para n conjuntos.
• Para 3 conjuntos:
‣ |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| -| B∩C| + |A∩B∩C|
Exemplo 1
• Em uma pesquisa de opinião pública, foram entrevistados 35 eleitores, todos apoiando o referendo 1, o referendo 2, ou ambos. Sabe-se que 14 eleitores apoiaram o referendo 1 e 26 apoiaram o referendo 2. Quantos apoiaram ambos os referendos?
Exemplo 2
• Um grupo de estudantes está planejando encomendar pizzas. Sabe-se que 13 estudantes gostam de pizza calabresa, 10 gostam de marguerita, 12 gostam de portuguesa, 4 gostam tanto de calabresa quanto marguerita, 5 gostam tanto de marguerita quanto de portuguesa, 7 de calabresa e portuguesa e 3 gostam de todas. Quantos estudantes há no grupo?
Exemplo 3
• Em um grupo de 42 turistas, todos falam inglês ou francês. Sabe-se que 35 falam inglês e 18 falam francês. Quantos falam inglês e francês?
Princípio das Casas de Pombo
• Se mais de k itens são colocados em k recipientes, então pelo menos um recipiente contém mais de um item.
Exemplos
Exemplos
• Em um grupo de 13 pessoas, pelo menos duas fazem aniversário no mesmo mês.
Exemplos
• Em um grupo de 13 pessoas, pelo menos duas fazem aniversário no mesmo mês.
• Quantas vezes é preciso jogar um dado de modo a garantir que um mesmo número apareça duas vezes?
Exemplos
• Em um grupo de 13 pessoas, pelo menos duas fazem aniversário no mesmo mês.
• Quantas vezes é preciso jogar um dado de modo a garantir que um mesmo número apareça duas vezes?
‣ É preciso jogar o dado 7 vezes.
Mais exemplos
Mais exemplos
• Quantas pessoas precisam estar presentes em uma sala para garantir que duas delas tenham o último nome começando com a mesma letra?
Mais exemplos
• Quantas pessoas precisam estar presentes em uma sala para garantir que duas delas tenham o último nome começando com a mesma letra?
‣ 27 pessoas (considerando alfabeto de 26 letras)
Mais exemplos
• Quantas pessoas precisam estar presentes em uma sala para garantir que duas delas tenham o último nome começando com a mesma letra?
‣ 27 pessoas (considerando alfabeto de 26 letras)
• Em um grupo de 25 pessoas, é verdade que existem pelo menos 3 pessoas que nasceram no mesmo mês?
Mais exemplos
• Quantas pessoas precisam estar presentes em uma sala para garantir que duas delas tenham o último nome começando com a mesma letra?
‣ 27 pessoas (considerando alfabeto de 26 letras)
• Em um grupo de 25 pessoas, é verdade que existem pelo menos 3 pessoas que nasceram no mesmo mês?
‣ Sim
Exemplo 4
• Prove que, se quatro números forem escolhidos do conjunto C = {1,2,3,4,5,6}, pelo menos um par (entre os números escolhidos) tem que somar 7.
Resumo
• Uso do Princípio de Inclusão e Exclusão para encontrar o número de elementos em uma união de conjuntos.
• Uso do Princípio das Casas de Pombo para encontrar o número mínimo de elementos que garantem que dois deles têm uma propriedade em comum.