Aula_011_Arranjos com Repetição

Prévia do material em texto

Introdução
Conteúdo:
Arranjo com repetição
Número de arranjos com repetição
 Aula 11 : Arranjos com Repetição 
11.1Módulo: Aplicações dos princípios aditivo e multiplicativo
• Observemos que a pessoa pode entrar e sair pela 
 mesma porta.
Se o evento "entrar por 1 porta" pode ocorrer de 8 maneiras e o evento 
"sair por 1 porta" pode ocorrer de 8 maneiras então o par de eventos, 
primeiro "entrar" e depois "sair", podem ocorrer de 8 × 8 maneiras.
Interpretação do princípio multiplicativo aqui usada:
8 × 8 = 8
2
N =
P.M
Resolução:
Possibilidades
entrada saída
___ ___
11.2Arranjos com repetição
Introdução:
Exemplo 1:
Um prédio tem 8 portas. De quantas maneiras 1 pessoa
pode entrar e sair?
 
A = { P1, ... , P8 } , n(A) = |A| = 8
N = |A × A| = |A| × |A| = 82P.M.
11.3Arranjos com repetição: Introdução
(Pi, Pj) representa entrada Pi e saída Pj, para i, j = 1, ... ,8.
A × A = { (P1, P1), (P1, P2), ... ,(P1, P8), (P2, P1), ... ,(P8, P7), (P8, P8) }
todas as possibilidades de entrar e sair
Resposta:
 Uma pessoa pode entrar e sair de 64 maneiras diferentes.
