Aula 06 - Arranjos e Permutações com Repetição de Elementos

Prévia do material em texto

1
 
 
 
Aula 6 
 
 
 
ARRANJOS E PERMUTAÇÕES COM REPETIÇÃO DE ELEMENTOS 
 
 
 
Objetivos 
Identificar um arranjo ou permutação com repetição de elementos. 
Calcular o número de arranjos ou permutações com repetição de elementos. 
 
 
 
Exemplo 1 
 
 Quantos anagramas distintos tem a palavra ARCADA? 
 
 Observemos, inicialmente, que na palavra ARCADA a letra A é repetida 3 vezes. 
 
 Se escrevêssemos A1RCA2DA3 e considerássemos todos os elementos distintos 
teríamos 6! = 720 anagramas. Mas, por exemplo, os 6 “anagramas” 
 
RCA1A2DA3 RCA1A3DA2 RCA2A3DA1 RCA2A1DA3 RCA3A1DA2 RCA3A2DA1 
 
correspondem a um único anagrama da palavra ARCADA. Cada anagrama da palavra 
dada foi anteriormente contado 6 vezes, o que corresponde à permutação simples das 
“letras” A1, A2 e A3. Portanto, o número de anagramas da palavra ARCADA é menor que 
720. 
 
 Calculemos, então, o número de permutações distintas da palavra ARCADA. 
_ _ _ _ _ _ 
 
1ª etapa – escolher 3 dos 6 espaços para colocar a letra A repetida 3 vezes. Isto pode ser 
feito de C(6, 3) = 20 maneiras distintas, pois a ordem em que colocaremos a mesma letra 
3 vezes não é importante. 
 
2ª etapa – escolher dos 3 espaços restantes, um para colocar a letra R. Isto pode ser feito 
de C(3, 1) = 3 maneiras distintas. 
 
3ª etapa – escolher dos 2 espaços restantes, um para colocar a letra C. Isto pode ser feito 
de C(2, 1) = 2 maneiras distintas. 
 
4ª etapa – colocar a letra D no anagrama. Isto pode ser feito de C(1, 1) = 1 modo. 
 
 Pelo princípio multiplicativo encontramos 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 2
 
 
 
