Instituto Federal de Educação, Ciência e
Tecnologia de São Paulo - IFSP
Campus de Caraguatatuba
Tecnólogo em Análise e Desenvolvimento de Sistemas
20 Semestre de 2013
Matemática Discreta 1 – MD 1
Prof. Lineu Mialaret
Aula 5: Combinatória (3)
Matemática Discreta 2
Aula 4 - 1/22
©Prof. Lineu Mialaret
Princípio das Casas de Pombos (1)
 Seja o seguinte problema:
 Quantas pessoas (no mínimo) têm que estar presentes em
uma sala para garantir que duas delas têm o último nome
(sobrenome) começando com a mesma letra?
 Ou este outro problema:
 Quantas vezes é preciso jogar (no mínimo) um dado de
modo a garantir que um mesmo valor apareça duas vezes?
Matemática Discreta 2
Aula 4 - 2/22
©Prof. Lineu Mialaret
Princípio das Casas de Pombos (2)
 O
Princípio das Casas de Pombos (Pigeonhole
Principle) surgiu a partir da seguinte idéia:
 Se mais de k pombos entram em k casas de pombos,
então pelo menos uma casa vai ter mais de um pombo.
 Pode ser aplicado a muitos problemas (cenários).
Matemática Discreta 2
Aula 4 - 3/22
©Prof. Lineu Mialaret
Princípio das Casas de Pombos (2)
 Princípio generalizado:
 Se mais de k itens são colocados em k caixas, então pelo
menos uma caixa contém mais de um item.
 Exemplos práticos de aplicação:
 Suponha que um departamento possui 13 professores.
Então dois dos professores nasceram no mesmo mês.
 Suponha que um saco de lavanderia contém meias
vermelhas, brancas e azuis. Então é necessário pegar
apenas quatro meias para se ter certeza de obter um par
com uma única cor.
Matemática Discreta 2
Aula 4 - 4/22
©Prof. Lineu Mialaret
Princípio das Casas de Pombos (2)
 Achar o menor número de elementos que devem ser
escolhidos em um conjunto S = {1,2,3,...,9} para se ter
certeza de que dois números somem 10.
 Os conjuntos de dois números que somam 10 são {1,9},
{2,8}, {3,7}, {4,6}, {5,5}. Logo qualquer escolha de seis
elementos de S garante que dois dos números somam
10.
Matemática Discreta 2
Aula 4 - 5/22
©Prof. Lineu Mialaret
Princípio das Casas de Pombos (1)
 Exercício 1 - Seja o seguinte problema:
 Quantas pessoas têm que estar presentes em uma sala
para garantir que duas delas têm o último nome
(sobrenome) começando com a mesma letra?
Matemática Discreta 2
Aula 4 - 6/22
©Prof. Lineu Mialaret
Princípio das Casas de Pombos (1)
 Exercício 1 - Seja o seguinte problema:
 Quantas pessoas têm que estar presentes em uma sala
para garantir que duas delas têm o último nome
(sobrenome) começando com a mesma letra?
 Resposta:
 O alfabeto tem 26 letras. Se a sala tiver 27 pessoas, então
existem 27 letras iniciais (itens) para se colocar em 26
caixas, de modo que uma caixa vai conter mais de uma
letra inicial do alfabeto.
Matemática Discreta 2
Aula 4 - 7/22
©Prof. Lineu Mialaret
Princípio das Casas de Pombos (1)
 Exercício 2 - Seja o seguinte problema:
 Quantas vezes é preciso jogar (no mínimo) um dado de
modo a garantir que um mesmo valor apareça duas vezes?
Matemática Discreta 2
Aula 4 - 8/22
©Prof. Lineu Mialaret
Princípio das Casas de Pombos (1)
 Exercício 2 - Seja o seguinte problema:
 Quantas vezes é preciso jogar (no mínimo) um dado de
modo a garantir que um mesmo valor apareça duas vezes?
 Resposta:
 Supondo que o resultado de 6 jogadas dos dados no
melhor cenário seja 1,2,3,4,5 e 6, para que um valor se
repita, é só jogar o dado novamente. Logo é necessário
jogar o dado 7 vezes.
Matemática Discreta 2
Aula 4 - 9/22
©Prof. Lineu Mialaret
Teorema Binomial (1)
 O binômio de Newton permite escrever na forma
canônica o polinômio correspondente à potência de um
binômio.
 O nome é dado em homenagem ao físico e matemático
Isaac Newton.
 A expressão para o quadrado de um binômio é bastante
conhecida:
 (a + b)2 = a2 + 2ab + b2
 Esse é o caso particular de se elevar ao quadrado um