Exemplo 1 (continuação):
Outra interpretação do princípio multiplicativo 
(baseada em conjuntos):
Exemplo 2:
Quantos números distintos de 3 algarismos podem se formar com os 
dígitos 3, 5, 7, 8 e 9?
A = { 3, 5, 7, 8, 9 }
A × A × A = { (u, v, w) | u ∈ A, v ∈ A, w ∈ A } = conjunto de possibilidades
( )
p1 p3 p2 
Resolução:
{ { {
p1 p2 p3
 representa ___ ___ ___ (posições dos dígitos
no número)
• Ilustração:
, , 3 5 553 5
11.4Arranjos com repetição: Introdução
N = |A × A × A| = |A| × |A| × |A| = |A|3 = 53P.M.
( pois A × A × A = (A × A) × A, logo |A × A × A| = | (A × A) × A| =
|A × A| × |A| = |A| × |A| × |A| )
P.M.
P.M.
Resposta: Podem se formar 5
3
 = 125 números diferentes
 com 3 algarismos escolhidos entre 3, 5, 7, 8 e 9.
11.5Arranjos com repetição: Introdução
• Ilustração:
35789359 (3, 5, 7, 8, 9, 3, 5, 9) ∈ A × A × ... × A 
associado
8
Resolução:
A = { 3, 5, 7, 8, 9 } , |A| = 5
conjunto de possibilidades: B = A × A × A × A × A × A × A × A
8
representamos um número de 8 algarismos por:
( , , , , , , , )
p1 p2 p3 p4 p5 p6 p7 p8
Exemplo 3:
Quantos números distintos de 8 algarismos podem se formar com os 
dígitos 3, 5, 7, 8 e 9?
 Pelo princípio multiplicativo podem se formar
 |B| = |A|8 = 58 números de 8 algarismos com 3, 5, 7, 8 e 9.Resposta: 
Características dos exemplos:
Os elementos considerados a1, a2, ..., an são diferentes
Cada escolha de r elementos ordenados, repetidos 
ou não, de a1, a2, ..., an corresponde a uma 
possibilidade
Na obtenção do número de possibilidades aplica-se
o princípio multiplicativo.
( A = { a1, a2, ... , an } )
( N = | B | )
( os r elementos ordenados correspondem a 1 r-upla do conjunto 
 B = A × ... × A ) 
r
11.6Arranjos com repetição: Introdução
Arranjo com repetição:
Definição
Dados n objetos distintos a1, a2, ..., an, um arranjo com 
repetição de n elementos tomados r a r é uma 
ordenação de r elementos escolhidos entre a1, a2, ..., an, 
que podem ser repetidos.
Observação: Pode ser r ≤ n ou r > n.
( não são consideradas permutações entre elementos iguais )
11.7Arranjos com repetição
Ilustração
• 357, 989, 998 são arranjos com repetição de 5 elementos, 3, 5, 7, 8 e 9, 
 tomados 3 a 3.
• 35789359 é um arranjo com repetição de 5 elementos, 3, 5, 7, 8 e 9 
 tomados 8 a 8.
11.8Arranjos com repetição
Resposta:
8
2
5
3
5
8
Observação
Número de escolhas dos exemplos anteriores:
Exemplo 1 Exemplo 2 Exemplo 3
2 entre 8
 portas
3 entre 5
algarismos
8 entre 5
algarismos
Número de arranjos com repetição:
Problema:
Dados n elementos distintos a1, a2, ... , an,
encontrar o número de arranjos com repetição
de n elementos tomados r a r
Propriedade:
O número de arranjos com repetição de n elementos 
distintos tomados r a r, denominado A
r
n , é dado por:
A
r
n = n
r
 
Observação:
A
r
n = |A × ... × A| onde A = { a1, a2, ... , an } 
r
11.9Arranjos com repetição
Ilustração:
Exemplo 1: A
2
8 = 8
2
 ( n = 8, r = 2 )
Exemplo 2: A
3
5 = 5
3
 ( n = 5, r = 3 ) 
Exemplo 3: A
8
5 = 5
8
 ( n = 5, r = 8 ) 
Outras notações:
AR
r
n , AR(n, r) 
11.10Arranjos com repetição: Número de arranjos
11.11
Exemplo 4:
As placas dos automóveis são formadas por três letras 
seguidas de quatro dígitos. Quantas placas podem
ser formadas? 
Arranjos com repetição: Número de arranjos
Resolução:
As letras do alfabeto são 26.
número de letras = 26
número de letras numa placa = 3
número de dígitos = 10
número de dígitos numa placa = 4
___ ___ ___ ___ ___ ___
posições
númerosletras
___
Característica:
• Sequências ordenadas de 3 letras e 
 4 números que podem ser repetidos.
___ ___ ___ ___ ___ ___
númerosletras
___
Exemplo 4 (continuação):
Tem-se 175.760.000 placas diferentes com 3 letras e 
4 números.
Resposta:
Número de possibilidades:
letras números
A
3
26 A
4
10 = 26
3
 × 10
4
 = 17576 × 10
4
 ×
P.M.
11.12Arranjos com repetição: Número de arranjos
Exemplo 5:
Quantos números naturais de 3 algarismos, na base 10,
existem?
Tem-se 900 números naturais de 3 algarismos.
Resposta:
11.13Arranjos com repetição: Número de arranjos
Resolução:
dígitos: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
os dígitos podem ser iguais ___ ___ ___0
Possibilidades:
9 × A
2
10 = 9 × 10
2
 = 900 
___ ___ ___0
11.14
Exemplo 6:
Quantos números naturais ímpares, m, existem entre
1000 e 9999 (1000 < m < 9999)?
Possibilidades: |U − B| = |U| − |B| = 9 × 102 × 5 − 1 
P.A.
Arranjos com repetição: Número de arranjos
Existem 4499 números ímpares entre 1000 e 9999.
Resposta:
Resolução:
• dígitos ímpares: 1, 3, 5, 7, 9
• dígitos na posição p
 
1 : 1, 2, 3, 4, 5, 6, 7, 8, 9
• dígitos na posição p4 : 1, 3, 5, 7, 9
• dígitos nas posições p2 e p3 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
p4p3p1 p2
___ ___ ___ ___9 ×
2
10 × 5|U| =
(excluímos 9999)
• U = { p ∈ | p ímpar, 1001 ≤ p ≤ 9999} , B = { 9999 }
N
 A
Preliminares para os próximos exemplos:
Representação decimal dos números
Observação: 
 Os números racionais admitem uma representação decimal com 
 finitos dígitos ou com infinitos dígitos periódicos. Os números 
 irracionais admitem uma representação decimal com infinitos 
 dígitos não periódicos.
11.15Arranjos com repetição: Número de arranjos
• = −0,333 ...3... : −[3 × 10−1 + 3 × 10−2 + ... + 3 × 10−k + ...] =__
3
1 
−
termo geral= −∑
k=1
3 × 10
−k∞
• pi = 3,1415926... : 
3 × 10
0
 + 1 × 10
−1
+ 4 × 10
−2 
+ 1 × 10
-3 
+ 5 × 10
−4
 + 9 × 10
−5
+ ...
Ilustração:
• 30,25 : 3 × 10
1
 + 0 × 10
0
 + 2 × 10
−1
 + 5 × 10
−2
Preliminares (continuação):
Representação binária
(30,25 = 1 × 2
4
 + 1 × 2
3
 + 1 × 2
2
 + 1 × 2
1
 + 0 × 2
0
 + 0 × 2
−1
 + 1 × 2
−2
)
= −[ 0 × 2
−1
 + 1 × 2
−2
 + 0 × 2
−3
 + 1 × 2
−4
 + ... + + 0 × 2
−(2n−1)
 
 + 1 × 2
−2n
 + ... ] )
__
3
1 
−(
11.16Arranjos com repetição: Número de arranjos
• Expressão binária de pi : 11,0010010000011...
 (binário não periódico)
Ilustração:• Expressão binária de 30,25 : 11110,01
__
3
1 
−
 (binário periódico)
• Expressão binária de : −0,010101 ... 01...
Preliminares (continuação):
decimal
30,25
−0,333 ... 3...
3,1415926...
11110,01
−0,0101 ... 01...
11,001001000...
Representação 
Número 
real
30,25
pi
__
3
1
−
10
2
 × 0,3025
−10
0
 × 0,33...33..
10
1
 × 0,31415
2
5
 × 0,1111001
−2
-1
 × 0,101010...10...
2
2
 × 0,110010010...
Característica de uma mantissa normalizada: o primeiro decimal 
(ou binário) é diferente de 0
potência
 de 10
 mantissa
normalizada
 decimal
potência
de 2
 mantissa
normalizada
 binária
11.17Arranjos com repetição: Número de arranjos
bináriadecimal em 
aritmética de 
ponto flutuante
binária em 
aritmética de 
ponto flutuante
Preliminares (continuação):
Representação dos números no computador
Os números são armazenados em um computador
(ou calculadora) em uma palavra
Sinal do número
ou da potência
0 : + , s : tamanho da potência
1 : − , t : tamanho da mantissa
11.18Arranjos com repetição: Número de arranjos
. . . .
1 2 s
. . . . . .
1 2 t
sinal do
número
sinal da
potência
(da base)
potência
 da base
mantissa normalizada
Preliminares (continuação):
Ilustração
Armazenamos os números −30,3125 e 0,0263671875 
numa máquina
(a) decimal com s = 2, t = 8
(b) binária com s = 4, t = 8
−30,3125 = −10
2
 × 0,3031250 2 3 0 3 1 2 5 0 001
(a) 
2 8
0,0263671875 = 10
-1
 × 0,26367187510 0 1 2 6 3 6 7 1 8 7 5
11.19Arranjos com repetição: Número de arranjos
(número armazenado exatamente)
(truncamento do número) 
Preliminares (continuação):
(b) binária com s = 4, t = 8
11.20Arranjos com repetição: Número de arranjos
(número armazenado exatamente)
(truncamento do número)
0 1 0 1 1 1 0 1 1 0 0 00 1
repr.
bin.
 0,0263671875 0,0000011011 = 
= 2
-5
 × 0,11011
101 0 1 0 1 1 1 1 1 0 0 1 0 −30,3125 −11110,0101 = 
 = −2
5
 × 0,111100101
( 5 101 )repr.
bin.
repr.
bin.
11.21Arranjos com repetição: Número de arranjos
Possibilidades 
para cada bit
0 1 0 1
1
0 10 1
n = 2 (0, 1) , r = 1 + 1 + 7 + 23 = 32{
 sinal
número
{
 sinal
potência
{
potência
{
mantissa
Exemplo 7:
Considere uma máquina binária (Intel 8087) que armazena os números 
em uma palavra com 24 bits para a mantissa, 7 bits para a potência de 2, 
1 bit para o sinal da potência e 1 bit para o sinal do número. Quantos 
números são armazenados exatamente nesta máquina?
Resposta: Nesta máquina são armazenados exatamente 
A
32
2 = 2
32
 = 4.294.967.296 números.
Resolução:
1 2 7 = s 1 2 23 24 = t3
. . . . . .
Resposta: Pelo princípio multiplicativo tem-se 2
2
 × 9 × 10
11
 números 
armazenados exatamente.
Resolução:
. . . .
1 2 9 10 = t1 2 = s
Possibilidades:
• sinais: A
2
2 = 2
2
• primeira posição da mantissa (normalizada) : 9
• posições restantes da mantissa e da potência : A
2 + 9
10 = A
11
10 = 10
11
Possibilidades para 
cada posição
1, 2, ...9
0, 1, ..., 90, 1, ..., 90 10 1
Observação: 2
2
 × 9 × 10
11
 > 2
2
 × 2
2
 × (2 × 4)
11
 = 2
37
 > 2
32
Exemplo 8:
Seja uma máquina decimal (HP-11C) cuja palavra tem s = 2 e t = 10. 
Quantos números são armazenados exatamente nesta máquina?
11.22Arranjos com repetição: Número de arranjos
11.23Arranjos com repetição
Resumo:
Conceito:
Importa os objetos considerados, as suas repetições 
e a posição dos elementos distinguíveis.
Características:
Considere n objetos distintos a1, a2, ..., an (A = {a1, ... , an}).
Arranjo com repetição de n objetos tomados r a r
Observação: r ≤ n ou r > n
(exemplos: a1a1a1a2a3 ... ar - 2 ≠ a1a2 ... ar - 2a1a1 ≠ a1a2a3 ... ar - 2ar - 1ar)
r r
Propriedade:
Número de arranjos com repetição de n objetos
tomados r a r : A
r
n = n
r
 = |A × ... × A|
r