Princípios de Contagem

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.