C(6,3) . C(3,1) . C(2,1) . C(1,1) = =−−−− !1.)!11(
!1.
!1.)!12(
!2.
!1.)!13(
!3.
!3.)!36(
!6 
!1.!0
!1.
!1.!1
!2.
!1.!2
!3.
!3.!3
!6 = 
!1.!1!.1.!3
!6 = 120 anagramas distintos. 
 
 
Exemplo 2 
 
 Quantos são os anagramas da palavra ADVOGADA? 
 
 Essa palavra tem a letra A repetida 3 vezes e a letra D duas vezes; as demais letras 
aparecem uma única vez. Usemos o mesmo raciocínio do exemplo 1. 
 
1ª etapa – escolher 3 lugares no anagrama para colocar a letra A. Isto pode ser feito de 
C(8, 3) = 56 maneiras distintas. 
 
2ª etapa – escolher 2, dos 5 espaços restantes, para colocar a letra D. Isto pode ser feito 
de C(5, 2) = 10 maneiras distintas. 
 
3ª etapa – escolher um espaço dos 3 restantes para colocar a letra V. Isto pode ser feito 
de C(3, 1) = 3 maneiras distintas. 
 
4ª etapa – escolher, dos 2 espaços restantes, um para colocar a letra O. Isto pode ser 
feito de C(2, 1) = 2 maneiras distintas. 
 
5ª etapa – colocar a letra G. Isto pode ser feito de C(1, 1) = 1 maneira. 
 
 Pelo princípio multiplicativo temos 
 
C(8,3).C(5,2).C(3,1).C(2,1).C(1,1) = 
!1)!.11(
!1.
!1)!.12(
!2.
!1)!.13(
!3.
!2)!.25(
!5.
!3)!.38(
!8
−−−−− = 
 
= 
!1!.0
!1.
!1!.1
!2.
!1!.2
!3.
!2!.3
!5.
!3!.5
!8 = 
!1!.1!.1!.2!.3
!8 = 3360 
 
 Observemos, que em produtos acima, o primeiro fator do denominador das frações 
pode ser simplificado com o numerador da fração seguinte. 
 
 
 
 No caso geral, suponhamos que temos n elementos para permutar, sendo n1 
elementos iguais ao elemento e1, n2 elementos iguais a e2, ... , nk elementos iguais a 
ek, com n1 + n2 + ... + nk = n. 
 
Etapa 1 – escolher n1 lugares para colocar o elemento e1. Isto pode ser feito de C(n, n1) 
maneiras. 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 3
 
 
Etapa 2 – escolher n2 lugares para colocar o elemento e2 nos n-n1 lugares restantes. Isto 
pode ser feito de C(n-n1, n2) maneiras. 
 
Etapa 3 – escolher n3 lugares para colocar o elemento e3, nos n-n1-n2 lugares. Isto pode 
ser feito de C(n-n1-n2, n3) maneiras. 
 
E assim por diante até a 
Etapa k – escolher nk lugares para colocar o elemento ek. Isto pode ser feito de 
C(n-n1-n2- ... – nk - 1, nk) maneiras. 
 
 Pelo princípio multiplicativo, o número de permutações distintas dos n elementos é 
igual a 
 
C(n, n1). C(n-n1, n2). C(n-n1-n2, n3). ... . C(n-n1-n2- ... – nk-1, nk) = 
 
= 
!)!....(
)!...(
....
!)!.(
)!(
.
!)!.(
)!(
.
!)!.(
!
1
11
3321
21
221
1
11 kk
k
nnnn
nnn
nnnnn
nnn
nnnn
nn
nnn
n
−−−
−−−
−−−
−−
−−
−
−
− = 
 
= 
!.....!.!
!
21 knnn
n 
 
 Denotemos por P knnnn ,...,, 21 o número de permutações distintas dos n elementos. 
 
P knnnn ,...,, 21 = !.....!.!
!
21 knnn
n 
 
 Observe que a permutação simples é um caso particular, pois temos 
n1 =n2 = ... = nk = 1. 
 
 
Exemplo 3 
 
(UFRJ) Uma partícula desloca-se sobre uma reta, percorrendo 1 cm para 
esquerda ou para direita a cada movimento. Calcule de quantas maneiras diferentes 
a partícula pode realizar uma seqüência de 10 movimentos terminando na posição 
de partida. 
 
Representemos por D um movimento para a direita e E um movimento para a 
esquerda. 
 
Observemos que uma seqüência de 10 movimentos terminando na posição de 
partida corresponde a uma permutação de 5 letras D e 5 letras E, isto é, a quantidade de 
movimentos para a direita ou para a esquerda são iguais. São exemplos de seqüências: 
DEDEDEDEDE e DDDEEDEEED. 
 
Temos então, 
!5!.5
!105,5
10 =P = 252 seqüências distintas. 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 4
 
 
Exemplo 4 
 
 Observe a figura abaixo. Se eu quiser colorir 8 dos 18 retângulos sendo 2 
com a cor azul, 3 com a cor amarela e 3 com a cor verde, de quantas maneiras 
diferentes essa pintura pode ser feita? 
 
 
 
 
 
 
 
 
 
 
 
 
 Pelo enunciado do exercício, a ordem em que os retângulos serão pintados não é 
importante. O que interessa é a pintura final. 
 
1ª solução 
Podemos entender como sendo uma permutação com elementos repetidos (azul, 
amarelo, verde e “branco”), em que 2 retângulos serão pintados com a cor azul, 3 com a 
cor amarela, 3 com a cor verde e os 10 restantes ficarão “brancos”. Logo, temos 
 
 P 10,3,3,218 = !10.!3.!3.!2
!18 = 24504480 maneiras distintas de colorir a figura. 
 
 
2ª solução 
 1ª etapa – escolher os 8 retângulos que serão pintados. Isto pode ser feito de 
C(18,8) = 43758 maneiras diferentes. 
 
 2ª etapa – pintar um grupo de 8 retângulos. 
 A cor azul será repetida 2 vezes, a amarela 3 vezes e a verde 3. Trata-se de uma 
permutação com elementos repetidos. Isto pode ser feito de 2,3,38P = 
8!
2!.3!.3!
 = 560 
maneiras. 
 
 Pelo princípio multiplicativo, temos 43758 . 560 = 24504480 maneiras de pintar 
8 retângulos quaisquer. 
 
 
Exemplo 5 
 
 O botão de um cofre tem os números 01, 02, ... , 50, sendo o seu segredo uma 
seqüência de 3 números, não necessariamente diferentes. Quantos são os 
possíveis segredos deste cofre? 
 
Etapa 1 – escolher o primeiro número. Isto pode ser feito de 50 maneiras. 
Etapa 2 – escolher o segundo número. Isto pode ser feito de 50 maneiras. 
Etapa 3 – escolher o terceiro número. Isto pode ser feito de 50 maneiras. 
 
 Pelo princípio multiplicativo, temos 50 . 50 . 50 = 503 segredos possíveis. 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 5
 
 
 Cada seqüência de 3 números, não necessariamente diferentes, é chamada de 
arranjo com repetição de elementos. Observemos que neste caso a ordem dos números 
é importante. 
 
 
Exemplo 6 
 
 A senha de uma conta corrente do Banco X é formada por uma seqüência de 4 
algarismos de livre escolha do cliente e três letras distintas que o banco fornece 
junto com a primeira tentativa de uso da conta corrente. Quantas senhas podem 
ser formadas? 
 
 A senha é formada por uma seqüência de 4 algarismos e 3 letras. 
 
1ª etapa - escolher a seqüência de 4 algarismos. Como a escolha dos algarismosé livre, 
há 10 possibilidades de escolha para cada um deles. Pelo princípio multiplicativo temos 
10.10.10.10 = 10000 seqüências de 4 algarismos. 
 
2ª etapa – escolher uma seqüência de 3 letras distintas dentre as 26 possíveis. Como a 
ordem é importante e as letras não se repetem, temos para a escolha da primeira letra 26 
possibilidades, para a segunda 25 e para a terceira 24 possibilidades. Pelo princípio 
multiplicativo há 26.25.24 = 15600 maneiras distintas de o banco enviar uma 
complementação da senha para o cliente. 
 
 Pelo princípio multiplicativo, há 104.26.25.24 = 156000000 senhas possíveis. 
 
 Compare a 1ª e a 2ª etapa do exemplo 6. Em ambas as etapas é importante a 
ordem na escolha dos elementos. Entretanto, na 1ª etapa é permitido a repetição dos 
elementos enquanto que na segunda não. Na primeira etapa temos o caso de um arranjo 
com repetição de elementos e na segunda etapa, um arranjo simples. 
 
 
 
Exercícios propostos 
 
1 – Dez moedas são colocadas sobre um tabuleiro uma ao lado da outra. De quantos 
modos diferentes podemos obter 3 caras e 7 coroas voltadas para cima? R.: 120 
 
2 -(UFF) Percorrendo-se uma unidade de comprimento por vez, em movimentos paralelos 
aos eixos coordenados e no sentido positivo dos mesmos, deseja-se caminhar da origem 
até o ponto (3,3), conforme o exemplificado na figura . Determine de quantas maneiras 
isto pode ser feito. R.: 20 
 
 
 
 
 
 
 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 6
 
 
3 – Com os algarismos 0, 1, ..., 9, quantos números de 5 algarismos podem ser formados 
sendo que exatamente 2 algarismos devem ser 8 e os demais algarismos diferentes de 8? 
R.: 6804 
 
4 - Quantos são os anagramas da palavra LANCHONETE que começam ou terminam 
por vogal? R.: 604800 
 
5 - Uma urna contém 20 bolas, sendo 9 azuis, 6 amarelas e 5 verdes. De quantas 
maneiras pode ser feita uma extração das 20 bolas da urna, uma a uma, sem reposição? 
R.: 77597520 
 
6 – Quantos são os anagramas da palavra PIRACICABA que não possuem 2 letras A 
juntas? R.: 70560 
 
7 -Um time de futebol jogou 9 partidas em um campeonato estadual tendo empatado em 2 
jogos, perdido em 3 e vencido em 4 jogos. De quantas maneiras distintas isto pode ter 
acontecido? R.: 1260 
 
8 – Quantos são os anagramas da palavra MATEMÁTICA que começam e terminam por 
vogal? R.: 33600 
 
9 – A figura abaixo representa 17 ruas que se cortam perpendicularmente, sendo 8 
verticais. Quantos caminhos mínimos uma pessoa pode percorrer para ir de A ao ponto B 
a) sem restrições; b) passando por C; c) sem passar por C; d) sem passar por C e D. 
 Um caminho mínimo é qualquer percurso partindo de A e caminhando sempre para 
cima ou para a direita até alcançar B. 
R.: a) 6435; b) 2450; c) 3985; d) 5035 
 
 
 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva