Aula 03 Matemática Computacional

Prévia do material em texto

*
*
MATEMÁTICA DISCRETA – AULA 3
PROFESSORA HELGA BODSTEIN, D.Sc. 
Aula 3
Análise Combinatória e 
Teorema Binomial
*
*
Conteúdo
·Conceitos de Permutações, Arranjos e Combinações.
·Teorema Binomial utilizando os coeficientes binomiais.
·O Triângulo de Pascal como uma ferramenta adicional facilitadora da utilização do Teorema Binomial.
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Introdução
Análise combinatória
 PROBLEMAS DE CONTAGEM
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Princípio Fundamental da Contagem 
Exemplo: Um número de telefone é uma seqüência de 8 dígitos, mas o primeiro dígito deve ser diferente de 0 ou 1. Quantos números de telefone distintos existem?
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Princípio Fundamental da Contagem 
Para cada dígito temos a possibilidade de 10 números, com exceção do 1º, onde só poderão existir 8 números:
	X X X X – X X X X
	8.10.10.10 – 10.10.10.10
	Assim: 8. 10...10 = 8.107
 	 7 vezes
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Princípio Fundamental da Contagem
Se um determinado evento ocorre em várias etapas sucessivas e independentes, onde:
P1 é o número de possibilidades de ocorrer a 1ª etapa, 
P2 o número de possibilidades de ocorrer a 2ª etapa,
 P3 o número de possibilidades de ocorrer a 3ª etapa,
 Pn o número de possibilidades de ocorrer a n-ésima etapa
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Princípio Fundamental da Contagem 
O número total de possibilidades de ocorrer esse evento é dado por 
P = P1 . P2 .P3 . … . Pn
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
 Dado um conjunto com n elementos distintos, chama-se arranjo dos n elementos, tomados p a p, a qualquer seqüência ordenada de p elementos distintos, escolhidos entre os n existentes. 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Temos um Arranjo quando os agrupamentos conseguidos ficam diferentes ao se inverter a posição dos seus elementos.  
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Exemplo: Se, por exemplo, de um grupo de oito (8) pessoas, devemos dispor cinco (5) delas em fila. De quantos modos podemos realizar tal processo?
____ ____ ____ ____ ____
 8 x 7 x 6 x 5 x 4
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Obteremos 8 x 7 x 6 x 5 x 4 = 6720 possibilidades de filas com cinco pessoas
		____ ____ ____ ____ ____ = 6720
 		 8 x 7 x 6 x 5 x 4
Representação: A8,5 ou A85.→ Arranjo 8 elementos tomados 5 a 5. 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Podemos fazer o cálculo do arranjo utilizando os conceitos de fatoração:
A8,5= 8 x 7 x 6 x 5 x 4 = 
	A8,5 = 		
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
De maneira geral, temos que um arranjo de n elementos tomados de K a K é igual a:
	
 		
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Exemplo: Quantos números de três dígitos distintos escolhidos entre 1, 2, 3, 4, 5, 6 e 7, podemos formar?
	
 		
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Isto significa que temos um arranjo de 
7 elementos tomados de 3 a 3.
Assim,
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Exemplo: Um grupo de pessoas é formado por
cinco homens e três mulheres. Deseja-se 
formar filas com 5 dessas pessoas de 
modo que as três mulheres ocupem sempre 
		as três primeiras posições. Assim, de todas as 			filas possíveis, quantas obedecem 
				essa restrição?
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Mulheres: arranjo de três mulheres tomado de 3 a 3.
OBS: 0! = 1
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Homens: arranjo de cinco homens tomado de 2 a 2.
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
				
 Possibilidades de		 Possibilidades de 
arranjos para as mulheres arranjos para os homens
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Resposta:
= 6 x 20 = 120 filas possíveis!
				
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Permutações simples é uma técnica combinatória utilizada quando desejamos contar as possibilidades de formação de uma fila ou seqüência em que não há repetição de elementos e todos esses elementos são utilizados no problema.
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Exemplo: com os algarismos 1, 2 e 3, quantos números de três algarismos distintos (isto é, sem repetição) podemos formar?			__1__ __2__ __3__ 
	__1__ __3__ __2__ 
	__2__ __1__ __3__ 
	__2__ __3__ __1__ 
	__3__ __1__ __2__ 
	__3__ __2__ __1__ 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Como os números não podem se repetir:
	____ ____ ____	3x2x1 = 6
	 3 X 2 X 1
 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Podemos entender a permutação simples como sendo um caso do arranjo, onde n=p:
 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Generalizando:
Então, a permutação simples pode ser representada pela equação:
 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Outro exemplo de contagem no qual lançamos mão da ferramenta permutação simples é a contagem do número de anagramas que podem ser formados com alguma palavra.
	Anagrama é um processo de troca de ordem das letras de uma palavra com o intuito de formar uma nova palavra (esta palavra formada pode ter sentido ou não). 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Exemplo:
	AMOR
		ROMA
			ORAM
				MARO
					etc. 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Como AMOR possui 4 letras:
	
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Exemplo: Quantos anagramas podem ser formados com a palavra LIVRO:
	 5 letras
			
	
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Exemplo: Quantos anagramas podem ser formados com a palavra LIVRO começando com vogal?
				___ ___ ___ ___ ___
	 O ou A 4 letras 
			
	
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO COM ELEMENTOS REPETIDOS
Se entre os n elementos de um conjunto, existem a elementos repetidos, b elementos repetidos, c elementos repetidos e assim sucessivamente, o número total de permutações que podemos formar é dado por:  
				
	
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO COM ELEMENTOS REPETIDOS
Exemplo: Quantos anagramas podemos formar com a palavra MISSISSIPPI? 
11 letras no total;
Repetições:
 4 letras I
 4 letras S
 2 letras P
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO COM ELEMENTOS REPETIDOS
Exemplo: Qual o número de maneiras diferentes de colocar em uma linha de um tabuleiro de xadrez (8 posições) as peças brancas (2 torres, 2 cavalos, 2 bispos, a rainha e o rei)?
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO COM ELEMENTOSREPETIDOS
8 posições no total 
Repetições: 2 torres, 2 cavalos, 2 bispos 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
COMBINAÇÃO SIMPLES
Combinação simples é uma ferramenta combinatória utilizada quando desejamos contar as possibilidades de formação de um subgrupo de elementos a partir de um grupo dado. 
	São as possibilidades de formação de um subconjunto formado a partir do conjunto dado.
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
COMBINAÇÃO SIMPLES
A ORDENAÇÃO DOS ELEMENTO, NESTE CASO, NÃO TEM IMPORTÂNCIA!
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
COMBINAÇÃO SIMPLES
Exemplo: Formar duplas com Pedro, João e Ana:
 Pedro e Ana = 	Pedro e João = 	 João e Ana = 
 Ana e Pedro	João e Pedro		 Ana e João
SERÃO FORMADOS APENAS 3 DUPLAS!
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
COMBINAÇÃO SIMPLES
A partir de um conjunto com n elementos devem-se formar um subconjunto com p elementos. A quantidade de subconjuntos é igual a:
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
COMBINAÇÃO SIMPLES
Exemplo: Dentre 9 Cd’s distintos que estão em oferta em uma loja, João deseja escolher 5 para comprar. De quantos modos diferentes João pode escolher os 5 Cd’s?
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
COMBINAÇÃO SIMPLES
CD1, CD2, CD3, CD4, CD5, CD6, CD7, CD8, CD9
Possibilidades:
CD1, CD2, CD3, CD4, CD5
	CD1, CD2, CD3, CD4, CD6
		CD1, CD2, CD3, CD4, CD7
			CD1, CD2, CD3, CD4, CD8
				CD1, CD2, CD3, CD4, CD9 etc...
 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
COMBINAÇÃO SIMPLES
					grupo de 9 CD’s
					em conjuntos de 5 CD’s
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Coeficientes Binomiais
	Dados dois números naturais, n e p, com n ≥ p, definimos o coeficiente binomial n sobre p, e indicamos por:
			 ou 
onde n é dito numerador e p chamado denominador.
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Triângulo de Pascal
O triângulo de Pascal é uma sequência de números binomiais, isto é, inteiros da forma C(n, p), dispostos em uma tabela em forma de triângulo, como na figura abaixo:
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Triângulo de Pascal
	Números binomiais em de tabela:
A “linha n” desta tabela será formada pelos inteiros C(n,p), onde p varia de 0 até n.
Linha 0, formada apenas pelo C (0,0) = 1.
Linha 4:
C (4,0) C (4,1) C (4,2) C (4,3) C (4 4)
 1 4 6 4 1
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Triângulo de Pascal
	Números binomiais em de tabela:
Linha 4: C (4,0) C (4,1) C (4,2) C (4,3) C (4 4)
- C (4,0)				- C (4,3)
C (4,1)				- C (4,4)
C (4,2) 
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Triângulo de Pascal
	Representando no Triângulo
