Aula_010_Permutações com Repetição

Prévia do material em texto

10.1Módulo: Aplicações dos princípios aditivo e multiplicativo
Introdução
Conteúdo:
Permutação com repetição
Número de permutações com repetição
 Aula 10 : Permutações com Repetição 
Ilustração:
uma possibilidade_______
João
_______
Rita
_______
Luiza
_______
Gabriel
_______
Felipe
• A troca de lapiseiras entre João e Luiza modifica a distribuição.
• A troca de lapiseiras entre João e Rita não modifica a distribuição.
Observações:
Introdução:
Exemplo 1:
Comprei 5 lapiseiras, 2 brancas, 1 azul, 1 preta e 1 verde,
para dar de presente a meus amigos João, Rita, Luiza,
Gabriel e Felipe. De quantas maneiras diferentes eu
posso distribuí-las?
10.2Permutações com repetição
10.3Permutações com repetição: Introdução
Exemplo 1 (continuação):
Raciocínio (baseado em permutações simples)
Resolução:
Etapa 1: Calculamos o número de distribuições 
considerando que marcamos cada lapiseira
branca para diferenciá-las.
Ilustração:
João Rita Luiza Gabriel Felipe
Número de distribuições marcadas: P5 = 5!
Etapa 2: Reduzimos as distribuições repetidas
P2 = 2 1 distribuição
correspondem
correspondem
P5 total de distribuições=
P5 ___
P2
5! ___
2
(etapa 1)
Ilustração:
1 distribuição
João Rita Luiza Gabriel Felipe
10.4Permutações com repetição: Introdução
Exemplo 1 (continuação):
Atenção, estamos considerando distribuições iguais como sendo diferentes! 
Resposta: Posso distribuir as lapiseiras para meus 
 amigos de modos diferentes.= 605! ___
2
Resolução:
Raciocínio 1 (baseado em permutações simples)
Raciocínio 2 (baseado em combinações simples)
133191 é uma possibilidade
Ilustração:
Exemplo 2:
Quantos números distintos de 6 algarismos podem ser
formados usando-se o dígito 1 três vezes, o dígito 3 duas 
vezes e o dígito 9 uma vez? 
10.5Permutações com repetição: Introdução
Exemplo 2 (continuação):
Etapa 1: Consideramos como sendo diferentes os 
 números repetidos (os marcamos).
 Calculamos o número total de ordenamentos.
Raciocínio 1 (baseado em permutações simples)
Número de ordenamentos diferentes de algarismos
marcados: P6 = 6!
Atenção, 
 estamos considerando números iguais como sendo diferentes!
1 3 3 1 9 1
1 3 3 1 9 1
Ilustração:
10.6Permutações com repetição: Introdução
Exemplo 2 (continuação raciocínio 1):
Etapa 2: Reduzimos os casos iguais considerados 
 como diferentes na etapa 1.
são iguais a 
133191
1 3 3 1 9 1
1 3 3 1 9 1
1 3 3 1 9 1
1 3 3 1 9 1
1 3 3 1 9 1
1 3 3 1 9 1
1 3 3 1 9 11 3 3 1 9 1
1 3 3 1 9 1
Ilustração:
P2 P1P3
×
P.M.
×
P.M.
10.7Permutações com repetição: Introdução
total de números distintos
correspondem
P6 permutações simples =
P6 ____________
P3 × P2 × P1
6! _______
3! 2! 1!
(etapa1)
correspondem
P3 × P2 × P1 permutações simples 1 número
Observação: dois números são diferentes quando 
as posições dos algarismos diferentes estão trocados 
( 131139 é diferente de 311139 ).
Reformulação do problema:
De quantas maneiras diferentes podemos colocar 
três 1, dois 3 e um 9 em 6 posições?
10.8Permutações com repetição: Introdução
Exemplo 2 (continuação):
Raciocínio 2 (baseado em combinações simples)
N1: número de modos de colocar três 1 em 6 posições 
N1 = C(6, 3)
Ilustração:
___ ___ ___ ___ ___ ___1 1 1
___ ___ ___ ___ ___ ___1 1 1
10.9Permutações com repetição: Introdução
Exemplo 2 (continuação raciocínio 2):
Etapa 1: Consideramos somente as possíveis posições 
dos três 1. Calculamos todos os modos de 
colocar os três 1 em 6 posições.
Exemplo 2 (continuação raciocínio 2):
Etapa 2: Fixada uma posição para os três 1, 
 consideramos as possíveis posições dos 
 dois 3 nos lugares restantes.
3 3
3 3
9
9___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___
1 1 1
1 1 1Ilustração:
N3: número de modos de colocar o 9 em 1 lugar = C(1, 1)
N2: número de modos de colocar os dois 3 em 3 lugares 
N2 = C(3, 2)
10.10Permutações com repetição: Introdução
Etapa 3: Fixada uma posição para os três 1 e os dois 3,
consideramos as possíveis posições para o 9.
10.11Permutações com repetição: Introdução
Etapa 2
N2 = C(3, 2)
___ ___ ___ ___ ___ ___1 1 13 3
1 1 1
Etapa 3
___ ___ ___ ___ ___ ___1 1 13 3 9
N3 = C(1, 1)
Resposta: O número total de possibilidades são
 N1 × N2 × N3 = _______
