Slides - Matemática Discreta - Combinatória

Prévia do material em texto

Aula 3
• Contagem (Combinatória)
– Princípio da Multiplicação
– Princípio da Adição
– Princípio da Inclusão e Exclusão
Contagem
• Princípio da Multiplicação
– Exemplo: Batalha Naval
• L = { a, b, c, d, e }
C = { 1, 2, 3, 4, 5, 6, 7, 8 }
Quantas opções de tiro?
1 2 3 4 5 6 7 8
a
b ⊗⊗⊗⊗
c
d
e
5 x 8 = 40
Contagem
• Princípio da Multiplicação
– Exemplo: Batalha Naval
• L = { a, b, c, d, e }
C = { 1, 2, 3, 4, 5, 6, 7, 8 }
• Tiros: pares ordenados
– T = L ×××× C = { (l, c) | l ∈ L e c ∈ C }
1 2 3 4 5 6 7 8
a
b ⊗⊗⊗⊗
c
d
e
(b,4) ∈ T
Contagem
• Princípio da Multiplicação
– Exemplo: Batalha Naval
• L = { a, b, c, d, e }
C = { 1, 2, 3, 4, 5, 6, 7, 8 }
• Quantos tiros? 
| T | = | L ×××× C | = | L | ×××× | C |
Assim: |T| = 5 × 8 = 40
1 2 3 4 5 6 7 8
a
b ⊗⊗⊗⊗
c
d
e
Contagem
• Princípio da Multiplicação
– Para dois conjuntos X e Y
| X ×××× Y | = |X| ×××× |Y|
Se temos n1 diferentes resultados para um evento E1 , e
n2 diferentes resultados para um 2º evento E2 , temos então
n1 × n2 resultados distintos para a sequência dos dois eventos.
Princípio da Multiplicação
• Exemplo
1) Gisele deseja formar um conjunto de calça-blusa para vestir-se. Se ela 
dispõe de 6 calças e 10 blusas para escolher, de quantos modos ela pode 
formar o conjunto?
Resp. (c,b) ∈ C ×××× B |C| = 6
|B| = 10
| C ×××× B | = 6 × 10 = 60 conjuntos
Princípio da Multiplicação
• Vale para mais conjuntos: | X ×××× Y ×××× Z | = |X|××××|Y|××××|Z|
• Exemplo
2) Gisele deseja formar um conjunto de calça-blusa-sapato para vestir-se. Se 
ela dispõe de 6 calças, 10 blusas e 8 sapatos para escolher, de quantos 
modos ela pode formar o conjunto?
Resp. (c,b,s) ∈ C ×××× B ×××× S |C| = 6 |B| = 10 |B| = 8
| C ×××× B ×××× S | = 6 × 10 × 8 = 480 conjuntos
Princípio da Multiplicação
• Exemplos
3) Quantas placas de automóveis distintas podem existir no Brasil?
Resp. L L L –DDDD
26 × 26 × 26 × 10 × 10 × 10 × 10 = 263 × 104 placas distintas
263 × 10 × 9 × 8 × 7
4) Quantas placas de automóveis possuem todos os dígitos distintos?
Resp. L L L –DDDD
Princípio da Multiplicação
• Exemplos
5) Quantas placas de automóveis possuem letras e dígitos distintos?
Resp. L L L –DDDD
26 × 25 × 24 × 10 × 9 × 8 × 7
26 × 1 × 1 × 10 × 10 × 10 × 10 = 26 × 104
ou 260000 placas possíveis.
6) Quantas placas de automóveis possuem todas as letras iguais?
Resp. L L L –DDDD
Princípio da Multiplicação
• Exemplos
7) Quantas placas de automóveis possuem todas as letras iguais e todos os 
dígitos distintos?
Resp. L L L –DDDD
26 × 1 × 1 × 10 × 9 × 8 × 7 = 26 × 10 × 9 × 8 × 7 
Contagem
• Princípio da Adição
– Para dois conjuntos disjuntos X e Y (X∩ Y =∅)
| X ∪ Y | = |X| + |Y|
•
Sejam dois eventos E1 e E2 disjuntos, com respectivamente
n1 e n2 resultados distintos.
Então temos n1 + n2 resultados distintos para o evento “E1 ou E2”.
Princípio da Adição
• Exemplo
8) Gisele mudou de ideia e resolveu usar um vestido. Como opções, ela tem 5
vestidos curtos e 8 vestidos longos. Quantas opções de vestido ela possui?
Resp. curto ou longo |C| = 5
|L| = 8
| C ∪ B | = | C | + | L | = 5 + 8 = 13 opções
Como C∩ L =∅
Princípio da Adição
• Exemplos
9) Quantas placas de veículos começam com a letra A ou com a letra B?
Resp. L L L –DDDD
Conjunto A = placas que começam com A: A L L –DDDD = 262 × 104 placas
Conjunto B = placas que começam com B: B L L –DDDD = 262 × 104 placas
Como A e B são disjuntos, pelo Princípio da Adição:
262 × 104 + 262 × 104 = 2 x 262 ×××× 104
Princípio da Adição
• Exemplos
9) Quantas placas de veículos começam com a letra A ou com a letra B?
Resp. L L L –DDDD
Outra solução: usamos direto o Princípio da Multiplicação
P L L –DDDD onde P = { A, B }
2 x 262 ×××× 104
Princípio da Adição
• Exemplos
10) Quantas placas de veículos começam com vogal?
Resp. A = placas que começam com A: ALL – DDDD = 262 × 104 placas
E = placas que começam com E: ELL – DDDD = 262 × 104 placas
I = placas que começam com I: ILL – DDDD = 262 × 104 placas
O = placas que começam com O: OLL – DDDD = 262 × 104 placas
U = placas que começam com U: ULL – DDDD = 262 × 104 placas
Ou então: VLL – DDDD onde V = { A, E , I , O , U }
5 x 262 ×××× 104
Princípio da Adição
• Exemplos
11) Quantos diferentes sufixos de telefone são formados apenas com dígitos 
distintos?
Resp.
D1 D2 D3 D4
10 x 9 x 8 x 7
Princípio da Adição
• Exemplos
12) Sufixos de telefone D1 D2 D3 D4
com todos os dígitos distintos,
D1 é par E D2 ≥ 5?
{0,2,4,6,8} {5,6,7,8,9} 8 7 
D1 D2 D3 D4
5 ?
Solução: Princípio da Adição
{0,2,4} {5,6,7,8,9} 8 7 
D1 D2 D3 D4
OU {6,8} {5,6,7,8,9} 8 7 
D1 D2 D3 D4
Resp.: 3 × 5 × 8 × 7 + 2 × 4 × 8 × 7.
Contagem
• Princípio da Inclusão e Exclusão
– Para dois conjuntos não disjuntos X e Y
| X ∪ Y | = |X| + |Y| + | X∩ Y |
Princípio da Inclusão e Exclusão
• Exemplos
13) Gisele foi escolher o vestido. Cores dos vestidos curtos: rosa, verde, preto, 
branco, azul; Cores dos vestidos longos: marfim, preto, branco, verde, lilás, 
grafite, turquesa, ocre. Quantas opções de cores ela tem para escolher?
Resp.
C = { r, v, p, b, a } | C | = 5
L = { m, p, b, v, l , g, t, o } | L | = 8
| C | + | L| + | C∩ L | =
5 + 8 – 3 = 10 opções distintas de cor.
|C|+|I| =
C: começam com par: 263 × 5 × 103
• Exemplos
14) Placas que começam com dígito par
OU terminam com dígito ímpar?
Resp.
- |C∩ I|
Princípio da Inclusão e Exclusão
263 × 104 
I : terminam com ímpar: 263 × 5 × 103
ABC – 2233
ABC – 2222
ABC – 3333
– 263 × 52 × 102 
• Exercícios
15) Sufixos de telefone em que a soma dos dois dígitos iniciais é igual a 8?
Resp.
Contagem
9 × 1 × 102 = 900
D1 D2 D3 D4
D1 + D2 = 8
• Exercícios
16) Sufixos de telefone com dígitos distintos, a soma dos dois dígitos iniciais é 
igual a 8?
Resp.
Contagem
8 × 1 × 8 × 7
D1 D2 D3 D4
D1 + D2 = 8
• Exercícios
17) Gisele possui 2 calças claras e 4 escuras. Quanto às blusas, são 3 claras e
7 escuras. Gisele quer variar as cores, misturando as tonalidades claras com 
as escuras. De quantos modos ela pode formar o conjunto?
Resp.
Contagem
2 × 7 + 4 × 3 = 14 + 12 = 26
Contagem
• Exercícios - AVA
–MATERIAL DIDÁTICO
• Notas de Aula MatDisc – Contagem; 1.13
– ATIVIDADES
• Exercícios MatDisc - Contagem; 22) a 28)
– MIDIATECA
• Exercícios de Arranjos, Combinações e Permutações; 1) a 8)
Obrigado!
Aula 4
• Contagem (Combinatória)
– Permutações simples
• Fatorial
– Permutações com repetições
– Arranjos Simples
• Exemplo
17) Quantos são os anagramas da palavra CONTAGEM?
Resp. ___ ___ ___ ___ ___ ___ ___ ___
Permutações simples
8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
Anagramas: Permutações das 8 letras (distintas)
Notação: P8 = 8!
• Permutações simples
– n objetos distintos
– Arranjos ordenados
• Os mesmos objetos dispostos em outra ordem = outra permutação
– Notação
• P
n
ou P(n,n): número de permutações dos n objetos
Permutações simples
P
n
= n ×××× (n–1) ×××× (n–2) ×××× ... ×××× 3 ×××× 2 ×××× 1 P
n
= n!ou
• Fatorial de n (n ∊ IN): n!
• Definição 1
Permutações simples
n! = 1 × 2 × 3 × ... × n
ou
n! = n × (n–1) × (n–2) × ... × 3 × 2 × 1
2! = 1 × 2 = 2
1! = 1
3! = 1 × 2 × 3 = 6
0! = ?
4! = 1 × 2 × 3 × 4 = 24
0! = 1
• Fatorial de n (n ∊ IN): n!
• Definição 2
Permutações simples
n! = n × (n–1) × (n–2) × ... × 3 × 2 × 1
0! = 1
1! =
3! = 3 × 2! = 
4! = 4 × 3! = n! = n × (n–1)!
2! = 2 × 1! = 
=1 × 0! = 1 × 1 = 1
2 × 1 = 2
3 × 2 = 6
4 × 6 = 24
• Fatorial de n (n ∊ IN): n!
• Definição 2
Permutações simples
n! = n × (n–1)!  � − 1 ! = 
�!
�
Exemplo: 3! = 
	!
	
 = 
	×�×�×
	
