contagem_2012_1

Prévia do material em texto

Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Contagem
Prof. Dr. Leandro Balby Marinho
Matema´tica Discreta
Prof. Dr. Leandro Balby Marinho 1 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Motivac¸a˜o
I Contagem e combinato´ria sa˜o partes importantes da matema´tica
discreta.
I Se resumem a contar elementos em conjuntos finitos.
I Problemas de contagem incluem:
I Quantas operac¸o˜es um algoritmo executa?
I Quantos enderec¸os IP va´lidos existem?
I Quantas senhas de seis caracteres alfanume´ricos existem em
um sistema computacional?
Prof. Dr. Leandro Balby Marinho 2 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Motivac¸a˜o
I Contagem e combinato´ria sa˜o partes importantes da matema´tica
discreta.
I Se resumem a contar elementos em conjuntos finitos.
I Problemas de contagem incluem:
I Quantas operac¸o˜es um algoritmo executa?
I Quantos enderec¸os IP va´lidos existem?
I Quantas senhas de seis caracteres alfanume´ricos existem em
um sistema computacional?
Prof. Dr. Leandro Balby Marinho 2 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Motivac¸a˜o
I Contagem e combinato´ria sa˜o partes importantes da matema´tica
discreta.
I Se resumem a contar elementos em conjuntos finitos.
I Problemas de contagem incluem:
I Quantas operac¸o˜es um algoritmo executa?
I Quantos enderec¸os IP va´lidos existem?
I Quantas senhas de seis caracteres alfanume´ricos existem em
um sistema computacional?
Prof. Dr. Leandro Balby Marinho 2 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Motivac¸a˜o
I Contagem e combinato´ria sa˜o partes importantes da matema´tica
discreta.
I Se resumem a contar elementos em conjuntos finitos.
I Problemas de contagem incluem:
I Quantas operac¸o˜es um algoritmo executa?
I Quantos enderec¸os IP va´lidos existem?
I Quantas senhas de seis caracteres alfanume´ricos existem em
um sistema computacional?
Prof. Dr. Leandro Balby Marinho 2 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Motivac¸a˜o
I Contagem e combinato´ria sa˜o partes importantes da matema´tica
discreta.
I Se resumem a contar elementos em conjuntos finitos.
I Problemas de contagem incluem:
I Quantas operac¸o˜es um algoritmo executa?
I Quantos enderec¸os IP va´lidos existem?
I Quantas senhas de seis caracteres alfanume´ricos existem em
um sistema computacional?
Prof. Dr. Leandro Balby Marinho 2 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Motivac¸a˜o
I Contagem e combinato´ria sa˜o partes importantes da matema´tica
discreta.
I Se resumem a contar elementos em conjuntos finitos.
I Problemas de contagem incluem:
I Quantas operac¸o˜es um algoritmo executa?
I Quantos enderec¸os IP va´lidos existem?
I Quantas senhas de seis caracteres alfanume´ricos existem em
um sistema computacional?
Prof. Dr. Leandro Balby Marinho 2 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Roteiro
1. Princ´ıpios Fundamentais da Contagem
2. Princ´ıpio da Inclusa˜o/Exclusa˜o
3. Princ´ıpio da Casa dos Pombos
4. Permutac¸o˜es
5. Combinac¸a˜o
Prof. Dr. Leandro Balby Marinho 3 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Princ´ıpio da Multiplicac¸a˜o
Definic¸a˜o 1
Assuma que um procedimento pode ser dividido em uma sequeˆncia
de k eventos. Se ha´ n1 possibilidades para o primeiro evento e para
cada dessas possibilidades do primeiro evento, ha´ n2 possibilidades
para o segundo evento, e assim por diante, existem
n1 · n2 · . . . · nk
possibilidades para a sequeˆncia de eventos.
Prof. Dr. Leandro Balby Marinho 3 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 1: Com a reforma da Universidade, o DSC tera´ 10 salas novas
para professores. Quantas formas existem de alocar diferentes salas para
dois professores rece´m contratados?
I 10 possibilidades de alocar uma sala para o primeiro professor.
I 9 possibilidades para alocar uma sala para o segundo professor.
I Portanto, 10 · 9 = 90 formas de alocar 10 salas para esses dois
professores.
Exemplo 2: 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 4 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 1: Com a reforma da Universidade, o DSC tera´ 10 salas novas
para professores. Quantas formas existem de alocar diferentes salas para
dois professores rece´m contratados?
I 10 possibilidades de alocar uma sala para o primeiro professor.
I 9 possibilidades para alocar uma sala para o segundo professor.
I Portanto, 10 · 9 = 90 formas de alocar 10 salas para esses dois
professores.
Exemplo 2: 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 4 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 1: Com a reforma da Universidade, o DSC tera´ 10 salas novas
para professores. Quantas formas existem de alocar diferentes salas para
dois professores rece´m contratados?
I 10 possibilidades de alocar uma sala para o primeiro professor.
I 9 possibilidades para alocar uma sala para o segundo professor.
I Portanto, 10 · 9 = 90 formas de alocar 10 salas para esses dois
professores.
Exemplo 2: 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 4 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 1: Com a reforma da Universidade, o DSC tera´ 10 salas novas
para professores. Quantas formas existem de alocar diferentes salas para
dois professores rece´m contratados?
I 10 possibilidades de alocar uma sala para o primeiro professor.
I 9 possibilidades para alocar uma sala para o segundo professor.
I Portanto, 10 · 9 = 90 formas de alocar 10 salas para esses dois
professores.
Exemplo 2: 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 4 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exerc´ıcio 1: 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 3: Quantas func¸o˜es existem de um conjunto com m elementos
em um conjunto com n elementos?
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.
Exerc´ıcio 2: Quantas func¸o˜es injetoras existem de um conjunto com m
elementos em um conjunto com n elementos?
Prof. Dr. Leandro Balby Marinho 5 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exerc´ıcio 1: Quantas placas de carro diferentes existemse cada placa
conte´m uma sequeˆncia de treˆs letras seguidas de treˆs d´ıgitos?
Exemplo 3: Quantas func¸o˜es existem de um conjunto com m elementos
em um conjunto com n elementos?
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.
Exerc´ıcio 2: Quantas func¸o˜es injetoras existem de um conjunto com m
elementos em um conjunto com n elementos?
Prof. Dr. Leandro Balby Marinho 5 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exerc´ıcio 1: 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 3: Quantas func¸o˜es existem de um conjunto com m elementos
em um conjunto com n elementos?
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.
Exerc´ıcio 2: Quantas func¸o˜es injetoras existem de um conjunto com m
elementos em um conjunto com n elementos?
Prof. Dr. Leandro Balby Marinho 5 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exerc´ıcio 1: 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 3: Quantas func¸o˜es existem de um conjunto com m elementos
em um conjunto com n elementos?
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.
Exerc´ıcio 2: Quantas func¸o˜es injetoras existem de um conjunto com m
elementos em um conjunto com n elementos?
Prof. Dr. Leandro Balby Marinho 5 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Princ´ıpio da Adic¸a˜o
Definic¸a˜o 2
Sejam A1,A2, . . . ,Am conjuntos finitos disjuntos. O nu´mero de ele-
mentos na unia˜o desses conjuntos e´ dado por:
|A1 ∪ A2 ∪ . . . ∪ Am| = |A1|+ |A2|+ . . . + |Am|
Prof. Dr. Leandro Balby Marinho 6 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 4: 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?
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.
Exerc´ıcio 3: 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 7 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 4: 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?
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.
Exerc´ıcio 3: 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 7 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 4: 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?
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.
Exerc´ıcio 3: 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 7 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinando os Princ´ıpios Fundamentais da Contagem
Os princ´ıpios fundamentais da contagem podem ser combinados para a
resoluc¸a˜o de problemas mais complexos.
Exemplo 5: Quantos nu´meros de 4 d´ıgitos comec¸am com 4 ou com 5?
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 8 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinando os Princ´ıpios Fundamentais da Contagem
Os princ´ıpios fundamentais da contagem podem ser combinados para a
resoluc¸a˜o de problemas mais complexos.
Exemplo 5: Quantos nu´meros de 4 d´ıgitos comec¸am com 4 ou com 5?
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 8 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinando os Princ´ıpios Fundamentais da Contagem
Os princ´ıpios fundamentais da contagem podem ser combinados para a
resoluc¸a˜o de problemas mais complexos.
Exemplo 5: Quantos nu´meros de 4 d´ıgitos comec¸am com 4 ou com 5?
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 8 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinando os Princ´ıpios Fundamentais da Contagem
Os princ´ıpios fundamentais da contagem podem ser combinados para a
resoluc¸a˜o de problemas mais complexos.
Exemplo 5: Quantos nu´meros de 4 d´ıgitos comec¸am com 4 ou com 5?
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 = 2000resultados poss´ıveis ao todo.
Prof. Dr. Leandro Balby Marinho 8 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exerc´ıcios
Exerc´ıcio 4: 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 5: 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?
Prof. Dr. Leandro Balby Marinho 9 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exerc´ıcios
Exerc´ıcio 4: 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 5: 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?
Prof. Dr. Leandro Balby Marinho 9 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Roteiro
1. Princ´ıpios Fundamentais da Contagem
2. Princ´ıpio da Inclusa˜o/Exclusa˜o
3. Princ´ıpio da Casa dos Pombos
4. Permutac¸o˜es
5. Combinac¸a˜o
Prof. Dr. Leandro Balby Marinho 10 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Princ´ıpio da Inclusa˜o/Exclusa˜o
Princ´ıpio da Inclusa˜o/Exclusa˜o
Quando contamos o nu´mero de elementos de |A ∪ B|, 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,
|A ∪ B| = |A|+ |B| − |A ∩ B|
Prof. Dr. Leandro Balby Marinho 10 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 6: Um vendedor oferece 2 produtos e 35 pessoas compraram.
Destes, 14 compraram o produto 1 e 26 o produto 2. Quantos compraram
ambos?
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
Portanto, 5 entrevistados escolheram ambos os produtos.
Prof. Dr. Leandro Balby Marinho 11 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 6: Um vendedor oferece 2 produtos e 35 pessoas compraram.
Destes, 14 compraram o produto 1 e 26 o produto 2. Quantos compraram
ambos?
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
Portanto, 5 entrevistados escolheram ambos os produtos.
Prof. Dr. Leandro Balby Marinho 11 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 6: Um vendedor oferece 2 produtos e 35 pessoas compraram.
Destes, 14 compraram o produto 1 e 26 o produto 2. Quantos compraram
ambos?
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
Portanto, 5 entrevistados escolheram ambos os produtos.
Prof. Dr. Leandro Balby Marinho 11 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 6: Um vendedor oferece 2 produtos e 35 pessoas compraram.
Destes, 14 compraram o produto 1 e 26 o produto 2. Quantos compraram
ambos?
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
Portanto, 5 entrevistados escolheram ambos os produtos.
Prof. Dr. Leandro Balby Marinho 11 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 6: Um vendedor oferece 2 produtos e 35 pessoas compraram.
Destes, 14 compraram o produto 1 e 26 o produto 2. Quantos compraram
ambos?
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
Portanto, 5 entrevistados escolheram ambos os produtos.
Prof. Dr. Leandro Balby Marinho 11 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Roteiro
1. Princ´ıpios Fundamentais da Contagem
2. Princ´ıpio da Inclusa˜o/Exclusa˜o
3. Princ´ıpio da Casa dos Pombos
4. Permutac¸o˜es
5. Combinac¸a˜o
Prof. Dr. Leandro Balby Marinho 12 / 34 UFCG CEEI
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
Se k + 1 itens sa˜o postos em k caixas, enta˜o pelo menos uma caixa
conte´m mais de um item.
Prof. Dr. Leandro Balby Marinho 12 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Corola´rio sobre Func¸o˜es Na˜o-Injetoras
O princ´ıpio da casa dos pombos pode ser usado para provar o seguinte
corola´rio sobre func¸o˜es.
Corola´rio 1
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.
Prof. Dr. Leandro Balby Marinho 13 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Corola´rio sobre Func¸o˜es Na˜o-Injetoras
O princ´ıpio da casa dos pombos pode ser usado para provar o seguinte
corola´rio sobre func¸o˜es.
Corola´rio 1
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.
Prof. Dr. Leandro Balby Marinho 13 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 7: 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.
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 14 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 7: Quantas pessoasprecisam 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.
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 14 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 7: 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.
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 14 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 7: 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.
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 14 / 34 UFCG CEEI
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
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.
Prof. Dr. Leandro Balby Marinho 15 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 8: 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, {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
Exerc´ıcio 8: Quantas cartas devem ser selecionadas de um baralho
de 52 cartas de modo a garantir que pelo menos 3 cartas do
mesmo naipe sera˜o escolhidas?
Prof. Dr. Leandro Balby Marinho 16 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 8: 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, {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
Exerc´ıcio 8: Quantas cartas devem ser selecionadas de um baralho
de 52 cartas de modo a garantir que pelo menos 3 cartas do
mesmo naipe sera˜o escolhidas?
Prof. Dr. Leandro Balby Marinho 16 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 8: 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, {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
Exerc´ıcio 8: Quantas cartas devem ser selecionadas de um baralho
de 52 cartas de modo a garantir que pelo menos 3 cartas do
mesmo naipe sera˜o escolhidas?
Prof. Dr. Leandro Balby Marinho 16 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Roteiro
1. Princ´ıpios Fundamentais da Contagem
2. Princ´ıpio da Inclusa˜o/Exclusa˜o
3. Princ´ıpio da Casa dos Pombos
4. Permutac¸o˜es
5. Combinac¸a˜o
Prof. Dr. Leandro Balby Marinho 17 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Introduc¸a˜o
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 de elementos em um conjunto.
Prof. Dr. Leandro Balby Marinho 17 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Introduc¸a˜o
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 de elementos em um conjunto.
Prof. Dr. Leandro Balby Marinho 17 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplo 9
Em quantas formas podemos alinhar cinco estudantes de um grupo
de cinco estudantes para uma foto? Em quantas formas podemos
alinhar treˆs de cinco estudantes para uma foto?
Soluc¸a˜o: Ha´ 5 · 4 · 3 · 2 · 1 = 120 formas de alinhar todos os cinco
estudantes para uma foto. E ha´ 5 · 4 · 3 = 60 formas de selecionar
treˆs estudantes de um grupo de cinco
Prof. Dr. Leandro Balby Marinho 18 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplo 9
Em quantas formas podemos alinhar cinco estudantes de um grupo
de cinco estudantes para uma foto? Em quantas formas podemos
alinhar treˆs de cinco estudantes para uma foto?
Soluc¸a˜o: Ha´ 5 · 4 · 3 · 2 · 1 = 120 formas de alinhar todos os cinco
estudantes para uma foto. E ha´ 5 · 4 · 3 = 60 formas de selecionar
treˆs estudantes de um grupo de cinco
Prof. Dr. Leandro Balby Marinho 18 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Contando Permutac¸o˜es
Teorema 1
Se n e´ um inteiro positivo e r um inteiro com 0 ≤ r ≤ n, enta˜o ha´
P(n, r) = n(n − 1)(n − 2) . . . (n − r + 1)
r permutac¸o˜es de r objetos entre n objetos distintos.
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´ exata-
mente 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 de r -elementos no conjunto.
Prof. Dr. Leandro Balby Marinho 19 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Contando Permutac¸o˜es
Teorema 1
Se n e´ um inteiro positivo e r um inteiro com 0 ≤ r ≤ n, enta˜o ha´
P(n, r) = n(n − 1)(n − 2) . . . (n − r + 1)
r permutac¸o˜es de r objetos entre n objetos distintos.
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´ exata-
mente 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 de r -elementos no conjunto.
Prof. Dr. Leandro Balby Marinho 19 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Contando Permutac¸o˜es
Corola´rio 2
Segueto Teorema 1 que se n e r sa˜o inteiros com 0 ≤ r ≤ n, enta˜o
P(n, r) =
n!
(n − r)!
Prof. Dr. Leandro Balby Marinho 20 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 10: Dez atletas competem um evento ol´ımpico. Sa˜o dadas medal-
has 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
Exemplo 11: Um representante de vendas deve visitar seis cidades difer-
entes. 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?
Soluc¸a˜o: Como a primeira cidade ja´ foi determinada, temos 5! = 120 rotas
poss´ıveis
Exerc´ıcio 9: Quantas permutac¸o˜es das letras ABCDEFGH conte´m a
cadeia FGH?
Prof. Dr. Leandro Balby Marinho 21 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 10: Dez atletas competem um evento ol´ımpico. Sa˜o dadas medal-
has 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
Exemplo 11: Um representante de vendas deve visitar seis cidades difer-
entes. 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?
Soluc¸a˜o: Como a primeira cidade ja´ foi determinada, temos 5! = 120 rotas
poss´ıveis
Exerc´ıcio 9: Quantas permutac¸o˜es das letras ABCDEFGH conte´m a
cadeia FGH?
Prof. Dr. Leandro Balby Marinho 21 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 10: Dez atletas competem um evento ol´ımpico. Sa˜o dadas medal-
has 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
Exemplo 11: Um representante de vendas deve visitar seis cidades difer-
entes. 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?
Soluc¸a˜o: Como a primeira cidade ja´ foi determinada, temos 5! = 120 rotas
poss´ıveis
Exerc´ıcio 9: Quantas permutac¸o˜es das letras ABCDEFGH conte´m a
cadeia FGH?
Prof. Dr. Leandro Balby Marinho 21 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 10: Dez atletas competem um evento ol´ımpico. Sa˜o dadas medal-
has 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
Exemplo 11: Um representante de vendas deve visitar seis cidades difer-
entes. 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?
Soluc¸a˜o: Como a primeira cidade ja´ foi determinada, temos 5! = 120 rotas
poss´ıveis
Exerc´ıcio 9: Quantas permutac¸o˜es das letras ABCDEFGH conte´m a
cadeia FGH?
Prof. Dr. Leandro Balby Marinho 21 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 10: Dez atletas competem um evento ol´ımpico. Sa˜o dadas medal-
has 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
Exemplo 11: Um representante de vendas deve visitar seis cidades difer-
entes. 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?
Soluc¸a˜o: Como a primeira cidade ja´ foi determinada, temos 5! = 120 rotas
poss´ıveis
Exerc´ıcio 9: Quantas permutac¸o˜es das letras ABCDEFGH conte´m a
cadeia FGH?
Prof. Dr. Leandro Balby Marinho 21 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Permutac¸o˜es com Repetic¸o˜es
Em alguns problemas, os n objetos podem ser usados quantas vezes quis-
ermos de forma que r pode ser maior que n.
Teorema 3
O nu´mero de permutac¸o˜es de r objetos entre n objetos distintos com
repetic¸a˜o e´ nr .
Prova: Pelo princ´ıpio da multiplicac¸a˜o, ha´ n formas de escolher um el-
emento 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 22 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 12: Quantas cadeias de tamanho r existem no alfabeto da l´ıngua
Portuguesa?
Soluc¸a˜o: Pelo Teorema 3, existem 26r cadeias de de tamanho r na l´ıngua
Portuguesa
Exerc´ıcio 10: Quantas formas ha´ de alocar treˆs tarefas para cinco alunos,
se cada aluno pode receber mais de uma tarefa?
Prof. Dr. Leandro Balby Marinho 23 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 12: Quantas cadeias de tamanho r existem no alfabeto da l´ıngua
Portuguesa?
Soluc¸a˜o: Pelo Teorema 3, existem 26r cadeias de de tamanho r na l´ıngua
Portuguesa
Exerc´ıcio 10: Quantas formas ha´ de alocar treˆs tarefas para cinco alunos,
se cada aluno pode receber mais de uma tarefa?
Prof. Dr. Leandro Balby Marinho 23 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 12: Quantas cadeias de tamanho r existem no alfabeto da l´ıngua
Portuguesa?
Soluc¸a˜o: Pelo Teorema 3, existem 26r cadeias de de tamanho r na l´ıngua
Portuguesa
Exerc´ıcio 10: Quantas formas ha´ de alocar treˆs tarefas para cinco alunos,
se cada aluno pode receber mais de uma tarefa?
Prof. Dr. Leandro Balby Marinho 23 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Roteiro
1. Princ´ıpios Fundamentais da Contagem
2. Princ´ıpio da Inclusa˜o/Exclusa˜o
3. Princ´ıpio da Casa dos Pombos
4. Permutac¸o˜es
5. Combinac¸a˜o
Prof. Dr. Leandro Balby Marinho 24 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Introduc¸a˜o
Uma combinac¸a˜o de elementos de um conjunto e´ uma selec¸a˜o na˜o
ordenada de elementos desse conjunto.
O nu´mero de combinac¸o˜es de r objetos distintos escolhidos entre n
objetos distintos e´ denotado por C (n, r) ou
(
n
r
)
.
Prof. Dr. Leandro Balby Marinho 24 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplo 13
Quantas combinac¸o˜es de dois elementos podemos obter do conjunto
P = {a, b, c , d}?
Soluc¸a˜o: C (4, 2) = 6, pois ha´ seis subconjuntos de dois elementos
em P, i.e.,
{a, b}, {a, c}, {a, d}, {b, c}, {b, d} e {c , d}
.
Note que P(4, 2) = C (4, 2)P(2, 2).
Prof. Dr. Leandro Balby Marinho 25 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Contando Combinac¸o˜es
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´
C (n, r) =
n!
r !(n − r)!
Prova: Pelo princ´ıpio da multiplicac¸a˜o, P(n, r) = C (n, r) · P(r , r).
Consequentemente,
C (n, r) =
P(n, r)
P(r , r)
=n!/(n − r)!
r !/(r − r)! =
n!
r !(n − r)!
Prof. Dr. Leandro Balby Marinho 26 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Contando Combinac¸o˜es
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´
C (n, r) =
n!
r !(n − r)!
Prova: Pelo princ´ıpio da multiplicac¸a˜o, P(n, r) = C (n, r) · P(r , r).
Consequentemente,
C (n, r) =
P(n, r)
P(r , r)
=
n!/(n − r)!
r !/(r − r)! =
n!
r !(n − r)!
Prof. Dr. Leandro Balby Marinho 26 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Contando Combinac¸o˜es
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´
C (n, r) =
n!
r !(n − r)!
Prova: Pelo princ´ıpio da multiplicac¸a˜o, P(n, r) = C (n, r) · P(r , r).
Consequentemente,
C (n, r) =
P(n, r)
P(r , r)
=
n!/(n − r)!
r !/(r − r)! =
n!
r !(n − r)!
Prof. Dr. Leandro Balby Marinho 26 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exerc´ıcio 11
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?
Prof. Dr. Leandro Balby Marinho 27 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinac¸a˜o com Repetic¸a˜o
Exemplo 14: 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 escol-
her as frutas.
4 mac¸a˜s 4 laranjas 4 peˆras
3 mac¸a˜s, 1 laranja 3 mac¸a˜s, 1 peˆra 3 laranjas, 1 mac¸a˜
3 laranjas, 1 peˆra 3 peˆras, 1 mac¸a˜ 3 peˆras, 1 laranja
2 mac¸a˜s, 2 laranjas 2 mac¸a˜s, 2 peˆras 2 laranjas, 2 peˆras
2 mac¸a˜s, 1 laranja, 1 peˆra 2 laranjas, 1 mac¸a˜, 1 peˆra 2 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 28 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinac¸a˜o com Repetic¸a˜o
Exemplo 14: 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 escol-
her as frutas.
4 mac¸a˜s 4 laranjas 4 peˆras
3 mac¸a˜s, 1 laranja 3 mac¸a˜s, 1 peˆra 3 laranjas, 1 mac¸a˜
3 laranjas, 1 peˆra 3 peˆras, 1 mac¸a˜ 3 peˆras, 1 laranja
2 mac¸a˜s, 2 laranjas 2 mac¸a˜s, 2 peˆras 2 laranjas, 2 peˆras
2 mac¸a˜s, 1 laranja, 1 peˆra 2 laranjas, 1 mac¸a˜, 1 peˆra 2 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 28 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinac¸a˜o com Repetic¸a˜o
Exemplo 14: 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 escol-
her as frutas.
4 mac¸a˜s 4 laranjas 4 peˆras
3 mac¸a˜s, 1 laranja 3 mac¸a˜s, 1 peˆra 3 laranjas, 1 mac¸a˜
3 laranjas, 1 peˆra 3 peˆras, 1 mac¸a˜ 3 peˆras, 1 laranja
2 mac¸a˜s, 2 laranjas 2 mac¸a˜s, 2 peˆras 2 laranjas, 2 peˆras
2 mac¸a˜s, 1 laranja, 1 peˆra 2 laranjas, 1 mac¸a˜, 1 peˆra 2 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 28 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinac¸a˜o com Repetic¸a˜o
Exemplo 15: 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.
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.
Prof. Dr. Leandro Balby Marinho 29 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinac¸a˜o com Repetic¸a˜o
Exemplo 15: 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.
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.
Prof. Dr. Leandro Balby Marinho 29 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplo 15 cont.
O problema corresponde ao nu´mero de formas de arranjar 6 barras e 5
asteriscos.
Nesse caso, C (11, 5) =
11!
5!6!
= 462
Prof. Dr. Leandro Balby Marinho 30 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplo 15 cont.
O problema corresponde ao nu´mero de formas de arranjar 6 barras e 5
asteriscos.
Nesse caso, C (11, 5) =
11!
5!6!
= 462
Prof. Dr. Leandro Balby Marinho 30 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinac¸a˜o com Repetic¸a˜o
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 represen-
tada 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 31 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Combinac¸a˜o com Repetic¸a˜o
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 represen-
tada 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 31 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 16: Suponha que uma chocolateria tem4 tipos diferentes de
chocolate. De quantas formas diferentes 6 chocolates podem ser
escolhidos? Assuma que a ordem da escolha na˜o importa.
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) =
9.8.7
3.2.1
= 84
Prof. Dr. Leandro Balby Marinho 32 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 16: 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.
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) =
9.8.7
3.2.1
= 84
Prof. Dr. Leandro Balby Marinho 32 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Exemplos
Exemplo 16: 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.
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) =
9.8.7
3.2.1
= 84
Prof. Dr. Leandro Balby Marinho 32 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Resumo
Tipo Repetic¸a˜o Fo´rmula
r -permutac¸o˜es Na˜o
n!
(n − r)!
r -combinac¸o˜es Na˜o
n!
r !(n − r)!
r -permutac¸o˜es Sim nr
r -combinac¸o˜es Sim
(n + r − 1)!
r !(n − 1)!
Prof. Dr. Leandro Balby Marinho 33 / 34 UFCG CEEI
Fundamentos Inclusa˜o/Exclusa˜o Princ´ıpio da Casa dos Pombos Permutac¸o˜es Combinac¸o˜es
Refereˆncias
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.
Prof. Dr. Leandro Balby Marinho 34 / 34 UFCG CEEI
	1. Princípios Fundamentais da Contagem
	2. Princípio da Inclusão/Exclusão
	3. Princípio da Casa dos Pombos
	4. Permutações
	5. Combinação