3! 2! 1!
 6!
= = _______
P3P2P1
P6. . _____
3! 3!
 6! _____
2! 1!
 3! _____
1! 0!
 1!
×
P.M.
×
P.M.
Observação: 
 3 + 2 + 1 = 6
Exemplo 2 (continuação raciocínio 2):
Resumindo
Etapa 1
N1 = C(6, 3)
___ ___ ___ ___ ___ ___
p1 p2 p3 p4 p5 p6
Características:
Os elementos considerados não são necessariamente
diferentes.
Os elementos iguais são indistinguíveis
Cada troca de posição (de ordem) dos elementos 
distinguíveis corresponde a uma possibilidade
Na obtenção do número de possibilidades aplica-se
os princípios aditivo e multiplicativo.
(não são consideradas as permutações dos elementos iguais).
10.12Permutações com repetição: Introdução
Permutação com repetição:
Definição
Entre n objetos dados tem-se n1 elementos iguais a a1,
n2 elementos iguais a a2, ... , nr elementos iguais a ar,
sendo a1, a2, ... , ar diferentes e n = n1 + n2 + ... + nr.
Uma permutação com repetição destes n objetos é uma
ordenação desses elementos onde não são consideradas
as permutações entre os elementos iguais.
Exemplo 2: a1 = 1 , n1= 3 , a2= 3 , n2= 2 , a3= 9 , n3= 1 (r = 3)
 n = n1 + n2 + n3 = 3 + 2 + 1 = 6,
Ilustração
permutações com repetição diferentes: 131139 e 311139
10.13Permutações com repetição
Número de permutações com repetição:
Problema
Dados n objetos tais que n1 elementos são iguais a a1,
 n2 elementos são iguais a a2 , ... , nr elementos são 
 iguais a ar e n = n1 + n2 + ... + nr,
encontrar o número de permutações com repetição.
10.14Permutações com repetição
Propriedade
O número de permutações com repetição de n elementos
sendo n1 iguais a a1, n2 iguais a a2, ... , nr iguais a ar e
n = n1 + n2 + ... + nr, é dado por: P
n1,n2, ... , nr
n = 
____________
n1! n2! ... nr!
n!
Número de permutações com repetição:
Outra notação: 
 PR (n; n1, ... , nr) 
Ilustração
exemplo 2: P
3, 2, 1
6 = 
________
3! 2! 1!
6!
Observação: se n = r e n1 = n2 = = nr = 1 
 então P
n1, ... , nr
n = P
1, ... , 1
n = Pn
...
10.15Permutações com repetição
Exemplo 3:
Um time de futebol jogou 15 partidas em um campeonato. 
Venceu 7 jogos, perdeu 5 e empatou 3. De quantos modos 
isto pode ter acontecido?
N = P
7, 5, 3
15 = = 360360
________
7! 5! 3!
15!
 O número de modos em que o time venceu, 
 perdeu e empatou é N = 360360.
Resposta:
n1 = 7
n2 = 5
n3 = 3
N: total das possíveis sequências de jogos vencidos,
 perdidos e empatados.
Resolução: n=15, a1 = jogo vencido, 
a2 = jogo perdido, 
a3 = jogo empatado, 
10.16Permutações com repetição: Número de permutações
10.17Permutações com repetição: Número de permutações
Exemplo 4:
Ana e Rosa moram em vértices opostos de um retângulo.
Ana precisa atravessar 3 avenidas e 4 ruas para chegar à
casa de Rosa. Quantos caminhos diferentes unemas
casas de Ana e de Rosa?
R1 R2 R3 R4
A1
A2
A3
Ana
Rosa
Exemplo 4 (continuação):
1 : atravessa 1 avenida (A1, A2 ou A3) 
0 : atravessa 1 rua (R1, R2, R3 ou R4) 
0 1 0 1 0 0 1
1 1 0 0 1 0 0
Cada caminho, a partir da casa de Ana até a de Rosa, pode ser 
representado por uma sequência de 0 e de 1 com o seguinte significado:
Observação:
10.18Permutações com repetição: Número de permutações
Ilustração:
A
R
R1 R2 R3 R4
A1
A2
A3
Exemplo 4 (continuação):
Reformulação do problema:
Quantas sequências diferentes podem ser formados com 
quatro 0 e três 1 ?
Resposta do problema:
As casas de Ana e Rosa estão unidas por 35 caminhos diferentes.
Resposta (problema reformulado):
O número de sequências diferentes é P
4, 3
7 = = 35.
_____
4! 3!
7!
Resolução:
Cada sequência corresponde a uma permutação com repetição.
n1 = 4 (a1 = 0) , n2 = 3 (a2 = 1) , n = 7 
10.19Permutações com repetição: Número de permutações
Exemplo 5:
Quantos são os anagramas da palavra MAMBEMBE 
que começam com vogal?
Resolução:
___ ___ ___ ___ ___ ___ ___ ___
p1 p2 p3 p4 p5 p6 p7 p8
A
E
} 
} 
etapa 1
etapa 2
N = N1 + N2
N: número de anagramas que começam com vogal
N1: número de anagramas que começam com A
N2: número de anagramas que começam com E
10.20Permutações com repetição: Número de permutações
 