Então 0! =
1!
1
= 
1
1
= 1
• Fatorial de n (n ∊ IN): n!
• Definição 2
– Definição por recorrência:
Permutações simples
n! = n × (n–1)!
0! = 1
• Exemplo
18) Quantos anagramas da palavra CONTAGEM começam com vogal?
Resp. { A,E,O } ___ ___ ___ ___ ___ ___ ___ 
Permutações simples
3
3 × P7 = 3 × 7!
× 7 × 6 × 5 × 4 × 3 × 2 × 1
• Exemplo
19) Quantos anagramas da palavra CONTAGEM começam com as três vogais?
Resp. ___ ___ ___ ___ ___ ___ ___ ___ 
Permutações simples
P3 × P5 = 3! × 5!
3 × 2 × 1 × 5 × 4 × 3 × 2 × 1
• Exemplo
20) Um grupo de 11 homens e 8 mulheres deve formar uma fila.
De quantas formas isso é possível?
Resp.
Permutações simples
P19 = 19!
• Exemplo
21) O mesmo grupo com 11 homens e 8 mulheres deve forma uma fila. Quantas 
filas distintas podem ser formadas, estando os homens todos juntos, e as 
mulheres também?
Resp.
Permutações simples
Homens depois mulheres: P11 × P8 = 11! × 8!
ou
Mulheres depois homens: P8 × P11 = 11! × 8!
2 × P8 × P11 = 2 × 11! × 8!
• Exemplo
22) Uma bibliotecária recebeu 5 livros de Algoritmos, 4 de Lógica, e 7 de 
Programação, todos distintos entre si. Ela tem que organizá-los em uma 
prateleira, mantendo todos os livros de um mesmo assunto agrupados. De 
quantas formas ela pode organizar os livros?
Resp.
Permutações simples
|A1A2...|L1L2...|P1P2... |
Mas... podemos trocar a ordem dos assuntos.
Permutando os assuntos: ALP, APL, LAP, LPA, PAL, PLA
3! ×××× 5! ×××× 4! ×××× 7!= 5! × 4! × 7!
• Exemplo
– Quantos anagramas da palavra CASO? R.: 4! = 24
– Quantos anagramas da palavra CASA?
Permutações com repetições
CA1SA2
A1A2CS
A1A2SC
A1CA2S
A1CSA2
A1SA2C 
A1SCA2
A2A1CS
A2A1SC
A2CA1S
A2CSA1
A2SA1C 
A2SCA1
CA2SA1CA1SA2
Resp: 
�
	