C (0,0)
C (1,0) C (1,1)
C (2,0) C (2,1) C (2,2) 
C (3,0) C (3,1) C (3,2) C (3,3)
C (4,0) C (4,1) C (4,2) C (4,3) C (4,4)
C (5,0) C (5,1) C (5,2) C (5,3) C (5,4) C (5,5)
C (6,0) C (6,1) C (6,2) C (6,3) C (6,4) C (6,5) C (6,6)
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Triângulo de Pascal
	Resultado
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1 
1 6 15 20 15 6 1
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Triângulo de Pascal
	Propriedade: Em uma mesma linha, os coeficientes binomiais equidistantes dos extremos são iguais.
Aplicando a fórmula de combinação para a linha 5, por exemplo:
		 = = = = = =
		 1 5 10 10 5 1
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Triângulo de Pascal
		 = = = = = =
		 1 5 10 10 5 1
	Esses coeficientes binomiais são complementares e, portanto, iguais!
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
A partir da linha 1, a cada elemento x, com exceção do primeiro e último, é igual à soma dos dois elementos da cima de anterior:
1
1 1
1 2 1
	1 3 3 1	
1 4 6 4 1
1 5 10 10 5 1
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
	Essa propriedade é conhecida como Relação de Stifel e pode ser generalizada por:
					 , n≥p
Exemplo:
				 +
				 = 45
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Teorema Binomial
O teorema binomial fornece uma fórmula para a potência de um binômio, isto é, uma fórmula que permite calcular diretamente uma expressão do tipo (a + b)n, onde n é um inteiro positivo.
Para n = 0  (a + b)0 = 1
Para n = 1  (a + b)1 = a + b
Para n = 2  (a + b)2 = a2 + 2ab + b2
Para n = 3  (a + b)3 = a3 + 3 a3b + 3ab3 + b3
Para n = 4  (a + b)4 = ( a + b)3 (a + b) = a4 + 4a3 b + 6a2b2 + 4ab3 + b4
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Teorema Binomial
À medida que o expoente n aumenta, o desenvolvimento do binômio (a+b)n fica mais complexo, podendo ser obtido multiplicando-se o desenvolvimento anterior, (a+ b)n-1 , por (a + b), isto é:
 
(a + b)n = (a + b)n-1 . (a + b)
Exemplo:
Para n = 4  (a + b)4 = ( a + b)3 (a + b)
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Teorema Binomial
	Os coeficientes de (a+b)n são os inteiros que formam a linha n do triângulo de Pascal, que são os números binomiais C(n,p). 
(a + b)0 = 1
(a + b)1 = 1a + 1b
(a + b)2 = 1a2 + 2ab + 1b2
(a + b)3 = 1a3 + 3 a3b + 3ab3 + 1b3
(a + b)4 = ( a + b)3(a + b) = 1a4 + 4a3 b + 6a2b2 + 4ab3 + 1b4
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Teorema Binomial
(a + b)0 = 1						 	1
(a + b)1 = 1a + 1b				 1 1
(a + b)2 = 1a2 + 2ab + 1b2			 	 1 2 1
(a + b)3 = 1a3 + 3 a3b + 3ab3 + 1b3	 	 1 3 3 1
(a + b)4 = 1a4 + 4a3 b + 6a2b2 + 4ab3 + 1b4 1 4 6 4 1
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Teorema Binomial
Fórmula do teorema binomial:
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Teorema Binomial
Exemplo:
(a + b)5 = ?
Aplicando a fórmula:
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
1º termo: 		= 1.a5.1 = a5
2º termo:		= 5.a4.b 
3º termo:		= 10.a3.b2 
4º termo:		= 10.a2.b3 
5º termo:		= 5.a1.b4 
6º termo:		= 5.a0.b5 = 5b5
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Resultado: 
(a + b)5 = 
a5 + 5.a4.b + 10.a3.b2 + 10.a2.b3 + 5.a1.b4 + 5b5
*
*
Aula 3 - Análise Combinatória e Teorema Binomial
Exemplo: Desenvolver (3x+2)4 usando o teorema binomial.
(3x+2)4 = 
(3x)4 + 4.(3x)3.2 + 6.(3x)2.22 + 4.(3x)1.23 + 1.(3x)0.24 =
81x4 + 4.(27x)3.2 + 6.(9x)2.4 + 4.(3x)1.8 + 1.(3x)0.16 = 
81x4 + 216x3 + 216x2 + 96x + 16 
*
*
Exemplo: Desenvolver (x - 2)4 usando o teorema binomial.
 		(-b)k = bk se k é par 
  Note que:
		(-b)k = -bk se k é ímpar
(x - 2)4 = x4 - x3.2 + x2.22 - x.23 + x0.24 =
 
 (x - 2)4 = x4 - 8x3 + 24x2 - 32x + 16 
*