Matematica Discreta Aula 3

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 A
8
5
.→ 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 =
)!58(
!8
−
67204.5.6.7.8
2.3
2.3.4.5.6.7.8
==
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:
)!(
!
,
pn
n
A pn
−
=
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,
)!(
!
,
pn
n
A pn
−
=
2105.6.7
!4
!4.5.6.7
)!37(
!7
3,7 ===
−
=A
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
61.2.3!
!0
3
)!33(
!3
3,3 ===
−
=A
Aula 3 - Análise Combinatória e Teorema Binomial
ARRANJO SIMPLES
Homens: arranjo de cinco homens tomado de 2 a 2.
20
!3
!3.4.5
)!25(
!5
2,5 ==
−
=A
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!
3,3A 2,5A
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:
61.2.3!
!0
3
)!33(
!3
3,3 ===
−
=A
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:
!
1
!
!0
!
)!(
!
, n
nn
nn
n
A nn ===
−
=
!nPn =
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:
241.2.3.4!44 ===P
Aula 3 - Análise Combinatória e Teorema Binomial
PERMUTAÇÃO SIMPLES
Exemplo: Quantos anagramas podem ser formados com a
palavra LIVRO:
5 letras
anagramas
P
120
1.2.3.4.5!55
=
==
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
481.2.3.4.2!4.2.2 4 ===P
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: 
!...!!!!
!...),,,,(
edcba
n
P edcban =
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 650.34
!2!4!4
!11)2,4,4(
11
=
=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 ELEMENTOS REPETIDOS
8 posições no total 
Repetições: 2 torres, 2 cavalos, 2 bispos 
5040
2.2.2
2.3.4.5.6.7.8
!2!2!2
!8)2,2,2(
8 ===P
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:






=
−
=
p
n
pnp
n
C pn
)(!
!
,
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
)!(!
!
,
pnp
n
C pn
−
=
)!59(!5
!9
5,9
−
=C
maneirasC 126
.1.2.3.4!5
!5.6.7.8.9
!4!5
!9
5,9 ===






=
5
9
5,9C
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.






p
n
)!(!
!
,
pnp
n
C pn
−
=
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:
Linha 0
Linha 1
Linha 2
Linha 3
Linha 4
Linha 5
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)
1
!04!0
!4
0
4
0,4 =
−
=





=C
4
!14!1
!4
1
4
1,4 =
−
=





=C
6
!24!2
!4
2
4
2,4 =
−
=





=C
4
!34!3
!4
3
4
3,4 =
−
=





=C
1
!44!4
!4
4
4
4,4 =
−
=





=C
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






0
5






1
5






2
5






3
5






4
5






5
5
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!






0
5






1
5






2
5






3
5






4
5






5
5
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






−
−
+




 −
=





1
11
p
n
p
n
p
n
45
2
90
1.2!8
!8.9.10
!2!8
!10
8
10
====





9
!8
!8.9
!1!8
!9
8
9
===





36
2
72
1.2!7
!7.8.9
!2!7
!9
7
9
====





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:
kkn
n
ok
n ba
k
n
ba ..)( −
=
∑ 





=+
Aula 3 - Análise Combinatória e Teorema Binomial
Teorema Binomial
Exemplo:
(a + b)5 = ?
• Aplicando a fórmula:
kkn
n
ok
n ba
k
n
ba ..)( −
=
∑ 





=+
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
kkn
n
ok
n ba
k
n
ba ..)( −
=
∑ 





=+
005 ..
0
5
ba −





115 ..
1
5
ba −





225 ..
2
5
ba −





335 ..
3
5
ba −





445 ..
4
5
ba −





555 ..
5
5
ba −





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 
=





+





+





+





+




 −−−−− 444334224114004 2.)3.(
4
4
2.)3.(
3
4
2.)3.(
2
4
2.)3.(
1
4
2.)3.(
0
4
xxxxx
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 
Aula 3 - Análise Combinatória e Teorema Binomial






0
4






1
4






2
4






3
4






4
4