�
 = 
	!
�
 = 12
• Exemplo
– Quantos anagramas da palavra ARARA?
Permutações com repetições
A1R1A2R2A3
A1R1A2R2A3 
A1R1A3R2A2 
A2R1A1R2A3 
A2R1A3R2A1 
A3R1A1R2A2 
A3R1A2R2A1
Resp: 
�
�
�
�
�
�
 = 
�!
�! ∙ �!
 =
�×	×�!
� ∙ �! 
A1R2A2R1A3 
A1R2A3R1A2 
A2R2A1R1A3 
A2R2A3R1A1 
A3R2A1R1A2 
A3R2A2R1A1
= 10
• Caso geral
n objetos
n1 ocorrências do mesmo objeto o1
n2 ocorrências no mesmo objeto o2
...
n
k
ocorrências do mesmo objeto o
k
.
Permutações dos n objetos = 
��
��
��
�
× ⋯ ×��
�
=
�!
�
!�
�
!×⋯×�
�
!
Permutações com repetições
• Exemplo
23) Existem quantos anagramas da palavra PROPORCIONAL?
Resp.
Permutações com repetições
12 Letras: 2 P, 2 R, 3 O
12!
3! 2! 2!
• Exemplo
24) Quantos anagramas da palavra PROPORCIONAL começam com vogal?
Resp.: usar o Princípio Aditivo
Permutações com repetições
A_____ = 11 Letras: 2 P, 2 R, 3 O
11!
2! 2! 2!
 + 2 ∙
11!
2! 2! 3!I______ = 11 Letras: 2 P, 2 R, 3 O
O_____ = 11 Letras: 2 P, 2 R, 2 O
• Desafios!
– Quantos anagramas da palavra PROPORCIONAL começam com todas 
as vogais na frente das consoantes?
– Quantos anagramas da palavra PROPORCIONAL contêm todas as 
vogais agrupadas, e também todas as consoantes agrupadas?
– Quantos anagramas da palavra PROPORCIONAL contêm todas as 
vogais agrupadas?
Permutações com repetições
• Exemplo
– Quantos diferentes sufixos (de números) de telefone com todos os 
dígitos distintos existem?
Resp. ___ ___ ___ ___
Arranjos (ou Arranjos simples)
10 × 9 × 8 × 7
Outra forma de resposta = 
�×�×�×�×�×�×�×�× ×!
�×�×�×�× ×!
= 
!"! 
�!
• Arranjos – ou Arranjos Simples
– n objetos distintos
– Seleção de r objetos
• Sem reposição
– A ordem da seleção influi
• Variação na ordem = arranjos distintos. Ex.: 1289 ≠≠≠≠ 1298
– Dizemos arranjos de n tomados r : #
$
%
ou &
$
%
ou &(%, $)
Arranjos
• Arranjos – ou Arranjos Simples – de n objetos tomados r
– Notação 
*
+
�
ou P
+
�
ou P �, +
• n objetos distintos entre si
• Seleção de r objetos
• Seleção sem reposição
• A ordem da seleção influi.
Ex.: 1289 ≠≠≠≠ 1298
Arranjos
*
+
�
= 
�!
(� − +)!
• Voltando ao exemplo anterior
– Quantos diferentes sufixos (de números) de telefone com todos os 
dígitos distintos existem?
Resp.
• n = 10
• r = 4
• Sem repetição
• A ordem influi
Arranjos
*
4
10
= 
10!
10 − 4 !
=
10!
6!
=
10 ∙ 9 ∙ 8 ∙ 7 ∙ �!
�!
= 10 × 9 × 8 × 7
• Exemplo
25) Quantas placas de automóveis possuem letras e dígitos distintos?
Resp.: usar o Princípio Multiplicativo com dois eventos
Escolher as letras e depois escolher os dígitos.
Arranjos
P 26,3 × P 10,4 =
26 × 25 × 24 × 23!
23! 
 × 10 × 9 × 8 × 7
• Exemplo
26) Quantos números de 3 algarismos distintos podem ser escritos com os 
dígitos 1, 3, 4, 5, 6, 8, e 9?
Resp.:
Arranjos
210567
!4
!4567
)!37(
!7)3,7(3737 =××=
×××
=
−
=== PPA
Arranjos com n = 7 e r = 3
• Exemplo
27) Temos uma prova olímpica individual com 10 competidores. De quantas 
formas distintas as medalhas de ouro, prata e bronze podem ser 
distribuídas?
Arranjos
Resposta nas Notas de Aula
Obrigado!
Aula 5
• Contagem (Combinatória)
– Combinações simples
– Exercícios
• Exemplo
– Conjunto com 5 estudantes { Ana, Bruno, Carlos, Diana, Edna }
A. Montar chapa (Presidente, Vice-presidente, Secretário) para o grêmio
• Seleção sem repetição
• A ordem influi: ABC é uma chapa; BAC é outra chapa
• Solução: arranjos de 5 tomados 3
Combinações Simples
Resp.: *
3
5
= 5 × 4 × 3 = �" chapas distintas
• Exemplo
– Conjunto com 5 estudantes { Ana, Bruno, Carlos, Diana, Edna }
B. Selecionar 3 alunos para representar a faculdade em uma gincana de 
Matemática Discreta. Quantas equipes podem ser formadas?
• Seleção sem repetição
• A ordem NÃO influi: ABC e BAC são a mesma equipe.
• Solução: combinações de 5 tomados 3 
Combinações Simples
Notação: 3
�
�
 ou 3 �, �
• Exemplo
– E = { A, B, C, D, E }. Selecionar uma equipe com 3 alunos.
Vamos enumerar os 60 arranjos:
Combinações Simples
Com ABC: Com ABD: Com ABE:
ABE
AEB 
BAE
BEA
EAB
EBA
3! arranjos
Com ACD:
ABC
ACB
BAC
BCA
CAB
CBA
6 arranjos
ABD
ADB
BAD
BDA
DAB
DBA
6 arranjos
Com ACE:
Com BCD:
Com BCE:
Com BDE:
Com CDE:
Com ADE:
Cada combinação “está relacionada” 
a um grupo de 3! arranjos contendo 
os mesmos alunos.
Número de combinações (grupos):
60 / 3!
• Exemplo
– E = { A, B, C, D, E }. Selecionar uma equipe com 3 alunos.
Vamos dividir os 60 arranjos em grupos de 3! arranjos (grupos com 
os mesmos alunos). Quantos grupos (combinações) existem?
Resp.:
Combinações Simples
C
3
5
 = 
7
�
�
�!
= 
8�
8
= 10 combinações 
• Exemplo
– E = { A, B, C, D, E }. Selecionar uma equipe com 3 alunos.
Vamos calcular de outra forma?
Resp.:
Combinações Simples
C
3
5
 = 
