Instituto Federal de Educação, Ciência e
Tecnologia de São Paulo - IFSP
Campus de Caraguatatuba
Tecnólogo em Análise e Desenvolvimento de Sistemas
20 Semestre de 2013
Matemática Discreta 2 – MD 2
Prof. Lineu Mialaret
Aula 4: Combinatória (2)
Matemática Discreta 2
Aula 4 - 1/47
©Prof. Lineu Mialaret
Introdução (1)
 Seja o seguinte problema:
 A última parte de seu número de telefone possui quatro
dígitos. Quantos dessas seqüências de quatro dígitos
existem, se um mesmo dígito não pode ser repetido?
 Nesse tipo de problema, a seqüência de dígitos 1259 é
diferente da seqüência 5912, já que a ordem dos dígitos é
importante.
 Seja M = {a1,a2,...,am} um conjunto com m elementos.
Denomina-se por arranjo dos m elementos, tomados
r a r, toda r-upla {a1,a2,a3,... ar}, com r  m, formada com
elementos de M, todos distintos.
 Um arranjo ordenado e distinto de elementos de M é
chamado de permutação (observar que não há repetição
de elementos).
Matemática Discreta 2
Aula 4 - 2/47
©Prof. Lineu Mialaret
Introdução (2)
n
r-uplas de 3 elementos
6
1
1,2,6
4
2
1,6,2
...
6,1,2
5
3
Arranjo de n elementos tomados r a r
Arranjo de 6 elementos tomados 3 a 3
Matemática Discreta 2
Aula 4 - 3/47
©Prof. Lineu Mialaret
Introdução (3)
 No caso das seqüências de quatro dígitos do telefone,
cada uma delas é uma permutação de 4 objetos distintos
escolhidos de um conjunto de 10 objetos distintos (os
dígitos). Quantas permutações existem?
 Lembrando-se do princípio da multiplicação, existem 10
escolhas para o primeiro dígito, 9 escolhas para o segundo e
assim por diante, totalizando 10 x 9 x 8 x 7 = 5040
permutações.
 O número de permutações de r objetos distintos
escolhidos entre n objetos distintos é simbolizado por
P(n,r).
 Para o cenário acima, pode-se expressar a solução do
problema como P(10,4) = 5040.
 E para o exemplo da transparência anterior?
Matemática Discreta 2
Aula 4 - 4/47
©Prof. Lineu Mialaret
Permutação (1)
 Pode-se estabelecer uma fórmula para P(n,r).
 Para isso usa-se a função fatorial.
 Definição:
 Para um inteiro positivo n qualquer, n fatorial ou n! é
definido como o produto dos termos n(n - 1)(n - 2) ...1.
 0! = 1, por definição. (1! também = 1).
 Da definição de n!, sabe-se que
 n! = n(n - 1)! = n(n - 1)(n - 2)! = n(n - 1)(n - 2)(n - 3)! = ...
 4! = 4(4 - 1)! = 4(3)(4 - 2)!
= 4(3)(2)(4 - 3)!
=
= 4(3)(2)(1) = ?
Matemática Discreta 2
Aula 4 - 5/47
©Prof. Lineu Mialaret
Permutação (2)
 Por exemplo, caso se tenha um total de 10 elementos,
por ex. S = {1,2,…,10}, uma permutação de três
elementos desse conjunto é (2,3,1).
 Nesse caso, n = 10 e r = 3. Então de quantas maneiras