binômio a uma potência inteira não negativa n.
 A fórmula genérica para (a + b)n envolve a combinação de
n elementos.
 Há um algoritmo simples para calcular os coeficientes
binomiais (obtidos na expansão do binômio).
Matemática Discreta 2
Aula 4 - 10/22
©Prof. Lineu Mialaret
Teorema Binomial (2)
 O Triângulo de Pascal leva o esse nome devido ao
matemático Blaise Pascal.
 A linha n do triângulo abaixo (n  0) consiste de todos os
valores de C(n,r), 0  r  n. O triângulo tem então o
seguinte formato:
Matemática Discreta 2
Aula 4 - 11/22
©Prof. Lineu Mialaret
Teorema Binomial (3)
 Calculando-se os valores das combinações, tem-se o
triângulo com os seguintes valores:
 Observando atentamente o triângulo, constata-se que
qualquer número que não esteja na borda pode ser
obtido somando-se os dois elementos diretamente acima
na linha anterior.
Matemática Discreta 2
Aula 4 - 12/22
©Prof. Lineu Mialaret
Teorema Binomial (4)
 A observação anterior implica que
 C(n,k) = C(n - 1,k - 1) + C(n - 1,k), para 1  k  n - 1.
 Esta equação é conhecida como Fórmula de Pascal.
Matemática Discreta 2
Aula 4 - 13/22
©Prof. Lineu Mialaret
Teorema Binomial (5)
 Pesquisa (vai cair na prova):
 Provar que
C(n,k) = C(n - 1,k - 1) + C(n - 1,k), para 1  k  n - 1.
(1)
(2)
 Dica: partir de (2) e chegar em (1).
Matemática Discreta 2
Aula 4 - 14/22
©Prof. Lineu Mialaret
Teorema Binomial (6)
 Demonstração Combinatória de
 C(n,k) = C(n - 1,k - 1) + C(n - 1,k), para 1  k  n - 1.
 Deseja-se calcular C(n,k), o número de maneiras de se
escolher k objetos entre n objetos. Tais escolhas podem
classificadas em duas categorias distintas: o objeto 1 é um
dos k objetos ou não.
 Se o objeto 1 for um dos k objetos, então os k - 1 objetos que
faltam têm que ser escolhidos entre os n - 1 objetos, retirandose o objeto 1, e existem C(n - 1,k - 1) escolhas possíveis.
 Se o objeto 1 não é um dos k objetos, então todos os k
objetos têm que ser escolhidos entre os outros n - 1 objetos e
existem C(n - 1,k) escolhas possíveis.
 O número total de escolhas é a soma das escolhas desses
dois casos disjuntos.
Matemática Discreta 2
Aula 4 - 15/22
©Prof. Lineu Mialaret
Teorema Binomial (7)
 Na expressão abaixo,
 (a + b)2 = a2 + 2ab + b2
 Os coeficientes da expansão 1, 2, e 1, representam a
segunda linha do Triângulo de Pascal.
 Calcular (a + b)3 e (a + b)4
 (a + b)3 = (a +b)(a2 + 2ab + b2)
 (a + b)4 = ?
Matemática Discreta 2
Aula 4 - 16/22
©Prof. Lineu Mialaret
Teorema Binomial (8)
 Uma análise dos coeficientes nas expansões anteriores
sugere um resultado geral, ou seja, que os coeficientes
na expansão (a + b)n são os elementos na linha n no
Triângulo de Pascal. Isso é formalizado no teorema
abaixo.
 Devido a seu uso no teorema binomial, a expressão
C(n, r) também é chamada de coeficiente binomial.
Matemática Discreta 2
Aula 4 - 17/22
©Prof. Lineu Mialaret
Teorema Binomial (9)
 Exemplo – Expandir (x -3)4
Matemática Discreta 2
Aula 4 - 18/22
©Prof. Lineu Mialaret
Teorema Binomial (10)
 Exercício: Expandir (x - 3)5
Matemática Discreta 2
Aula 4 - 19/22
©Prof. Lineu Mialaret
Teorema Binomial (11)
 Exercício: Expandir (x - 3)5
 Resposta:?
Matemática Discreta 2
Aula 4 - 20/22
©Prof. Lineu Mialaret
Teorema Binomial (12)
 Exercício: Expandir (x + y)6
Matemática Discreta 2
Aula 4 - 21/22
©Prof. Lineu Mialaret
Teorema Binomial (13)
 Exercício: Expandir (x + y)6
 Resposta:?
Matemática Discreta 2
Aula 4 - 22/22
©Prof. Lineu Mialaret