7
�
�
�!
= 
�!
�! 
⋅
�! 
= 
�×	× �! 
� ⋅ �! 
= 
��
�
= 10 combinações 
• Caso geral
– n objetos distintos
– Selecionar r objetos, sem repetição
– A ordem NÃO influi
– Combinações de n tomados r
Combinações Simples
C
+
�
 = 
7
:
�
:!
= 
%!
(%;$)! ⋅ $!
• Exemplo
28) De um grupo de 5 pessoas, quantas equipes com 3 componentes podem ser 
formadas?
Resp.: já utilizamos a fórmula
Combinações Simples
C
3
5
 = 
7
�
��!
= 
�!
�! ⋅ �!
= 
�×	× �! 
� ⋅ �! 
= 
��
�
= 10 combinações 
• Exemplo
29) De um grupo de 11 homens e 8 mulheres, queremos formar um júri com 4 
membros. De quantas formas distintas o júri pode ser formado?
Resp.:
Combinações Simples
C
4
19
 =
�!
�! ⋅	!
= 
�×
�×
�×
8× 
�! 
	 ⋅ � ⋅ � ⋅ 
�! 
= 19 × 6 × 17 × 2 combinações 
Obs.: nas Notas de Aula as simplificações foram diferentes
• Exemplo
30) Grupo de 11 homens e 8 mulheres, júri com 4 membros. De quantas formas 
distintas o júri pode ser formado somente com membros do mesmo sexo?
Resp.:
Combinações Simples
C
4
11
 = 
!
�! ⋅	!
+ 
�!
	! ⋅	!
= 
×
�×�×�× �! 
	 ⋅ � ⋅ � ⋅ �! 
+
�×�×8×�× 	! 
	 ⋅ � ⋅ � ⋅ 	! 
= 11 × 10 × 3
C
4
8
+
+ 7 × 2 × 5 combinações 
• Exemplo
31) Grupo de 11 homens e 8 mulheres, júri com 4 membros. De quantas formas 
distintas o júri pode ser formado contendo metade de cada sexo?
Resp.:
Combinações Simples
C
2
11
 = 
11!
9! ⋅ 2!
×
8!
6! ⋅ 2!
= 
×
�× �! 
� ⋅ �! 
×
�×�× 8! 
� ⋅ 8! 
= 11 × 5
C
2
8
×
 × 4 × 7 combinações 
• Exemplo
32) Grupo de 11 homens e 8 mulheres, júri com 4 membros. De quantas formas 
distintas o júri pode ser formado contendo mais homens do que mulheres?
Resp.:
Combinações Simples
C
3
11
 = 
!
�! ⋅�!
 ×
�!
�! ⋅
!
= 
×
�×�× �! 
� ⋅ � ⋅ �! 
×
�× �! 
 ⋅ �! 
C
1
8
×
= 11 × 5 × 3 × 8 + 11 × 10 × 3 combinações 
C
4
11
 = 
11!
7! ⋅ 4!
= 11 × 10 × 3C
0
8
×
ou
• Vamos trabalhar?
33) Gisele tem 12 amigos, mas ela só pode convidar 6 deles para a sua festa. De 
quantas formas distintas ele pode formar a lista de convidados?
34) Imagine que, dentre os 12 amigos de Gisele, 2 não se falam, e ela não pode 
convidar ambos. De quantas formas distintas ele pode formar a lista de 
convidados sem que ambos estejam presentes?
35) Imagine que exista um casal entre os 12 amigos de Gisele, e ela não pode 
convidar um deles apenas. De quantas formas distintas ele pode formar a 
lista de convidados com esta restrição?
Combinações Simples
Contagem
• Exercícios - AVA
–MATERIAL DIDÁTICO
• Notas de Aula MatDisc – Exercícios 33) a 35)
– ATIVIDADES
• Exercícios MatDisc - Contagem; 29) a 47)
– MIDIATECA
• Exercícios de Arranjos, Combinações e Permutações; 9) a 33)
Obrigado!