isso pode ser completamente feito?
Para o primeiro membro de todas as permutações
possíveis se escolhe um elemento de todos os n possíveis.
Uma vez já utilizado um dos n elementos, para o segundo
membro da permutação há (n − 1) elementos para escolher
desse conjunto.
O terceiro membro pode ser preenchido de (n − 2)
maneiras, devido ao uso dos que o antecederam.
Esse padrão continua até que tenham sido utilizados os r
membros na permutação. Isso significa que o último
membro pode ser preenchido de (n − r + 1) maneiras.
Matemática Discreta 2
Aula 4 - 6/47
©Prof. Lineu Mialaret
Permutação (3)
__ __ __
3_ __ __
3_ 7_ __
3_ 7_ 9_
1,
2,
3,
4,
5,
6,
7,
8,
9,
10
1, 1,
2, 2,
3, 4,
4, 5,
5, 6,
6, 7,
7, 8,
8, 9,
9, 10
10
1,
2,
3,
4,
5,
6,
7,
8,
9,
10
1, 1,
2, 2,
3, 4,
4, 5,
5, 6,
6, 8,
7, 9,
8, 10
9,
10
n = 10
Matemática Discreta 2
(n -1) = 9
1,
2,
4,
5,
6,
8,
9,
10
1,
2,
4,
5,
6,
8,
10
(n – 2)
ou
n = 10
Inserção da última coluna
r=3
n–r +1=8
Aula 4 - 7/47
©Prof. Lineu Mialaret
Permutação (4)
 Em síntese, se encontra um total de
 n(n − 1)(n − 2) … (n − r + 1) permutações diferentes dos r
objetos, retirados do grupo dos n objetos.
 Caso se denote esse número por P(n,r) e utilizando a
notação fatorial, pode-se escrever
= n(n - 1)...(n - r +1)
= n(n - 1)...(n - r +1)(n - r)!
= n(n - 1)...(n - r +1)(n - r)!
(n – r)!
=
P(n,r)
Matemática Discreta 2
Aula 4 - 8/47
=
= n!
= n!
(n – r)!
©Prof. Lineu Mialaret
Permutação (5)
 Assim, P(n,r) pode ser dado pela fórmula
 P(n,r) = n!/(n - r)!, para 0  r  n
 P(n,r) significa permutar n objetos em r objetos.
 No
cenário dos 4 dígitos, usando a fórmula de
permutação, tem-se
 P(10,4) = 10x9x8x7=
= 10x9x8x7x6x5x4x3x2x1 = 10! = 10!
6x5x4x3x2x1
= 6! = (10 - 4)!
 Ex.:
 P(7,3) = 7!/(7-3)! = 7!/4! =
 P(7,3) = (7x6x5x4x3x2x1)/(4x3x2x1) = 210.
Matemática Discreta 2
Aula 4 - 9/47
©Prof. Lineu Mialaret
Permutação (6)
 Há três casos especiais no cálculo de P(n,r):
 P(n,0).
 P(n,1).
 P(n,n).
 Para P(n,0):
 P(n,0) = n!/(n - 0)! = n!/n! = 1.
 Existe apenas um arranjo ordenado de zero objetos, o
conjunto .
 Para P(n,1):
 P(n,1) = n!/(n - 1)! = n.
 Existem n arranjos ordenados de um objeto.
Matemática Discreta 2
Aula 4 - 10/47
©Prof. Lineu Mialaret
Permutação (7)
 Para P(n,n):
 P(n,1) = n!/(n - n)! = n!/0! = n!.
 Existem n! arranjos ordenados de n objetos.
Matemática Discreta 2
Aula 4 - 11/47
©Prof. Lineu Mialaret
Permutação (8)
 Exemplo 1: Qual o número de permutações de três
elementos obtidas com o conjunto S = {a,b,c}?
 O número de permutações de 3 objetos, a, b, e c é dado
por P(3,3) = 3! = 6.
 As permutações são:
 abc, acb, bac, bca, cab, cba.
Matemática Discreta 2
Aula 4 - 12/47
©Prof. Lineu Mialaret
Permutação (9)
 Exemplo 2: Quantas palavras de 3 letras (que podem
não fazer sentido) são formadas a partir da palavra
“compilar”, se nenhuma letra pode ser repetida?
 Neste caso, a ordem das letras importa, e se deseja saber
o número de permutações de 3 objetos distintos retirados
de um conjunto de 8 objetos.
 P(n,r) = P(8,3) = 8!/(8 - 3)! = 8!/5!= 336.
 Obs.:
 Poderia ter sido usado o princípio da multiplicação para a
solução desse problema.
 Qual a solução usando esse princípio?
Matemática Discreta 2
Aula 4 - 13/47
©Prof. Lineu Mialaret
Permutação (10)
 Exercício 1: Dez atletas competem num evento olímpico.
São dadas medalhas de ouro, prata e bronze. De
quantas maneiras podem ser dadas as medalhas aos
atletas?
Matemática Discreta 2
Aula 4 - 14/47
©Prof. Lineu Mialaret
Permutação (11)
 Exercício 1: Dez atletas competem num evento olímpico.
São dadas medalha de ouro, prata e bronze. De quantas
maneiras podem ser dadas as medalhas aos atletas?
 Resposta:
 Neste tipo de problema, a ordem é importante, ou seja, a
dado 3 atletas, A, B e C, a premiação A(ouro), B(prata) e
C(bronze) é diferente da premiação C(ouro), A(prata) e
B(bronze).
 Se quer então o número de arranjos ordenados de 3
objetos de um conjunto de 10 objetos, ou seja, P(10,3).
 P(10,3) = 10!/(10 - 3)!
= 10!/7! = 7!(8 x 9 x 10)/7!
= 720.
Matemática Discreta 2
Aula 4 - 15/47
©Prof. Lineu Mialaret
Permutação (12)
 Exercício 2: De quantas maneiras se pode selecionar um
presidente e um vice-presidente de um grupo de 20
pessoas?
Matemática Discreta 2
Aula 4 - 16/47
©Prof. Lineu Mialaret
Permutação (13)
 Exercício 2: De quantas maneiras se pode selecionar um
presidente e um vice-presidente de um grupo de 20
pessoas?
 Resposta:
 Neste problema deseja-se selecionar 2 pessoas distintas
de um conjunto de 20 pessoas. Deseja-se saber o valor de
P(20,2).
 P(20,2) = 20!/(20 – 2)! = 20!/18! = (19 X 20)18!/18! = 380.
Matemática Discreta 2
Aula 4 - 17/47
©Prof. Lineu Mialaret
Permutação (14)
 Exercício 3: De quantas maneiras seis pessoas podem
se sentar em uma fileira de seis cadeiras?
Matemática Discreta 2
Aula 4 - 18/47
©Prof. Lineu Mialaret
Permutação (15)
 Exercício 3: De quantas maneiras seis pessoas podem
se sentar em uma fileira de seis cadeiras?
 Resposta:?
Matemática Discreta 2
Aula 4 - 19/47
©Prof. Lineu Mialaret
Combinação (1)
 Em certas ocasiões deseja-se selecionar r objetos de um
conjunto de n objetos, mas sem considerar a ordem da
sequência gerada, ou seja, a sequência 123 é a mesma
que 321.
 Neste caso está-se contando o número de combinações de
r objetos distintos escolhidos entre n objetos distintos, ou
seja, o número de subconjuntos de r elementos de um
conjunto de n elementos.
 Lembrando-se do princípio da multiplicação, o número de
permutações de r objetos distintos escolhidos num
conjunto de n objetos distintos P(n,r) é o produto do
número de escolhas possíveis de r objetos (combinações),
simbolizado aqui por C(n,r), pelo número de maneiras de
ordenar os objetos escolhidos (permutações de r objetos
em r), simbolizado aqui por r!.
Matemática Discreta 2
Aula 4 - 20/47
©Prof. Lineu Mialaret
Combinação (2)
n
r-uplas de 3 elementos
6
1
1,2,6
4
2
2,6,1
...
6,1,2
5
3
Número de permutações de r (03) objetos distintos escolhidos num
conjunto de n (06) objetos distintos P(n,r)
=
Combinações de 3 elementos entre si (não importa a ordem dos elementos)
multiplicado pelas
Maneiras de se ordenar 3 elementos em um subconjunto de 3 elementos
Matemática Discreta 2
Aula 4 - 21/47
©Prof. Lineu Mialaret
Combinação (3)
n
r-uplas de 3 elementos
6
1
1,2,6
4
2
2,6,1
...
6,1,2
5
3
Número de permutações de r (03) objetos distintos escolhidos num
conjunto de n (06) objetos distintos P(n,r)
=
P(6,3) = 6!/(6-3)! = 6!/3! = 4x5x6=120 permutações
Matemática Discreta 2
Aula 4 - 22/47
©Prof. Lineu Mialaret
Combinação (4)
n
r-uplas de 3 elementos
6
1
1,2,6
4
2
2,6,1
...
6,1,2
5
3
Maneiras de se ordenar 3 elementos em um subconjunto de 3 elementos
3
Matemática Discreta 2
2
1
= 6 maneiras
Aula 4 - 23/47
©Prof. Lineu Mialaret
Combinação (5)
n
r-uplas de 3 elementos
6
1
1,2,6
4
2
2,6,1
...
6,1,2
5
3
Número de permutações de r (03) objetos distintos escolhidos num
conjunto de n (06) objetos distintos P(n,r)
120
=
Combinações de 3 elementos entre si (não importa a ordem dos elementos)
x
multiplicado pelas
Maneiras de se ordenar 3 elementos em um subconjunto de 3 elementos
Matemática Discreta 2
Aula 4 - 24/47
6
©Prof. Lineu Mialaret
Combinação (6)
 Dessa forma, tem-se que:
 P(n,r) = C(n,r) x r!
ou
 C(n,r) = P(n,r)/r! = n!/(r!(n - r)!), para 0  r  n.
 C(n,r) significa combinar n objetos em r objetos.
 C(n,r) representa o número de subconjuntos de tamanho r que
podem ser obtidos de um conjunto de n elementos.
 Outras notações utilizadas para C(n,r):
n
Cr,
Cr
n
 r 
 
n, 

 Ex.:O valor de C(7,3) é
 C(7,3) = 7!/(3!(7 - 3)!) = 7!/(3! x 4!) = 35.
Matemática Discreta 2
Aula 4 - 25/47
©Prof. Lineu Mialaret
Combinação (7)
 Casos especiais para C(n,r):
 C(n,0).
 C(n,1).
 C(n,n).
 Para C(n,0):
 C(n,0) = n!/(0!(n - 0)!) = n!/(1(n)!) = 1.
 Isso reflete o fato de que há uma única maneira de
escolher zero objetos entre n objetos, escolher o conjunto
.
 Para C(n,1):
 C(n,1) = n!/(1!(n - 1)!) = n(n - 1)!/(n - 1)! = n.
 Isso reflete o fato de que há n maneiras de selecionar um
objeto entre n objetos.
Matemática Discreta 2
Aula 4 - 26/47
©Prof. Lineu Mialaret
Combinação (8)
 Para C(n,n):
 C(n,n) = n!/(n!(n - n)!) = n!/(n!(0!)) = 1.
 Isso reflete o fato de que há uma única maneira de
escolher n objetos entre n objetos, escolher todos os
objetos.
Matemática Discreta 2
Aula 4 - 27/47
©Prof. Lineu Mialaret
Combinação (9)
 Exemplo 3: Quantas mãos de pôquer, com 5 cartas cada,
podem ser distribuídas com um baralho de 52 cartas?
 Neste caso a ordem não é importante, já que o se deseja
saber é quais cartas ficaram em cada mão.
 Quer se calcular o número de maneiras de escolher 5
objetos dentre 52, ou seja, C(52,5).
 C(52,5) = 52!/5!(52 - 5)! = 52!/5!47! = 2598960.
Matemática Discreta 2
Aula 4 - 28/47
©Prof. Lineu Mialaret
Combinação (10)
 Exemplo 4: Dez atletas competem em um evento
olímpico, e três deles serão declarados vencedores. De
quantas maneiras podem ser escolhidos os vencedores?
 Neste caso, a ordem de escolha dos atletas não é
importante, de modo que se deve escolher simplesmente 3
objetos dentre um conjunto de 10 objetos, ou seja, C(10,3).
 C(10,3) = 10!/3!(10 - 3)! = 10!/3!7! = 120.
Matemática Discreta 2
Aula 4 - 29/47
©Prof. Lineu Mialaret
Combinação (11)
 Exercício 4: De quantas maneiras pode-se escolher uma
comissão de 3 pessoas de um grupo de 12 pessoas?
Matemática Discreta 2
Aula 4 - 30/47
©Prof. Lineu Mialaret
Combinação (12)
 Exercício 4: De quantas maneiras pode-se escolher uma
comissão de 3 pessoas de um grupo de 12 pessoas?
 Resposta:?
Matemática Discreta 2
Aula 4 - 31/47
©Prof. Lineu Mialaret
Combinação (13)
 Exercício 5: Uma comissão de 8 alunos deve ser
escolhida em um grupo contendo 19 alunos do primeiro
ano e 34 alunos do segundo ano.
 De quantas maneiras pode-se selecionar 3 alunos do
primeiro ano e 5 alunos do segundo ano?
 De quantas maneiras pode-se selecionar uma comissão
contendo exatamente um aluno do primeiro ano?
Matemática Discreta 2
Aula 4 - 32/47
©Prof. Lineu Mialaret
Combinação (14)
 Exercício 5: Uma comissão de 8 alunos deve ser
escolhida em um grupo contendo 19 alunos do primeiro
ano e 34 alunos do segundo ano.
a) De quantas maneiras pode-se selecionar 3 alunos do
primeiro ano e 5 alunos do segundo ano?
b) De quantas maneiras pode-se selecionar uma comissão
contendo exatamente um aluno do primeiro ano?
 Resposta a):
 Como a ordem dos indivíduos escolhidos é irrelevante,
esse é um problema de combinação.
 Há uma seqüência de duas tarefas: selecionar alunos do
primeiro ano e depois escolher alunos do segundo ano.
 Deve-se usar o princípio da multiplicação.
Matemática Discreta 2
Aula 4 - 33/47
©Prof. Lineu Mialaret
Combinação (15)
 Como existem C(19,3) modos de se escolher um aluno do
primeiro ano e C(34,5) maneiras de escolher um aluno do
segundo ano, a resposta é
 C(19,3) x C(34,5) = (19!/3!16!) x (34!/5!29!)
= 969 x 278256.
 Resposta b): ?
Matemática Discreta 2
Aula 4 - 34/47
©Prof. Lineu Mialaret
Combinação (16)
 Exercício 6: A Lotofácil é um tipo de loteria onde o
jogador escolhe 15 dezenas entre 25 dezenas possíveis.
De quantas maneiras pode-se escolher as 15 dezenas?
Matemática Discreta 2
Aula 4 - 35/47
©Prof. Lineu Mialaret
Combinação (17)
 Exercício 6: A Lotofácil é um tipo de loteria onde o
jogador escolhe 15 dezenas entre 25 dezenas possíveis.
De quantas maneiras pode-se escolher as 15 dezenas?
 Resposta:
– Como a ordem das dezenas escolhidas é irrelevante,
esse é um problema de combinação.
– Existem C(25,15) maneiras de escolher 15 dezenas
num conjunto de 25 dezenas.
– C(25,15) = 25!/(25-15)!15! = 3.268.760 combinações
de 15 dezenas.
– As chances de acertar as 15 dezenas são 1/
3.268.760 = ?
Matemática Discreta 2
Aula 4 - 36/47
©Prof. Lineu Mialaret
Combinação (18)
 Exercício 7: A Lotofácil também premia com 14 dezenas
que o jogador escolhe dentre as 25 dezenas possíveis
(lembrando que as 14 dezenas são na realidade obtidas
das 15 dezenas premiadas). De quantas maneiras podese escolher as 14 dezenas premiadas? E quais são as
chances de se acertar 14 pontos?
 Resposta:
 Como a ordem das dezenas escolhidas é irrelevante, esse
é um problema de combinação.
 Existem C(15,14) maneiras de escolher 14 dezenas
premiadas num conjunto de 15 dezenas premiadas.
 C(15,14) = 15!/(15-14)!14! = 15 combinações de 14
dezenas.
Matemática Discreta 2
Aula 4 - 37/47
©Prof. Lineu Mialaret
Combinação (19)
 Como se tem 14 dezenas premiadas, mas se joga com 15
dezenas, temos que escolher a dezena não premiada das
10 dezenas não premiadas que sobram (quando se
escolhe as 15 dezenas das 25 para se jogar).
 Logo, se tem 15 combinações de 14 dezenas multiplicadas
por C(10,1) = 15 x 10!/(10-1)!1! = 15 X 10 = 150
combinações premiadas de 14 dezenas.
 Para se saber as chances, é só dividir o número de
combinações de 14 dezenas premiadas pelo total de
combinações de 15 dezenas.
 Logo, as chances de se ganhar um sub-prêmio de 14
dezenas são 150/ 3.268.760 = 1/21791.
Matemática Discreta 2
Aula 4 - 38/47
©Prof. Lineu Mialaret
Combinação (20)
 Exercício 7: A Lotofácil também premia com 11 dezenas
que o jogador escolhe dentre as 25 dezenas possíveis
(lembrando que as 11 dezenas são na realidade obtidas
das 15 dezenas premiadas). De quantas maneiras podese escolher as 11 dezenas premiadas? E quais são as
chances de se acertar 11 pontos?
 Resposta:
Matemática Discreta 2
Aula 4 - 39/47
©Prof. Lineu Mialaret
Permitindo Repetição (1)
 Há cenários onde deve-se tratar com permutações e
combinações envolvendo objetos repetidos.
 Por exemplo, seja a palavra MISSISSIPI. Nessa palavra
há 4 objetos (letras) repetidos, ou seja, tem-se
MIS1S2IS3S4IPI, onde S1, S2, S3 e S4 referem-se ao
mesmo objeto (letra).
 Caso se deseje calcular o número de permutações
distintas que podem ser feitas com as letras que formam a
palavra MISSISSIPI, a resposta não será 10!, pois os 10
caracteres da palavra não são distintos.
 Isso significa que o número 10! conta alguns arranjos mais
de uma vez (MIS1S2IS3S4IPI e MIS2S1IS3S4IPI, por
exemplo.)
Matemática Discreta 2
Aula 4 - 40/47
©Prof. Lineu Mialaret
Permitindo Repetição (2)
 Seja uma seqüência (arranjo) qualquer das letras da
palavra MISSISSIPI. Os quatro caracteres S ocupam
determinadas posições na seqüência.
 Rearrumando esses caracteres S nessas posições obtémse a mesma cadeia, logo a seqüência tem 4! cadeias de
caracteres iguais.
 Para evitar contar a mesma cadeia mais de uma vez, devese dividir 10! por 4!, para se retirar todas as maneiras de se
permutar os caracteres S na mesma posição. De modo
análogo, tem que se dividir também por 4! por causa das
letras I.
 Logo, o número de permutações distintas desses n
objetos é
 10!/4!4! = 5x6x7x8x9x10/4!
Matemática Discreta 2
Aula 4 - 41/47
©Prof. Lineu Mialaret
Permitindo Repetição (3)
 Definição: Supondo que há n objetos dos quais um
conjunto de n1 são indistinguíveis entre si (são repetidos),
um outro conjunto de n2 objetos são também
indistinguíveis entre si, e assim por diante até um
conjunto de nk objetos que também são indistinguíveis
entre si.
 O número de permutações distintas desses n objetos é
