Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Motivação
Contagem
I
Contagem e combinatória são partes importantes da matemática
discreta.
I
Se resumem a contar elementos em conjuntos finitos.
I
Parece fácil mas nem sempre pode-se determinar com facilidade
uma resposta.
I
Problemas de contagem incluem:
Prof. Dr. Leandro Balby Marinho
I
I
I
Matemática Discreta
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
1 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Roteiro
Quantas operações um algoritmo executa?
Quantos endereços IP válidos existem?
Quantas senhas de seis caracteres alfanuméricos existem em
um sistema?
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
2 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Conjuntos Contáveis
1. Conjuntos Contáveis
2. Princı́pios Fundamentais da Contagem
Definição 2
Um conjunto X diz-se contável (ou enumerável) quando ele é um conjunto
finito ou se existe uma bijeção f : X → Y tal que Y ⊆ Z+ , X = {xn | n ∈
Y } sendo xn = f (n) ∀n ∈ Y . Denota-se a cardinalidade de um conjunto
S infinito e contável por |S| = ℵ0 .
3. Princı́pio da Inclusão/Exclusão
4. Princı́pio da Casa dos Pombos
5. Permutações
6. Combinação
Prof. Dr. Leandro Balby Marinho
3 / 28
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
3 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Exemplo 1
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Exercı́cios
Mostre que o conjunto dos inteiros positivosı́mpares é um conjunto contável.
Solução: Considere a função
f (n) = 2n + 1
de Z+ no conjunto dos inteiros positivos ı́mpares. Mostramos que f é
bijetora mostrando que é injetora e sobrejetora ao mesmo tempo.
1. Para verificar que f é injetora, observe que quando f (n) = f (m)
temos 2n + 1 = 2m + 1 ⇒ n = m.
Exercı́cio 1: Mostre que o conjunto dos inteiros é contável.
Exercı́cio 2: Mostre que o conjunto dos racionais positivos é contável.
2. Como cada elemento no contramı́nio está associado a um elemento
no domı́nio então a função também é sobrejetora.
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
4 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Exemplo 2
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Exemplo 2 cont.
Mostre que R é um conjunto não-contável.
Solução: Podemos usar uma prova por contradição. Dessa forma, supomos
que o subconjunto dos reais em [0, 1] é contável1 onde os elementos podem
ser listados como:
r1 = 0.d11 d12 d13 d14 . . .
Suponha um novo número real r onde os dı́gitos decimais seguem a seguinte
regra:
(
4, se dii 6= 4
di =
5, se dii = 4
Agora suponha, por exemplo
r2 = 0.d21 d22 d23 d24 . . .
r1 = 0.23794102 . . .
r3 = 0.d31 d32 d33 d34 . . .
r2 = 0.44590138 . . .
r4 = 0.d41 d42 d43 d44 . . .
..
.
r3 = 0.09118764 . . .
r4 = 0.80553900 . . .
..
.
onde dij ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
1
5 / 28
Note que o subconjunto de um conjunto contável também é contável.
Prof. Dr. Leandro Balby Marinho
6 / 28
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
7 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Exemplo 2 cont.
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Roteiro
1. Conjuntos Contáveis
Portanto temos r = d1 d2 d3 . . . = 0.454 . . ., onde d1 = 4 já que d11 6= 4,
d2 = 5 já que d22 = 4 e assim por diante.
Note que r difere das expansões decimais de ri na i-ésima posição à direita
do ponto decimal, para cada i. Portanto, como r não está na lista, a
hipótese é falsa e o subconjunto dos reais em [0, 1] é incontável.
2. Princı́pios Fundamentais da Contagem
3. Princı́pio da Inclusão/Exclusão
4. Princı́pio da Casa dos Pombos
5. Permutações
6. Combinação
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
8 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Princı́pio da Multiplicação
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
9 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Exemplos
Exemplo 3: Uma empresa com apenas dois empregados, Carlos e Paulo,
aluga um andar em um prédio com 12 escritórios. Quantas formas existem
de alocar diferentes escritórios para esses dois empregados?
I
Se um procedimento pode ser dividido em uma sequência de k
eventos onde há
I
I
I
I
n1 possibilidades para o primeiro evento,
n2 possibilidades para o segundo evento,
nk possibilidades para o k-ésimo evento, então
existem n1 · n2 · . . . · nk possibilidades para a sequência dos eventos.
I
12 possibilidades de alocar um escritório para Carlos.
I
11 possibilidades para alocar um escritório para Paulo.
I
Portanto, 12 · 11 = 132 formas de alocar 12 escritórios para esses
dois empregados.
Exemplo 4: Quantas cadeias de bits de tamanho 7 existem?
Solução: Há duas possibilidades para cada bit, 0 ou 1. Portanto há um
total de 27 = 128 cadeias de bits diferentes.
Prof. Dr. Leandro Balby Marinho
9 / 28
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
10 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Exemplos
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Princı́pio da Adição
Exercı́cio 3: Quantas placas de carro diferentes existem se cada placa
contém uma sequência de três letras seguidas de três dı́gitos?
Exemplo 5: Quantas funções existem de um conjunto com m elementos
em um conjunto com n elementos?
Princı́pio da Adição
Se A e B são eventos disjuntos com |A| = n1 e |B| = n2 resultados
possı́veis, respectivamente, então o número total de possibilidades para o
evento A ∪ B é n1 + n2 .
Solução: Uma função corresponde a escolha de um dos n elementos no
codomı́nio para cada um dos m elementos do domı́nio. Portanto, há nm
funções possı́veis.
Exemplo 6: Um cliente deseja comprar um veı́culo de uma concessionária
que dispõe de 23 carros e 14 motocicletas em estoque. Quantas escolhas
possı́veis o cliente pode ter?
Exercı́cio 4: Quantas funções injetoras existem de um conjunto com m
elementos em um conjunto com n elementos?
Solução: O cliente deseja escolher um carro ou uma motocicleta. São
eventos disjuntos com 23 possibilidade de escolha de um carro e 14 de
uma motocicleta. Pelo princı́pio da adição, a escolha de um veı́culo tem
23 + 14 = 37 possibilidades.
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
11 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Princı́pio da Adição
Conjuntos Contáveis
Fundamentos
12 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Combinando os Princı́pios Fundamentais da Contagem
Princı́pio Geral da Adição
Exemplo 7: Quantos números de 4 dı́gitos começam com 4 ou com 5?
Sejam A1 , A2 , . . . , Am conjuntos finitos disjuntos, então o número de elementos na união desses conjuntos é dado por:
|A1 ∪ A2 ∪ . . . ∪ Am | = |A1 | + |A2 | + . . . + |Am |
Exercı́cio 5: Um aluno pode escolher um projeto de uma de três listas.
As três listas contém 23,15 e 19 possı́veis projetos respectivamente.
Nenhum projeto está em mais de uma lista. Quantos projetos possı́veis os
alunos podem escolher?
Prof. Dr. Leandro Balby Marinho
Prof. Dr. Leandro Balby Marinho
13 / 28
UFCG CEEI
Solução: Podemos considerar dois conjuntos disjuntos: números que começam
com 4 e números que começam com 5. Portanto, são 1 · 10 · 10 · 10 = 1000
formas de escolher um número de 4 dı́gitos começando com o 4.
Para a contagem do segundo conjunto se aplica o mesmo raciocı́nio dando
o mesmo resultado: 1000.
Usando agora o Princı́pio da Adição, podemos deduzir que existem 1000 +
1000 = 2000 resultados possı́veis ao todo.
Prof. Dr. Leandro Balby Marinho
14 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Exercı́cios
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Roteiro
1. Conjuntos Contáveis
Exercı́cio 6: Numa versão da linguagem de programação BASIC o nome da
variável é uma cadeia de um ou dois caracteres alfanuméricos. Além disso,
um nome de variável deve começar com uma letra e deve ser diferente das
5 cadeias de dois caracteres que são reservadas pela linguagem. Quantos
nomes possı́veis de variáveis existem nessa versão do BASIC?
Exercı́cio 7: Cada usuário de um sistema possui uma senha que compreende de 6 a 8 caracteres alfanuméricos. Cada senha deve possuir pelo
menos um dı́gito. Quantas senhas possı́veis existem nesse sistema?
2. Princı́pios Fundamentais da Contagem
3. Princı́pio da Inclusão/Exclusão
4. Princı́pio da Casa dos Pombos
5. Permutações
6. Combinação
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
15 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Princı́pio da Inclusão/Exclusão
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
16 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Exemplos
Exemplo 4: Um vendedor oferece 2 produtos e 35 pessoas compraram.
Destes, 14 compraram o produto 1 e 26 o produto 2. Quantos compraram
ambos?
Princı́pio da Inclusão/Exclusão
Quando contamos o número de elementos de |AeB|, precisamos incluir
(contar) o número de elementos em A e o número de elementos em B,
mas devemos excluir (subtrair) os elementos que pertencem a A ∩ B para
evitar contá-los duas vezes. Portanto,
Solução: Seja A o conjunto das pessoas que escolheram o produto 1 e B
o conjunto dos que escolheram o produto 2.
|A ∪ B| = 35, |A| = 14, |B| = 26
Mas,
|A ∩ B| = |A| + |B| − |A ∪ B| = 14 + 26 − 35 = 5
|A ∪ B| = |A| + |B| − |A ∩ B|
Portanto, 5 entrevistados escolheram ambos os produtos.
Prof. Dr. Leandro Balby Marinho
16 / 28
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
17 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Roteiro
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Definição
Princı́pio da Casa dos Pombos
1. Conjuntos Contáveis
Se k + 1 itens são postos em k caixas, então pelo menos uma caixa
contém mais de um item.
2. Princı́pios Fundamentais da Contagem
3. Princı́pio da Inclusão/Exclusão
4. Princı́pio da Casa dos Pombos
5. Permutações
6. Combinação
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
18 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Corolário sobre Funções Não-Injetoras
Corolário 1
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Exemplo 5: Quantas pessoas precisam estar presentes em uma sala para
garantir que pelo menos duas delas tenham o primeiro nome começando
com a mesma letra?
Solução: 27, pois pelo princı́pio da casa dos pombos, existiriam 27 iniciais
para se colocar em 26 caixas, de modo que pelo menos uma caixa vai
conter mais de uma inicial.
Uma função f de um conjunto com k + 1 ou mais elementos em um
conjunto com k elementos não é injetora.
Prova: Pelo princı́pio da casa dos pombos, vemos que como o domı́nio
possui pelo menos k + 1 elementos e o codomı́nio k elementos, então vai
haver pelo menos uma imagem com duas ou mais pré-imagens.
19 / 28
Conjuntos Contáveis
18 / 28
Exemplos
O princı́pio da casa dos pombos pode ser usado para provar o seguinte
corolário sobre funções.
Prof. Dr. Leandro Balby Marinho
Prof. Dr. Leandro Balby Marinho
UFCG CEEI
Exercı́cio 6: Quantas vezes é preciso jogar um dado de modo a garantir
que um mesmo valor apareça duas vezes?
Exercı́cio 7: Quantas pessoas são necessárias para garantir que pelo
menos duas delas tenham aniversário no mesmo dia?
Prof. Dr. Leandro Balby Marinho
20 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Generalização do Princı́pio da Casa dos Pombos
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Roteiro
1. Conjuntos Contáveis
Generalização do Princı́pio da Casa dos Pombos
Se n itens são colocados em k caixas, então há pelo menos uma caixa
com dn/ke itens.
2. Princı́pios Fundamentais da Contagem
Exemplo 6: Qual o número mı́nimo de alunos necessário em um curso de
matemática discreta de modo a garantir que pelo menos seis receberão a
mesma nota, se há cinco notas possı́veis, {5, 6, 7, 8, 9, 10}?
Solução: Devemos encontrar o menor inteiro n tal que dn/5e = 6. Esse
inteiro é
n = 5 · 5 + 1 = 26
3. Princı́pio da Inclusão/Exclusão
4. Princı́pio da Casa dos Pombos
5. Permutações
6. Combinação
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
21 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Introdução
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
22 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Contando Permutações
Teorema 1
I
Uma permutação de um conjunto de elementos distintos é um
arranjo ordenado desses objetos.
I
Muitos problemas de contagem são resolvidos contando-se o
número de permutações possı́veis em um conjunto.
Se n é um inteiro positivo e r um inteiro com 1 ≤ r ≤ n, então há
P(n, r ) = n(n − 1)(n − 2) . . . (n − r + 1)
r permutações de um conjunto com n elementos distintos.
Exemplo 8: Em quantas formas podemos alinhar três estudantes de um
grupo de cinco estudantes para uma foto? Em quantas formas podemos
alinhar todos os cinco estudantes para uma foto?
Solução: Há 5 · 4 · 3 = 60 formas de selecionar três estudantes de um
grupo de cinco. E há 5 · 4 · 3 · 2 · 1 = 120 formas de alinhar todos os cinco
estudantes para uma foto.
Prova: Pelo princı́pio da multiplicação, há n formas de escolher o
primeiro elemento, n − 1 formas de escolher o segundo elemento, . . . até
exatamente n − (r − 1) = n − r + 1 formas de escolher o r -ésimo
elemento. Consequentemente há
n(n − 1)(n − 2) . . . (n − r + 1)
permutações do conjunto.
Prof. Dr. Leandro Balby Marinho
22 / 28
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
23 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Contando Permutações
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Permutações com Repetições
Corolário 2
Segue to Teorema 1 que se n e r são inteiros com 0 ≤ r ≤ n, então
P(n, r ) =
n!
(n − r )!
Teorema 3
O número de permutações de r objetos de um conjunto de n objetos com
repetição é nr .
Exemplo 9: Dez atletas competem um evento olı́mpico. São dadas medalhas de ouro, prata e bronze. De quantas maneiras diferentes podem ser
dadas as medalhas?
Solução: P(10, 3) = 10!/7! = 10 · 9 · 8 = 720
Exercı́cio 8: Um representante de vendas deve visitar seis cidades
diferentes. Ele deve iniciar sua viagem em uma determinada cidade, mas
pode visitar as outras cinco em qualquer ordem que desejar. Quantas
ordens possı́veis de visita o representante pode escolher para visitar as
cidades?
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
24 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Exemplos
Prova: Pelo princı́pio da multiplicação, há n formas de escolher um elemento do conjunto para cada uma das r posições na permutação com
repetição, e sendo assim nr permutações com repetição são permitidas
(ver Exemplo 4).
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
25 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Roteiro
1. Conjuntos Contáveis
Exemplo 10: Quantas cadeias de tamanho r existem no alfabeto da lı́ngua
Portuguesa?
2. Princı́pios Fundamentais da Contagem
Solução: Pelo Teorema 3, existem 26r cadeias de de tamanho r na lı́ngua
Portuguesa
3. Princı́pio da Inclusão/Exclusão
Exercı́cio 9: Quantas formas há de alocar três tarefas para cinco alunos,
se cada aluno pode receber mais de uma tarefa?
4. Princı́pio da Casa dos Pombos
5. Permutações
6. Combinação
Prof. Dr. Leandro Balby Marinho
26 / 28
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
27 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Introdução
Conjuntos Contáveis
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Contando Combinações
Uma combinação de elementos de um conjunto é uma seleção não
ordenada de elementos desse conjunto.
Teorema 2
O número de combinações de um conjunto com n elementos, no qual n é
um inteiro não negativo e r um inteiro com 0 ≤ r ≤ n é
Exemplo 11: Seja S o conjunto {1, 2, 3, 4}. Então {1, 3, 4} é uma
combinação de três elementos de S.
C (n, r ) =
O número de combinações de r objetos distintos
escolhidos entre n
n
.
objetos distintos é denotado por C (n, r ) ou
r
Exemplo 12: Quantas combinações de dois elementos podemos obter do
conjunto P = {a, b, c, d}?
Prof. Dr. Leandro Balby Marinho
Fundamentos
27 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Problemas de Combinação
n!
r !(n − r )!
Prova: Pelo princı́pio da multiplicação, P(n, r ) = C (n, r ) · P(r , r ).
Consequentemente,
Solução: C (4, 2) = 6, pois há seis subconjuntos de dois elementos em P,
i.e., {a, b}, {a, c}, {b, c}, {b, d} e {c, d}.
Conjuntos Contáveis
Fundamentos
C (n, r ) =
P(n, r )
n!/(n − r )!
n!
=
=
P(r , r )
r !/(r − r )!
r !(n − r )!
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
28 / 28
Inclusão/Exclusão
UFCG CEEI
Princı́pio da Casa dos Pombos
Permutações
Combinações
Combinação com Repetição
Exercı́cio 10: Uma comissão de 8 alunos deve ser escolhida em um
grupo contendo 15 alunos do curso de matemática discreta (MD) e 20 do
curso de teoria dos grafos (TG).
a) De quantas maneiras é possı́vel selecionar 3 alunos de MD e 5 de TG?
b) De quantas maneiras é possı́vel selecionar uma comissão contendo
exatamente 1 aluno de MD?
c) De quantas maneiras é possı́vel selecionar uma comissão contendo no
máximo 1 aluno de MD?
d) De quantas maneiras é possı́vel selecionar uma comissão contendo
pelo menos 1 aluno de MD?
Exemplo 13: Quantas formas há de escolher quatro frutas de uma cesta
contendo maçãs, laranjas e pêras se a ordem na qual as frutas são escolhidas
não importa, e há pelo menos quatro frutas de cada tipo na cesta?
Solução: Para solucionar esse problema listamos todas as formas de escolher as frutas.
4
3
3
2
2
maçãs
maçãs, 1 laranja
laranjas, 1 pêra
maçãs, 2 laranjas
maçãs, 1 laranja, 1 pêra
4
3
3
2
2
laranjas
maçãs, 1 pêra
pêras, 1 maçã
maçãs, 2 pêras
laranjas, 1 maçã, 1 pêra
4
3
3
2
2
pêras
laranjas, 1 maçã
pêras, 1 laranja
laranjas, 2 pêras
pêras, 1 maçã, 1 laranja
A solução é o número de combinações de quatro elementos com repetição
de um conjunto de três elementos {maçã, laranja, pêra}.
Prof. Dr. Leandro Balby Marinho
29 / 28
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
30 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Combinação com Repetição
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Exemplo 14 cont.
Exemplo 14: Quantas formas há de escolher cinco notas de uma caixa
contendo notas de $1, $2, $5, $10, $20, $50 e $100? Assuma que a ordem
em que as notas são escolhidas não importa, as notas de cada denominação
são indistintas e que há no mı́nimo 5 notas de cada tipo.
O problema corresponde ao número de formas de arranjar 6 barras e 5
asteriscos.
Solução: Esse problema envolve contar combinações de 5 elementos com
repetição em um conjunto com 7 elementos. Suponha uma caixa com um
compartimento para da uma das 7 notas.
Nesse caso, C (11, 5) =
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
31 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Combinação com Repetição
Prof. Dr. Leandro Balby Marinho
Conjuntos Contáveis
Fundamentos
32 / 28
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
UFCG CEEI
Permutações
Combinações
Exemplos
Exemplo 15: Suponha que uma chocolateria tem 4 tipos diferentes de
chocolate. De quantas formas diferentes 6 chocolates podem ser
escolhidos? Assuma que a ordem da escolha não importa.
Teorema 4
Há C (n + r − 1, r ) combinações com repetição de um conjunto com n
elementos.
Prova: Cada combinação com repetição de r elementos pode ser representada por uma lista de n − 1 barras e r asteriscos. Então o número de tais
listas é C (n + r − 1, r ) pois cada lista corresponde a uma escolha para as
r posições para dispor r asteriscos das n + r − 1 posições que contém r
asteriscos e n − 1 barras.
Prof. Dr. Leandro Balby Marinho
11!
= 462
5!6!
33 / 28
UFCG CEEI
Solução: O problema é escolher 6 chocolates com repetição de um
conjunto com 4 tipos diferentes de chocolate. Pelo Teorema 4 temos
C (9, 6) =
Prof. Dr. Leandro Balby Marinho
9.8.7
= 84
3.2.1
34 / 28
UFCG CEEI
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Resumo
Conjuntos Contáveis
Fundamentos
Inclusão/Exclusão
Princı́pio da Casa dos Pombos
Permutações
Combinações
Referências
Tipo
Repetição
r -permutações
Não
r -combinações
Não
r -permutações
Sim
r -combinações
Sim
Prof. Dr. Leandro Balby Marinho
35 / 28
Fórmula
n!
(n − r )!
n!
r !(n − r )!
nr
(n + r − 1)!
r !(n − 1)!
Keneth H. Rosen. Discrete Mathematics and Its Applications.
Sexta Edição. McGRAW-HILL International Edition, 2007.
Judith L. Gersting. Fundamentos Matemáticos para a Ciência
da Computação. Quinta Edição. LTC, 2004.
“Function.” Wikipedia. Wikimedia Foundation Inc.. 15 Out
2010. hhttp://en.wikipedia.org/wiki/Function (mathematics)i.
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
36 / 28
UFCG CEEI