N1 = P
3, 2, 2
7 =
_______
3! 2! 2!
7!
N2 = P
3, 2, 1, 1
7 =
________
3! 2! 1! 1!
7!
Resposta: O número de anagramas de MAMBEMBE 
que começam com vogal são N = _____
3! 2!
7!
= 630.( 1__ 2
(
+ 1
7 letras: 3 M, 2 B, 2 E 
(MAMBEMBE)
Exemplo 5 (continuação):
Etapa 1:
___ ___ ___ ___ ___ ___ ___ ___A
Etapa 2:
___ ___ ___ ___ ___ ___ ___ ___E
7 letras: 3 M, 2 B, 1 E, 1 A 
10.21Permutações com repetição: Número de permutações
Exemplo 6:
Quantos são os anagramas da palavra MAMBEMBE 
que não possuem duas ou três letras M juntas?
10.22Permutações com repetição: Número de permutações
MAMBEMBE, AMBMEMBE são possíveis anagramas
AMMBEMBE, AMMMBEBE não são anagramas 
 possíveis para o problema 
Ilustração:
10.23
Resolução:
N: número de anagramas que não possuem duas ou 
 três letras M juntas.
Permutações com repetição: Número de permutações
Exemplo 6 (continuação):
Etapa 1: Consideramos as letras de MAMBEMBE 
diferentes de M e calculamos o número de 
ordenamentos.
Conclusão 1: O número de ordens diferente de 
 A, B, E, B e E é P
2, 2, 1
5 .
• Observação: cada ordem das letras A (1 vez), B (2 vezes)
 e E (2 vezes) é 1 permutação com repetição: 
n1 = 1 (a1 = A) , n2 = 2 (a2 = B) , n3 = 2 (a3 = E) , n = 5
Exemplo 6 (continuação):
Etapa 2: Fixada uma permutação de A (1 vez), B (2 vezes)
 e E (2 vezes), calculamos as possibilidades de 
 intercalar nessa permutação cada M(3).
Ilustração: E A B B E___ ___ ___ ___ ___
Conclusão 2: Fixada uma permutação de A(1), B(2) e 
E(2), temos C(6, 3) maneiras de colocar as letras M(3).
. . . . . .
lugares possíveis para colocar M(3)
• Para cada permutação com repetição temos 6 lugares possíveis para 
 colocar a letra M
• Devemos escolher 3 lugares entre 6 para colocar as 3 letras M
Observações:
10.24Permutações com repetição: Número de permutações
Exemplo 6 (continuação):
Conclusão do problema:
(etapa 1)
( _______2! 2! 1!
5! × _______
3! 3!
6! (
10.25Permutações com repetição: Número de permutações
1 permutação com repetição de A, B e E
total de permutações com repetição P
2, 2, 1
5
 
gera
geram
C(6, 3) anagramas
 P
2, 2, 1
5 × C(6, 3) = N
(etapa 2)
(P. M.)
Resposta:
O número de anagramas da palavra MAMBEMBE
que não possuem duas ou três letras M juntas são 600.
Desafio:
Tente resolver o exemplo 6 usando o seguinte raciocínio:
Etapa 1: Calcule o número de todos os anagramas de 
MAMBEMBE (incluindo aqueles em que 
aparecem 2 ou 3 letras M juntas), N1.
Etapa 2: Calcule o número de anagramas onde 
aparecem exatamente duas M juntas, N2. 
Etapa 3: Calcule o número de anagramas onde 
aparecem exatamente três M juntas, N3. 
( MMMABEBE não é um anagrama desta etapa )
10.26Permutações com repetição: Número de permutações
Conclusão:
N = N1 − N2 − N3 (pelo princípio aditivo)
10.27Permutações com repetição
Resumo:
Sejam n objetos tais que n1 entre eles são iguais a a1,
n2 são iguais a a2, ... , nr são iguais a ar, sendo a1 ... ar
diferentes e n = n1 + n2 + ... + nr .
Permutação com repetição
Conceito:
Número de permutações com repetição
P
n1, ... , nr
n = 
__________
n1! ... nr!
n!
Propriedade:
(a1, a1, ... , a1, a2 ... a2 ... ar, ... ar ≠ a1 ... a1, a2 a1 a2 ... a2 ... ar ... ar)
n1 n2 nr n1 − 1 n2 − 1 nr
 importa a posição dos objetos diferentes.Característica: