Contagem Parte 2 - Ufla

Prévia do material em texto

Contagem
Renato Ramos da Silva
Universidade Federal de Lavras
renato.ramos@dcc.ufla.br
8 de janeiro de 2016
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 1 / 21
Overview
1 Permutações
2 Combinações
3 Repetições
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 2 / 21
Terminologia
Terminologia
Uma permutação de um conjunto de objetos distintos é um arranjo
ordenado desses objetos.
Interessamo-nos também por arranjos ordenados de alguns dos elementos
de alguns conjuntos.
Um arranjo ordenado de r elementos de um conjunto é chamado de
r-permutações.
Exemplo
Considere S ={1, 2, 3}. O arranjo ordenado 3,1,2 é uma permutação de S.
O arranjo ordenado (3,2) é uma 2-permutação de S.
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 3 / 21
Teorema
Teorema 1
Se n for um número inteiro positivo e r um inteiro com 1 ≤ r ≤ n, então há
P(n, r) = n(n − 1)(n − 2) . . . (n − r + 1)
r-permutações de um conjunto com n elementos distintos.
Teorema 2
Se n e r são números inteiros com 0 ≤ r ≤ n, então
P(n, r) = n!(n−r)!
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 4 / 21
Exemplo
Exemplo
Quantas maneiras há de selecionar o vencedor do primeiro, do segundo e
do terceiro lugar a partir de 100 pessoas diferentes que participam de um
concurso?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 5 / 21
Exemplo
Exemplo
Quantas maneiras há de selecionar o vencedor do primeiro, do segundo e
do terceiro lugar a partir de 100 pessoas diferentes que participam de um
concurso?
Resposta
P(100, 3) = 100× 99× 98 = 970.200
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 6 / 21
Exemplo
Exemplo
Quantos comitês diferentes de três estudantes podem ser formados a partir
de um grupo de quatro estudantes?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 7 / 21
Terminologia
Terminologia
Uma r-combinação de elementos de um conjunto é uma seleção não
ordenada de r-elementos a partir de um conjunto.
Então, uma r-combinação é simplesmente um subconjunto do conjunto
com r elementos.
Exemplo
Considere S ={1, 2, 3, 4}. Então, {1, 3, 4} é uma 3-combinação de S.
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 8 / 21
Teorema
Teorema 1
O número de r-combinações de um conjunto com n elementos, em que n é
um número inteiro não negativo e r é um inteiro com 0 ≤ r ≤ n, é igual a
C (n, r) = n!r !(n−r)!
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 9 / 21
Exemplo
Exemplo
Quantas mãos de poker de cinco cartas podem ser retiradas a partir de um
baralho de 52 cartas?
Quantas formas de selecionar 47 cartas a parir de um baralho de 52 cartas
são possíveis?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 10 / 21
Exemplo
Exemplo
Quantas mãos de poker de cinco cartas podem ser retiradas a partir de um
baralho de 52 cartas?
Quantas formas de selecionar 47 cartas a parir de um baralho de 52 cartas
são possíveis?
Resposta
C (52, 5) = 52!5!47! = 2.598.960
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 11 / 21
Permutações com Repetições
Teorema
O número de r-permutações de um conjunto com n objetos, com
repetições, é nr
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 12 / 21
Exemplo
Exemplo 1
Quantas sequências de extensão r podem ser formadas com o alfabeto da
língua inglesa?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 13 / 21
Exemplo
Exemplo 1
Quantas sequências de extensão r podem ser formadas com o alfabeto da
língua inglesa?
Resposta
26r
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 14 / 21
Exemplo - Permutações com Objetos idênticos
Exemplo 2
Quantas sequências diferentes podem ser obtidas reorganizando-se as letras
da palavras SUCCESS?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 15 / 21
Exemplo - Permutações com Objetos idênticos
Exemplo 2
Quantas sequências diferentes podem ser obtidas reorganizando-se as letras
da palavras SUCCESS?
Resposta
C (7, 3)C (4, 2)C (2, 1)C (1, 1) = 420
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 16 / 21
Exemplo - Distribuição de objetos em caixas
Exemplo 3
Quantas maneiras existem de distribuir mãos de 5 cartas para cada um dos
quatros jogadores, a partir de um baralho de 52 cartas?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 17 / 21
Exemplo - Distribuição de objetos em caixas
Exemplo 3
Quantas maneiras existem de distribuir mãos de 5 cartas para cada um dos
quatros jogadores, a partir de um baralho de 52 cartas?
Resposta
C (52, 5)C (47, 5)C (42, 5)C (37, 5) = 52!5!5!5!5!32!
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 18 / 21
Combinações com repetições
exemplo
4 brinquedos =⇒ a, b, c, d
Comprar 2 bilhetes?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 19 / 21
Combinações com repetições
Definição
CRpn = C
p
n+p−1
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 20 / 21
Exemplo
Exemplo 1
De quantos modos podemos comprar 4 refrigerantes em um bar que vende
2 tipos de refrigerantes?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 21 / 21
Exemplo
Exemplo 1
De quantos modos podemos comprar 4 refrigerantes em um bar que vende
2 tipos de refrigerantes?
Resposta
CR42 = C
4
2+4−1 = C
4
5 = 5
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 22 / 21
Exemplo
Exemplo 3
De quantos modos diferentes podemos distribuir 10 bombons idênticos em
4 caixas diferentes?
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 23 / 21
Exemplo
Exemplo 3
De quantos modos diferentes podemos distribuir 10 bombons idênticos em
4 caixas diferentes?
Resposta
CR104 = C
10
13 = 286
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 24 / 21
The End
Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 25 / 21
	Permutações
	Combinações
	Repetições