Contagem
George Darmiton da Cunha Cavalcanti
CIn - UFPE
Sumário
• Princípios Básicos de Contagem
– A Regra do Produto
– A Regra da Soma
– O número de subconjuntos de um conjunto finito
• Princípio da Inclusão-Exclusão
• Princípio da Casa do Pombo
A Regra do Produto
• Suponha que um procedimento pode ser
quebrado em uma seqüência que duas
tarefas.
• Se existem n1 maneiras de fazer a primeira
tarefa e n2 maneiras de fazer a segunda
tarefa após a finalização da primeira
• Então existem n1n2 maneiras de realizar o
procedimento.
Exemplo
• As cadeiras de uma auditório serão
rotuladas com uma letra e um inteiro
positivo menor ou igual a 100.
• Qual é o maior número de cadeiras que
podem ser rotuladas de maneira diferente?
Exemplo
• Quantos números binários diferentes podese ter com comprimento igual a 7?
Exemplo
• Quantas placas de carros diferentes pode-se
ter se cada uma delas contém uma
seqüência de três letras seguidas de quatro
dígitos?
Exemplo
• Contando funções
– Quantas funções existem de um conjunto de m
elementos para um conjunto com n elementos?
– Quantas funções injetoras (one-to-one) existem
de um conjunto de m elementos para um
conjunto com n elementos?
Exemplo
O número de subconjuntos de um conjunto finito
– Use a regra do produto para mostrar que o número de
diferentes subconjuntos de um conjunto finito S é igual a
2|S|.
– Existe uma correspondência um-para-um (uma bijeção)
entre os subconjuntos de S e uma string de bits de
tamanho |S|.
– Um subconjunto de S é associado a uma string com valor
1 na i-ésima posição se o i-ésimo elemento na lista
encontra-se no subconjunto; e 0 caso contrário.
A Regra da Soma
• Se uma primeira tarefa pode ser realizada de
n1 maneiras e a segunda tarefa pode ser
realizada de n2 maneiras
• E essas tarefas não podem ser realizadas ao
mesmo tempo
• Então, existem n1+n2 maneiras de realizar
uma dessas tarefas.
Exemplo
• Suponha que um dos professores ou um dos
alunos será escolhido como um
representante de um comitê universitário.
• De quantas maneiras é possível selecionar
um representante sabendo que são 37
professores e 83 alunos?
Exemplo
• Um estudante pode escolher um projeto de
uma de três listas existentes.
• Cada uma das listas contém 23, 15 e 19
possíveis projetos, respectivamente.
• Qual a quantidade de possíveis escolhas de
projetos?
Exemplo
• Em uma versão da linguagem BASIC, o nome de
uma variável é uma string com um ou dois
caracteres alfanuméricos, sabendo que caracteres
maiúsculos e minúsculos não são distinguidos.
• O nome da variável deve começar por uma letra e
deve ser diferente de cinco strings com dois
caracteres que são palavras reservadas da
linguagem.
• Quantos nomes diferentes de variáveis podem ser
criados nessa versão de BASIC?
Exemplo
• Cada usuário em um sistema computacional
possui uma senha de tamanho 6, 7 ou 8
caracteres.
• Cada caractere é uma letra maiúscula ou um
dígito. Cada senha deve conter pelo menos
um dígito.
• Quantas senhas são possíveis nesse
sistema?
Princípio da Inclusão-Exclusão
• Em uma sala de aula temos 90 estudantes e
70 solteiros.
• Quantos estudantes solteiros existem nessa
sala de aula?
• Sem o auxílio de mais informações não é
possível responder essa pergunta.
Exemplo
• Uma classe de matemática discreta tem 25
estudantes de computação, 13 estudantes de
matemática e 8 estudantes de matemática e
computação.
• A classe possui quantos estudantes?
|A∪B| = |A| + |B| – |A∩B|
= 25 + 13 – 8
= 30
Exemplo
• Quantos inteiros positivos menor ou igual a
1000 são divisíveis por 7ou 11?
A – conjuntos dos inteiros ≤1000 divisíveis por 7
B – conjuntos dos inteiros ≤1000 divisíveis por 11
A∩B – conjuntos dos inteiros ≤1000 divisíveis por 7 e 11
A∪B – conjuntos dos inteiros ≤1000 divisíveis por 7 ou 11
Exemplo
• Suponha que existam 1807 calouros na faculdade. Do total,
453 são de computação, 567 de matemática e 299 estão
fazendo dois cursos, matemática e computação.
• Quantos não estão fazendo nem computação nem matemática?
A – conjuntos dos calouros de computação
B – conjuntos dos calouros de matemática
A∩B – conjuntos dos calouros que fazem matemática e computação
A∪B – conjuntos dos calouros que fazem matemática ou computação
A∪B = A + B – A∩B
= 453 + 567 – 299 = 721
1807 – 721 = 1086 calouros não fazem nem computação nem matemática
Exemplo
1232 estudantes fazem curso de espanhol, 879 francês, 114 russo.
103 fazem espanhol e francês, 23 espanhol e russo e 14 francês e russo.
2092 estudantes fazem pelo menos um curso de espanhol, francês ou russo.
Quantos estudantes fazem os três cursos?
|E| = 1232 – espanhol
|E∩F| = 103
|E∪F∪R| = 2092
|F| = 879 – francês
|E∩R| = 23
|R| = 114 – russo
|F∩R| = 14
|E∪F∪R| = |E| + |F| + |R| – |E∩F| – |E∩R| – |F∩R| + |E∩F∩R|
2092 = 1232 + 879 + 114 – 103 – 23 – 14 + |E∩F∩R|
|E∩F∩R| = 7
Princípio da Inclusão-Exclusão
Teorema
Princípio da Casa do Pombo
Teorema: Princípio da Casa do Pombo
Se k+1 ou mais objetos são colocados em k
caixas, então existe pelo menos uma caixa que
contém dois ou mais objetos.
Princípio da Casa do Pombo
Existem mais pombos do que casas de pombo.
Exemplo
• Dentre um grupo de 367 pessoas, deve
existir pelo menos duas que têm o mesmo
dia de aniversário.
• Pois têm-se apenas 366 possíveis dias de
nascimento.
Exemplo
• Em um grupo com 27 palavras em inglês,
deve existir pelo menos duas que começam
com a mesma letra.
• Uma vez que existem 26 letras no alfabeto
da língua inglesa.
Exemplo
Quantos estudantes devem existir em uma
sala de aula para garantir que pelo menos dois
estudantes irão receber a mesma nota em uma
prova cuja pontuação varia de 0 a 100?
101 pontuações possíveis
102 estudantes são necessários para que pelo
menos 2 tenham a mesma nota.
Princípio da Casa do Pombo Generalizado
Teorema: Princípio da Casa do Pombo
Generalizado
Exemplo
Entre 100 pessoas existem pelo menos
100/12 =9 quem nasceram no mesmo mês.
Exemplo
Qual é o número mínimo de estudantes em uma classe de
matemática discreta de forma que pelo menos seis receberão a
mesma pontuação?
Adote que existem cinco pontuações: A, B, C, D e F.
O número mínimo de estudantes é o menor inteiro N de forma
que N/5 =6.
Assim, N = 5×5+1=26.