n!/(n1! x n2! x ... x nk!).
Matemática Discreta 2
Aula 4 - 42/47
©Prof. Lineu Mialaret
Permitindo Repetição (4)
 Exercício 6: Quantas permutações distintas das letras da
palavra MONGOOSES existem?
Matemática Discreta 2
Aula 4 - 43/47
©Prof. Lineu Mialaret
Permitindo Repetição (5)
 Exercício 6: Quantas permutações distintas das letras da
palavra MONGOOSES existem?
 Resposta:?
Matemática Discreta 2
Aula 4 - 44/47
©Prof. Lineu Mialaret
Permitindo Repetição (6)
 As fórmulas apresentadas para permutação, P(n,r), e
combinação, C(n,r) supõem que se seleciona r objetos
dentre n objetos disponíveis, usando-se cada objeto uma
só vez. Logo r  n.
 Entretanto, pode-se supor que os n objetos estão
disponíveis para se usar quantas vezes forem
necessárias, ou seja, que há repetição na escolha de
objetos.
 Pode-se construir palavras usando as 26 letras do alfabeto,
e as palavras podem ter qualquer tamanho, usando
repetidamente as letras.
 Ou pode-se falar em permutações e combinações de r
objetos entre n objetos, mas com a possibilidade de
repetição, o valor de r pode ser maior que n, ou seja, r  n.
Matemática Discreta 2
Aula 4 - 45/47
©Prof. Lineu Mialaret
Permitindo Repetição (7)
 Contar o número de permutações com repetições de r
objetos entre n objetos distintos é fácil.
 Tem-se n escolhas para o primeiro objeto, e como se
permite repetição, n escolhas para o segundo objeto, n
escolhas para o terceiro e assim por diante.
 Logo o número de permutações com repetições de r
objetos escolhidos dentre n objetos distintos é nr.
Matemática Discreta 2
Aula 4 - 46/47
©Prof. Lineu Mialaret
Permitindo Repetição (8)
 Exercício 7: Quantas palavras de 3 letras pode-se formar
com as 26 letras do alfabeto, sendo permitida a repetição
de letras?
 Resposta:?
Matemática Discreta 2
Aula 4 - 47/47
©Prof. Lineu Mialaret
Permitindo Repetição (9)
 Para
se contar o número de combinações com
repetições de r objetos entre n objetos distintos, usa-se a
fórmula C(r + n -1,r).
 C(r + n - 1,r) = (r + n - 1)/(r!(r + n -1 – r)!) =

Matemática Discreta 2
= (r + n - 1)!/(r!(n - 1)!).
Aula 4 - 48/47
©Prof. Lineu Mialaret
Permitindo Repetição (10)
 Exemplo 5: Um joalheiro, ao projetar um broche, decidiu
usar cinco pedras preciosas escolhidas entre diamantes,
rubis e esmeraldas. De quantas maneiras diferentes
podem ser escolhidas as pedras, admitindo-se que há
repetição de pedras.
 Este é um exemplo de combinação com repetição.
 Logo, tem-se r = 5 (número de objetos repetidos
escolhidos) e n = 3 (número de objetos distintos)
 C(r + n - 1,r) = (r + n - 1)!/(r!(n - 1)!)

Matemática Discreta 2
= (5 + 3 -1)!/(5!2!) = 7!/(5!2!)
Aula 4 - 49/47
©Prof. Lineu Mialaret
Permitindo Repetição (11)
 Exercício 8: Seis crianças escolhem um pirulito cada
entre uma seleção de pirulitos vermelhos, amarelos e
verdes. De quantas maneiras isso pode ser feito?
 Resposta:?
Matemática Discreta 2
Aula 4 - 50/47
©Prof. Lineu Mialaret
Permitindo Repetição (12)
 Sintetizando:
Matemática Discreta 2
Aula 4 - 51/47
©Prof. Lineu Mialaret