Livro Texto 1 - Matemática Discreta

Prévia do material em texto

Matemática Discreta
Professor conteudista: Edson Tiharu Tsukimoto
Sumário
Matemática Discreta
Unidade I
1 TEORIA DOS CONJUNTOS ................................................................................................................................1
1.1 Definições na teoria dos conjuntos .................................................................................................2
1.2 Exemplos .....................................................................................................................................................4
2 PRINCÍPIO DA INCLUSÃO-EXCLUSÃO ..................................................................................................... 13
2.1 Princípio da inclusão-exclusão (PIE) (para dois conjuntos) ................................................ 13
2.2 Princípio da inclusão-exclusão (PIE) (caso geral) ................................................................. 13
2.3 Exemplos .................................................................................................................................................. 14
3 ANÁLISE COMBINATÓRIA ............................................................................................................................. 17
3.1 O princípio fundamental da contagem (para dois conjuntos finitos) ............................ 17
3.1.1 Exemplos .................................................................................................................................................... 17
3.2 Princípio fundamental da contagem (para n conjuntos finitos) ...................................... 19
3.3 Aplicações do princípio fundamental da contagem .............................................................. 21
3.3.1 Arranjo com repetição (ARn,k) ............................................................................................................. 21
3.3.2 Arranjo sem repetição (An,k) ............................................................................................................... 24
3.3.3 Permutação (Pn) ...................................................................................................................................... 27
3.3.4 Permutação com elementos repetidos .......................................................................................... 30
3.3.5 Permutações circulares ......................................................................................................................... 34
3.3.6 Combinação ( Cn,k) ................................................................................................................................... 36
Unidade II
4 O PRINCÍPIO DA CASA DO POMBO (OU PCP) ...................................................................................... 41
4.1 Formulações ........................................................................................................................................... 41
4.2 Exemplos .................................................................................................................................................. 42
5 O PRINCÍPIO DE INDUÇÃO FINITA ............................................................................................................ 46
5.1 Introdução ............................................................................................................................................... 46
5.2 Princípio de Indução Finita (PIF fraco) ........................................................................................ 48
5.3 Princípio de Indução Finita (PIF) – versão conjuntista .......................................................... 49
5.4 Exemplos – (PIF fraco) ........................................................................................................................ 50
5.5 Princípio de Indução Finita Forte (PIF forte) ............................................................................. 54
5.6 Exemplos (PIF forte) ............................................................................................................................ 55
6 RECURSÃO ......................................................................................................................................................... 59
6.1 Definições ................................................................................................................................................ 59
6.2 Exemplos .................................................................................................................................................. 60
6.3 Conjuntos definidos por recursão ................................................................................................. 67
6.4 Cadeias ...................................................................................................................................................... 68
6.4.1 Exemplos .................................................................................................................................................... 69
6.5 A Torre de Hanói ................................................................................................................................... 70
6.5.1 Alguns resultados ................................................................................................................................... 72
1
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Unidade I5
10
15
20
25
30
35
1 TEORIA DOS CONJUNTOS
Linguagem
Para uma introdução às noções básicas de teoria dos 
conjuntos, necessitaremos de uma linguagem apropriada, cujos 
símbolos serão os símbolos da lógica e os símbolos próprios da 
teoria dos conjuntos, que listamos a seguir:
I. Símbolos da lógica
• ¬ (lê-se “não”).
• ∧ (lê-se “e”).
• ∨ (lê-se “ou”).
• → (lê-se “implica” ou “se... então”).
• ↔ (lê-se “se e somente se”).
• ∀ (lê-se “para todo” ou “para qualquer”).
• ∃ (lê-se “existe”).
II. Símbolos da teoria dos conjuntos
• ∈ (lê-se “pertence”).
• ⊆ (lê-se “contido”).
• ∅ ou { } (lê-se “conjunto vazio”).
• ∪ (lê-se “união”).
• ∩ (lê-se “intersecção”).
2
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
• \ (lê-se “diferença”).
• ℘ (lê-se “partes”).
• × (lê-se “produto cartesiano”).
1.1 Definições na teoria dos conjuntos
Sejam A, B e C conjuntos quaisquer.
• C1. Igualdade:
— A = B (x ∈ A ↔ x ∈ B).
• C2. Inclusão:
— A ⊆ B ⇔ (x ∈ A → x ∈ B).
• C3. Conjunto vazio:
— ∀x(x ∉ ∅).
• C4. União:
— x ∈ A ∪ B ⇔ (x ∈ A ∨ x ∈ B).
• C5. Intersecção:
— x ∈ A ∩ B ⇔ (x ∈ A ∧ x ∈ B).
• C6. Diferença:
— x ∈ A \ B ⇔ (x ∈ A ∧ x ∉ B);
– ou seja, x ∈ A \ B ⇔ (x ∈ A ∧ ¬ (x ∉ B)).
• C7. Conjunto das partes (subconjuntos):
— x ∈ ℘(A) ⇔ x ⊆ A.
• C8. Produto cartesiano:
— 
A x B se A ou B
A x B a b a A b B se A e B
= = =
= ∈ ∧ ∈ ≠ ≠



φ φ φ
φ φ{( , ) : }
3
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Observação 1
Quando escrevemos explicitamente um conjunto, a ordem 
na qual os elementos aparecem não importa.
Por exemplo, os conjuntos {1, 2} e {2, 1} são iguais, mas 
atenção: a situação é diferente quando tratamos de pares 
ordenados: assim, (1, 2) ≠ (2, 1).
Observação 2
Não devemos escrever duas ou mais vezes o mesmo elemento 
em um conjunto.
Por exemplo, os conjuntos {1, 2, 2, 2}, {1, 1, 2, 2} e {1, 2} 
representam o mesmo conjunto, de forma que convencionamos 
não repetir elementos em um conjunto.
Observação 3
Se A ⊆ B, dizemos que A está contido emB, ou que B 
contém A, ou ainda, que A é um subconjunto de B. Note que 
qualquer conjunto é subconjunto de si próprio, ou seja, para 
qualquer conjunto A, temos que A ⊆ A.
Por exemplo, se A = {1, 2, 3, 4, 5}, então {1}, {1,2}, {1,3,5} 
e {2,3,4,5} são subconjuntos de A, mas {1,2,3,4,6}, {7,8,9} e 
{2,3,4,7} não são.
O conjunto das partes de um conjunto A é o conjunto de 
todos os subconjuntos do conjunto A, e é denotado por ℘(A).
Por exemplo, se A = {1, 2, 3} então φ (veja a observação 
4), {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, são todos os 
subconjuntos de A.
Então, ℘(A) = {φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
4
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Observação 4
O conjunto vazio φ é subconjunto de qualquer conjunto, ou 
seja, ∀A(φ ⊆ A).
Esse fato decorre da forma lógica da definição de subconjunto, 
pois φ ⊆ A ⇔ ∀x (x ∈ φ → x ∈ A). Assim, como x ∈ φ é sempre 
falso, a implicação é sempre verdadeira para qualquer conjunto 
A, mas cuidado, ∀A(φ ∈ A) não é sempre válida.
Observação 5
Embora nas teorias de conjunto usuais todo objeto seja um 
conjunto, nesta introdução intuitiva consideramos que existem 
objetos que não são conjuntos.
Por exemplo, com relação ao número 3, não terá sentido 
escrever x ∈ 3 ou x ⊆ A.
Observação 6
Se A é um conjunto finito, então |A| denota o número de 
elementos de A.
1.2 Exemplos
Exemplo 1
Assinale verdadeiro (V) ou falso (F):
3 12 3 4∈{ }, , , V
3 12 4 6∈{ }, , , F
3 12 3 4{ } ∈{ }, , , F
3 1 3 5{ } ∈ { } { } { }{ }, , V
3 3{ } ∈{ } F
3 3{ } ∈{ }{ } V
5
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
{ } { }3 3{ } ∈{ } F
{ } { }3 3{ } ∈ { }{ } V
3 12 3 4∈{ }{ , , }, F
3 12 3 4{ } ∈{ }{ , , }, F
{ } , , ,3 12 3 4{ } ∈{ } F
{ } , ,3 1 3 5{ } ∈ { } { } { }{ } F
{ },{ } , { },{ }3 5 1 3 5{ } ∈ { } { }{ } V
{ } { , , }3 13 5{ } ∈{ } F
{ } ,{{ }}, { }3 1 3 5{ } ∈{ } V
12 3 12 3 4, , { , , },{ } ∈{ } V
12 3 12 3 4, , , , ,{ } ∈{ } F
12 3 4 12 3 4, , , , , ,{ } ∈{ } F
12 3 4 12 3 4, , , { , , , }{ } ∈{ } V
{ , }, , , , ,12 3 4 12 3 4{ } ∈{ } F
{ , }, , { , , },12 3 4 12 3 4{ } ∈{ } F
{ , }, , { , , , }12 3 4 12 3 4{ } ∈{ } F
{ , }, , { },{ },{ },{ }12 3 4 1 2 3 4{ } ∈{ } F
{ , }, , { , },{ , }12 3 4 12 3 4{ } ∈{ } F
{ , }, , { , }, ,12 3 4 12 3 4{ } ∈ { }{ } V
φ ∈{ }12 3 4, , , F
φ φ∈{ }, , , ,12 3 4 V
φ φ∈{ }{ }, , , ,12 3 4 F
{ } , , ,φ ∈{ }12 3 4 F
{ } , , , ,φ φ∈{ }12 3 4 F
{ } { }, , , ,φ φ∈{ }12 3 4 V
6
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Exemplo 2
Assinale verdadeiro (V) ou falso (F):
3 12 3 4{ } ⊆ { }, , , V
3 1 3 5{ } ⊆ { } { } { }{ }, , F
3 12 3 4{ } ⊆ { }{ , , }, F
{ } , , ,3 12 3 4{ } ⊆ { } F
{ } , ,3 1 3 5{ } ⊆ { } { } { }{ } V
{ },{ } , { },{ }3 5 1 3 5{ } ⊆ { } { }{ } F
{ },{ } ,{ },{ },{ }3 5 1 3 5 7{ } ⊆ { }{ } V
{ } { , , }3 13 5{ } ⊆ { } F
{ } ,{{ }}, { }3 1 3 5{ } ⊆ { } F
{{ }} ,{{ }}, { }3 1 3 5{ } ⊆ { } V
12 3 12 3 4, , { , , },{ } ⊆ { } F
12 3 12 3 4, , , , ,{ } ⊆ { } V
12 3 4 12 3 4, , , , , ,{ } ⊆ { } V
12 3 4 12 3 4, , , { , , , }{ } ⊆ { } F
{ , }, , , , ,12 3 4 12 3 4{ } ⊆ { } F
{ , }, , { , , },12 3 4 12 3 4{ } ⊆ { } F
{ , }, , { , , , }12 3 4 12 3 4{ } ⊆ { } F
{ , }, , { },{ },{ },{ }12 3 4 1 2 3 4{ } ⊆ { } F
{ , }, , { , },{ , }12 3 4 12 3 4{ } ⊆ { } F
{ , }, , { , }, , , ,12 3 4 12 3 4 5 6{ } ⊆ { } V
7
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
{ , }, , { , }, ,12 3 4 12 3 4{ } ⊆ { }{ } F
φ ⊆ { }12 3 4, , , V
φ φ⊆ { }, , , ,12 3 4 V
φ φ⊆ { }{ }, , , ,12 3 4 V
φ ⊆ { }{{ }}, , ,{ , , , },2 3 5 12 3 4 7 V
{ } , , ,φ ⊆ { }12 3 4 F
{ } , , , ,φ φ⊆ { }12 3 4 V
{ } { }, , , ,φ φ⊆ { }12 3 4 F
Exemplo 3
Considere A = {1,2,3}; B = {3,4,5,6}; C = { 7 }; D = { 2,5,8}, 
E = { 1,5,7 }. Calcule:
a) (A ∩ B)∪ E.
b) (A ∩ B)∩ E.
c) ((B \ A)∩ E)\ D.
d) (((A \ B)\ E)∩ C)∩ D.
e) ((B \ A) ∩ (E \ D).
f) (B \ E) \ ((C \ D) ∩ (C \ E)).
Solução
a) A ∩ B = {3}.
— (A ∩ B)∩ E = {1,3,5,7}.
b) A ∪ B = {1,2,3,4,5,6}.
— (A ∪ B)∩ E = {1,5}.
8
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
c) B \ A = {4,5,6}.
— (B \ A)∩ E = {5}.
— ((B \ A)∩ E) \ D = φ.
d) A \ B = {1,2}.
— (A \ B)\ E = {2}.
— ((A \ B) \ E)∪ C = {2,7 }.
— (((A \ B)\ E)∪ C)∩ D = {2}.
e) B \ A = {4,5,6}.
— E \ D = {1,7}.
— (B \ A) ∩ (E \ D) = φ.
f) B \ E ={3,4,6}.
— C \ D = {7}.
— C \ E = φ.
— (C \ D) ∪ (C \ E) = {7}.
— (B \ E) \ ((C \ D) ∪ (C \ E)) = {3,4,6}.
Observação
Lembremos a notação para intervalos reais.
Sejam a, b ∈ IR (conjunto dos números reais). Então 
definimos:
• [a,b] = {x ∈ IR : a < x < b}.
• [a,b [ = {x ∈ IR : a < x < b}.
• ]a,b ] = {x ∈ IR : a < x < b}.
• ]a,b[ = {x ∈ IR : a < x < b}.
9
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
• [a, + ∞[ = {x ∈ IR : a < x}.
• ]a, + ∞[ = {x ∈ IR : a < x}.
• ]- ∞,b] = {x ∈ IR : x < b}.
• ]- ∞,b[ = {x ∈ IR : x < b}.
Exemplo 4
Considere A = [ 2, 7 ]; B = ] 4, 9 ]; C = ] 5, 8 [ e D = [ 1, 7 [. 
Calcule:
a) (D \ C)∩ B.
b) (A ∩ B)\C.
c) (C ∩ D) \ (A ∪ B).
Solução
a) D \ C = [1,5]
— (D \ C)∩ B = ]4,5].
b) A ∩ B = ]4,7]
— (A ∩ B) \ C = ]4,5].
c) C ∩ D = ]5,7[
— A ∪ B = [2,9]
— (C ∩ D) \ (A ∪ B) = φ.
Exemplo 5
Considere A = {1}; B = {1,2}; C = {1,2,3}; D = {1,2,3,4}. 
Calcule:
a) A x B
10
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
b) B x A
c) B x B
d) B x C
e) C x B
Solução
a) A x B = {1} x {1,2} = {(1,1),(1,2)}.
b) B x A = {1,2} x {1} = {(1,1),(2,1)}.
c) B x B = {1,2} x {1,2} = {(1,1),(1,2),(2,1),(2,2)}.
d) B x C = {1,2} x {1,2,3} = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)}.
e) C x B = {1,2,3} x {1,2} = {(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)}.
Exemplo 6
Considere A = {1}; B = {1,2}; C = {1,2,3}; D = {1,2,3,4}. 
Calcule:
a) ℘(A).
b) ℘(B).
c) ℘(C).
d) ℘(D).
e) ℘(φ).
f) ℘(℘(φ)).
Solução
a) ℘(A) = {φ, {1}}.
b) ℘(B) = {φ, {1}, {2}, {1,2}}.
c) ℘(C) = {φ, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.
11
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
d) ℘( )
,{ },{ },{ },{ },{ , },{ , },{ , },{ , },{ , },
{ , }
D =
φ 1 2 3 4 12 13 14 2 3 2 4
3 4 ,,{ , , },{ , , },{ , , },{ , , },{ , , , },12 3 12 4 13 4 2 3 4 12 3 4






.
e) ℘(φ) = {φ}.
f) ℘(℘(φ)) = {φ,{φ}}.
Observação
Lembrando que |A| denota o número de elementos de um 
conjunto finito A, no exemplo acima percebemos que:
• |A| = 0 ⇒ |℘(A)| = 1.
• |A| = 1 ⇒ |℘(A)| = 2.
• |A| = 2 ⇒ |℘(A)| = 4.
• |A| = 3 ⇒ |℘(A)| = 8.
• |A| = 4 ⇒ |℘(A)| = 16.
Haveria alguma relação entre o número de elementos do 
conjunto A e o número de elementos do conjunto ℘(A) de suas 
partes?
Os exemplos acima sugerem a relação |℘(A)| = 2”, e, de fato, 
essa relação é válida. Então se A é um conjunto finito, temos 
que:
|A| = n ⇒ |℘(A)| = 2”.
Exemplo 7
Considere A ={1}; B = {2,3}; C = {4,5,6}. Calcule:
a) ℘(A x B).
b) ℘(A) x B.
12
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
c) ℘(B) x ℘(A).
d) (℘(A x B)) x A.
e) (℘(B) ∩ ℘(A)) \ (A ∩ B).
Solução
a) A x B = {(1,2),(1,3)}
 ℘(A x B) = {φ, {(1,2)}, {(1,3)}, {(1,2), (1,3)}}.
b) ℘(A) = {φ, {1}}
 ℘(A)x B = {(φ, 2), (φ, 3), ({1}, 2), ({1}, 3)}.
c) ℘(B) = {φ, {2}, {3}, {2,3}}
 ℘(A) = {φ, {1}}
 ℘ ℘( ) ( )
( , ),( ,{ }),({ }, ),({ },{ },({ }, )
({ },{ }),
B x A =
φ φ φ φ φ1 2 2 1 3
3 1 (({ , }, ),({ , },{ })2 3 2 3 1φ






.
d) A x B = {(1,2), (1,3)}
 ℘(A x B) = {φ, {(1,2)}, {(1,3)}, {(1,2), (1,3)}}.
(℘(A x B))xA = {(φ, 1), ({(1,2)}, 1), ({(1, 3)}, 1), ({(1,2), 
(1, 3)}, 1)}.
e) ℘(A) = {φ, {2}, {3}, {2,3}}
 ℘(A) = {φ, {1}}
 ℘(B) ∩ ℘(A) = {φ}
 A ∩ B = φ 
 (℘(B) ∩ ℘(A)) \ (A ∩ B)
13
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
2 PRINCÍPIO DA INCLUSÃO-EXCLUSÃO 
Dados dois conjuntos A e B, podemos afirmar que 
|A ∪ B| = |A| + |B|? 
Não! Basta ver este exemplo:
Seja A = { 1, 2, 3, 4, 5 } e B = { 2, 4, 6, 8 }. Então |A ∪ B| 
= {1, 2, 3, 4, 5, 6, 8}
Temos então que |A ∪ B| = 7, mas |A| + |B| = 5 + 4 = 9, e 
portanto |A ∪ B| ≠ |A| + |B|
É fácil perceber que a igualdade |A ∪ B| = |A| + |B| vale se e 
somente se |A ∪ B| = φ ou seja, a igualdade |A ∪ B| = |A| + |B| não 
é válida em geral porque temos que “descontar” a intersecção 
A ∩ B. É isso que diz o Princípio da Inclusão-Exclusão (PIE).
2.1 Princípio da inclusão-exclusão (PIE) (para 
dois conjuntos)
“Sejam A e B dois conjuntos. Então: |A ∪ B| = |A| + |B| - |A ∩ B|“
No nosso exemplo acima, se A = { 1, 2, 3, 4, 5 } e 
B = { 2, 4, 6, 8 }, então pelo PIE:
|A ∪ B| = |A| + |B| - |A ∩ B| = 5 + 4 - 2 = 7
No caso geral, teremos:
2.2 Princípio da inclusão-exclusão (PIE) (caso 
geral) 
A A A A A A Ai
i n
i
i n
i j
i j n
i j k
1 1 1
1
≤ ≤ ≤ ≤ ≤ < ≤
= − ∩ + ∩ ∩ − −∑ ∑ | | | | | | .......( )nn i
i ni j k n
A+
≤ ≤≤ < < ≤
∑ 1
11
.

14
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
A expressão acima pode assustar a princípio, mas vamos 
utilizar o princípio da inclusão-exclusão nos casos particulares 
n = 3 e n = 4 e logo perceberemos uma regularidade (faça depois 
o caso n = 5). 
Princípio da inclusão-exclusão (para três conjuntos)
| | | | | | | | | | | | | | | |A B C A B C A B A C B C A B C∪ ∪ = + + − ∩ − ∩ − ∩ + ∩ ∩
Princípio da inclusão-exclusão (para quatro 
conjuntos)
A B C D A B C D A B A C A D B C B D C D
A B C A B D A C D
∪ ∪ ∪ = + + + − ∩ − ∩ − ∩ − ∩ − ∩ − ∩ +
+ ∩ ∩ + ∩ ∩ + ∩ ∩ ++ ∩ ∩ − ∩ ∩ ∩B C D A B C D
2.3 Exemplos
Exemplo 1
Em um grupo com 42 turistas, todos falam inglês ou francês. 
Sabe-se que 35 falam inglês e 18 falam francês. Quantos falam 
ambas as línguas?
Solução
Seja E = conjunto das pessoas que falam inglês 
e F = conjunto das pessoas que falam francês
Então pelo princípio da inclusão-exclusão (PIE):
| | | | | | | | | | | |E F E F E F E F E F∪ = + − ∩ ⇔ = + − ∩ ⇔ ∩ =42 35 183 11
Portanto, 11 falam ambas a s línguas.
15
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Exemplo 2
Em um grupo com 24 pessoas, todos gostam de rock, jazz ou 
blues. Sabe-se que 14 gostam de rock, 17 de blues, 11 de rock 
e jazz, 9 de rock e blues, 13 de jazz e blues e 8 gostam dos três 
estilos. Quantas pessoas gostam de jazz ?
Solução
Seja R = conjunto das pessoas que gostam de rock
 J = conjunto das pessoas que gostam de jazz
 B = conjunto das pessoas que gostam de blues
Então, pelo princípio da inclusão-exclusão (PIE):
R J B R J B R J R B J B R J B
J J
∪ ∪ = + + − ∩ − ∩ − ∩ + ∩ ∩ ⇔
⇔ = + + − − − + ⇔ =24 14 17 9 11 13 8 18
Portanto, 18 pessoas gostam de jazz.
Exemplo 3
Uma pesquisa feita com 200 donas de casa revelou que 111 
preferem o detergente Alvo, 94 preferem o detergente Brancura, 
84 preferem o detergente Claro, 47 preferem os detergentes Alvo 
e Brancura, 43 preferem os detergentes Alvo e Claro, 32 preferem 
os detergentes Brancura e Claro e 4 preferem os detergentes 
Alvo, Brancura e Claro.
a) Quantas não preferem nenhum dos três detergentes 
citados?
b) Quantos preferem apenas o detergente Brancura ?
16
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Solução
Considere os conjuntos:
A = conjunto das donas de casa que preferem o detergente 
Alvo
B = conjunto das donas de casa que preferem o detergente 
Brancura
C = conjunto das donas de casa que preferem o detergente 
Claro
Então, pelo princípio da inclusão-exclusão (PIE):
A B C A B C A B A C B C A B C
A B C
∪ ∪ = + + − ∩ − ∩ − ∩ + ∩ ∩ ⇔
⇔ ∪ ∪ = + + − − − + ⇔111 94 84 47 43 32 4 AA B C∪ ∪ = 171
a) Como a pesquisa envolveu 200 donas de casa pessoas e 
171 preferiam um dos três detergentes citados, concluímos 
que 200 – 171 = 29 donas de casa não preferem nenhum 
dos três detergentes citados.
b) Quero calcular |B \ A ∪ C|, então:
B A C B B A C B B A B C
B B A B C B A B C
\ ( ) ( ) ( )
( ) | |( ) ( ) ( )
∪ = − ∩ ∪ = − ∩ ∪ ∩ =
− ∩ + ∩ − ∩ ∩ ∩( ))=
= − ∩ + ∩ − ∩ ∩( )
− ∩ − ∩ + ∩ ∩ = − − + =
B B A B C B A C
B B A B C B A C
( ) | |( ) ( )
94 47 32 4 19
Portanto, 19 donas de casa preferem apenas o detergente 
Brancura.
17
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
3 ANÁLISE COMBINATÓRIA 
3.1 O princípio fundamental da contagem 
(para dois conjuntos finitos)
“Sejam A e B dois conjuntos tais que |A| = m e |B| = n, então 
|A x B| = m.n.”
Ou, de maneira informal:
“Se um processo de passagem de um estado R para um 
estado T pode ser dividido em duas etapas, de R para S e depois 
de S para T, de forma que a passagem de R para S pode ser 
executada de m formas distintas, e a passagem de S para T 
pode ser executada de n formas distintas, então o processo de 
passagem de um estado R para um estado T pode ser feito de 
m.n maneiras distintas.”
Observação
Qual a relação entre os enunciados formal e informal?
No enunciado formal, o conjunto A corresponde às 
passagens possíveis do estado R para o estado S, e o conjunto 
B corresponde às passagens possíveis do estado S para o estado 
T.
3.1.1 Exemplos
Exemplo 1
Existem 4 estradas ligando São Paulo ao Rio de Janeiro e 
3 estradas ligando Rio de Janeiro à Bahia. Quantos caminhos 
distintos podem ser feitos de São Paulo à Bahia, passando pelo 
Rio de Janeiro?
18
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Solução
Como posso fazer a viagem de São Paulo ao Rio de 
Janeiro de 4 formas distintas, e depois fazer a viagem do 
Rio de Janeiro à Bahia de 3 formas distintas, então pelo 
princípio fundamental da contagem, posso fazer a viagem 
de São Paulo à Bahia, passando pelo Rio de Janeiro, de 
4.3 = 12 formas distintas.
 
SP à BASP ao RJ
34
 
Exemplo 2
Uma mulher possui 5 saias e 8 blusas. De quantas formas 
distintas ela pode se vestir usando uma saia e uma blusa?
Solução
Ela tem 5 escolhas para a saia e 8 escolhas para a 
blusa, logo, peloPFC, ela pode se vestir de 5.8 = 40 
formas distintas.
 blusasaia
85
O princípio fundamental da contagem pode ser generalizado 
para qualquer número finito de conjuntos:
19
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
3.2 Princípio fundamental da contagem (para 
n conjuntos finitos)
“Sejam A1, A2,........., Anconjuntos finitos e tais que |Ai| = mi, 
para i = 1,2,.........n, então |A1 x A2 x.........xAn| = m1, m2.........mn“.
Retomando os exemplos acima, teremos:
Exemplo 3
Existem 4 estradas ligando São Paulo ao Rio de Janeiro, 3 
estradas ligando Rio de Janeiro à Bahia e 2 estradas ligando 
Bahia a Sergipe. 
Quantos caminhos distintos podem ser feitos de São Paulo a 
Sergipe, passando pelo Rio de Janeiro e pela Bahia?
Solução
Como posso fazer a viagem de São Paulo ao Rio de Janeiro 
de 4 formas distintas, do Rio de Janeiro à Bahia de 3 formas 
distintas e da Bahia a Sergipe de 2 formas distintas, então, pelo 
princípio fundamental da contagem, posso fazer a viagem de 
São Paulo a Sergipe de 4.3.2 = 24 formas distintas.
 SP à BASP ao RJ
34 2
BA a SE
Exemplo 4
Uma mulher possui 5 saias, 8 blusas, 4 colares e 3 chapéus. 
De quantas formas distintas ela pode se vestir usando uma saia, 
uma blusa, um colar e um chapéu?
20
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Solução
Ela tem 5 escolhas para a saia, 8 escolhas para a blusa, 4 
escolhas para o colar e 3 escolhas para o chapéu, logo, pelo 
princípio fundamental da contagem, ela pode se vestir de 5.8.4.3 
= 480 formas distintas.
blusasaia
85 4
colar chapéu
3 
Exemplo 5
Uma agência bancária possui 7 portas. De quantas maneiras 
um cliente pode entrar e sair desse banco?
Solução
Consideramos cada par entrada/saída como uma maneira 
do cliente entrar e sair do banco. Existem 7 possibilidades para 
a escolha da porta de entrada, e, depois de entrar, ele possui 
novamente 7 possibilidades para a escolha da porta de saída. 
Portanto, pelo princípio fundamental da contagem, ele pode 
entrar e sair do banco de 7.7 = 49 maneiras.
77
Exemplo 6
Uma agência bancária possui 7 portas. De quantas maneiras 
um cliente pode entrar e sair desse banco se a porta de entrada 
não pode ser a mesma porta de saída ?
21
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Considere cada par entrada/saída como uma maneira do 
cliente entrar e sair do banco.
Solução
Existem 7 possibilidades para a escolha da porta de entrada, 
e depois de entrar, ele possui apenas 6 possibilidades para a 
escolha da porta de saída, já que não pode sair pela mesma 
porta que entrou. Portanto, pelo princípio fundamental 
da contagem, ele pode entrar e sair do banco de 7.6 = 42 
maneiras.
67
3.3 Aplicações do princípio fundamental da 
contagem
O princípio fundamental da contagem será a ferramenta 
básica para desenvolver várias técnicas de contagem, que 
apresentamos a seguir:
3.3.1 Arranjo com repetição (ARn,k) 
Seja S um conjunto com n elementos. Então o número 
de k-uplas (1 ≤ k ≤ n) ordenadas de elementos de S (que 
representamos por ARn,k) é dado por:
 
A nRnk
k
, =
Exemplo 1
Usando os algarismos 1, 2, 3, 4, 5, 6, 7 e 8, quantas senhas 
de 5 dígitos existem?
22
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Solução
Existem 8 possibilidades para o 1° dígito, 8 para 
o 2°, 8 para o 3° , 8 para o 4° e 8 para o 5°, portanto pelo 
princípio fundamental da contagem, podem ser construídas 
8.8.8.8.8 = 85 = 32768 senhas.
 
8 8 8 8 8
Exemplo 2
Uma prova-teste consta de 12 questões cujas alternativas 
são “verdadeiro” ou “falso”. De quantas formas diferentes essa 
prova pode ser respondida?
Solução
Existem 2 possibilidades para cada questão (“verdadeiro” ou 
“falso”), portanto, pelo princípio fundamental da contagem, a 
prova pode ser respondida de 212 maneiras.
2
questão 1 questão 2 questão 3 questão 10 questão 11 questão 12
2 2 • • • • • • • • • • • • • • • • 2 2 2
• • • • • • • • • • • • • • • •
Exemplo 3
Uma senha deve consistir de uma sequência de 4 números, 
escolhidos entre os algarismos 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9, que 
podem ser repetidos ou não. Quantas senhas distintas podem 
ser construídas?
23
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Solução
Existem 10 algarismos disponíveis, logo existem 10 
possibilidades para cada dígito. Portanto, pelo princípio 
fundamental da contagem, podem ser construídos 104 
senhas.
10 10 10 10
 
Exemplo 4
Cinco dados (cada um com seis faces numeradas de 1 até 
6) são lançados. Quantas sequências de resultados distintos 
existem?
Solução
Como um dado possui 6 lados, existem 6 possibilidades para 
cada jogada. Portanto, pelo princípio fundamental da contagem, 
podem ser construídos 65 sequências.
 
6 6 6 6 6
Exemplo 5
Em certo jogo de computador, um objeto está parado na 
origem de um sistema de coordenadas e ele pode mover-se 
apenas para cima ou para a direita, com apenas um movimento 
por vez. Após 4 passos, quantas trajetórias distintas são 
possíveis?
24
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Solução
O objeto tem apenas duas alternativas de movimento, para 
cima e para a direita. Portanto, pelo princípio fundamental da 
contagem, após 4 passos, o objeto pode descrever 24 trajetórias.
 
2 2 2 2
Exemplo 6
Sejam A e B conjuntos tais que |A| = n e |B| = k. Quantas 
funções ƒ : A → B existem ?
Solução 
Para uma enumeração a1, a2, ................, an, qualquer dos 
elementos do conjunto A, temos que existem k possibilidades para 
o valor de ƒ(a1), k possibilidades para o valor de ƒ(a2),................., 
e k possibilidades para o valor de ƒ(an). Portanto, pelo princípio 
fundamental da contagem, existem kn funções.
 
k
ƒ(a1) ƒ(a2) ƒ(a3) ƒ(an-1) ƒ(an)
k k k k
• • • • • • • • • • • • • • • •
• • • • • • • • • • • • • • • •
3.3.2 Arranjo sem repetição (An,k) 
Seja S um conjunto com n elementos. Então o número de 
k-uplas (1 ≤ k ≤ n) ordenadas de elementos de S sem repetição 
é dado por :
A
n
n knk,
!
( )!
=
−
25
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Exemplo 1
Utilizando os algarismos 1,2,3,4,5,6 e 7, quantos números 
de 3 dígitos existem se não podem haver algarismos 
repetidos?
Solução
Existem 7 possibilidades pra o 1° dígito, 6 para o 2° e 5 para 
o 3°. Portanto, pelo princípio fundamental da contagem, podem 
ser construídas 7.6.5 = 210 números.
Observe que 
7
7 3
7
4
7 6 5 210
!
( )!
!
!
. .
−
= = =
 2º dígito1º dígito
67 5
3º dígito
Exemplo 2
Utilizando os algarismos 0, 2, 3, 4, 5, 6, 8 e 9, quantas 
senhas de 5 dígitos existem se não podem haver algarismos 
repetidos?
Solução
Existem 8 possibilidades pra o 1° dígito, 7para o 
2°, 6 para o 3°, 5 para o 4° e 4 para o 5°. Portanto, pelo 
princípio fundamental da contagem, podem ser construídas 
8.7.6.5.4 = 6729 senhas.
Observe que 
8
8 5
8
3
8 7 6 5 4 6729
!
( )!
!
!
. . . .
−
= = =
26
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
 
2º dígito1º dígito
78 6
3º dígito 4º dígito
5
5º dígito
4
 
Exemplo 3
Um torneio de futebol de salão conta com 12 times. Quantas 
são as possibilidades para os quatro primeiros colocados ?
Solução 
Existem 12 possibilidades pra o 1° lugar, 11 para o 2°, 10 
para o 3° e 9 para o 4°. Portanto, pelo princípio fundamental da 
contagem, existem 12.11.10.9 = 11880 possibilidades.
Observe que 
12
12 4
12
8
12 11 10 9 11880
!
( )!
!
!
. . .
−
= = =
 
vicecampeão
1112 10
3º lugar 4º lugar
9
Exemplo 4
Sejam A e B conjuntos tais que |A| = n e |B| = k, onde n < k. 
Quantas funções injetoras ƒ : A → B existem?
Solução
Para uma enumeração a1, a2, ................, an qualquer dos 
elementos do conjunto A, temos que existem k possibilidades 
para o valor de ƒ(a1), k - 1 possibilidades para o valor de ƒ(a) 
27
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
(pois como ƒ é injetora, não pode haver valores iguais para 
argumentos diferentes),................., e k - n+1) possibilidades 
para o valor de ƒ(an). Portanto, pelo princípio fundamental da 
contagem, existem k.(k - 1)......(k - n + 1) funções injetoras.
Observe que 
k
k n
k k k n k n
k n
k k
!
( )!
.( )........( ).( )!
( )!
.( )......
−
= − − + −
−
= −1 1 1 .....( )k n− +1
k
ƒ(a1) ƒ(a2) ƒ(a3) ƒ(an-1) ƒ(an)
k-1 k-2 k-n+2 k-n+1
• • • • • • • • • • • • • • • •
• • • • • • • • • • • • • • • •
3.3.3 Permutação (Pn)
Seja S um conjunto com n elementos. O número de n-uplas 
ordenadas de elementos de S sem repetição é dado por :
 
P nn = !
Observação
Podemos notar que uma permutação é um caso particular 
de um arranjo sem repetição quando k = n.
Exemplo 1
Cinco pessoas devem formar uma fila. Quantas filas distintas 
podem ser formadas? 
Solução
Existem 5 possibilidades pra o 1° lugar, 4 para o 2°, 3 para o 
3°, 2 para o penúltimo e 1 para o último lugar. Portanto, existem 
5.4.3.2.1 = 5! = 120 filas.
28
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
5 4 3 2 1
Observação
Um anagrama de uma palavra é qualquer reordenação das 
letras da palavra original, tenha essa reordenação sentido ou 
não (a palavra original também é considerada um anagrama 
de si própria. Por exemplo, “gol, glo, lgo, log, ogl, olg” são os 
anagramas da palavra “gol”).
Exemplo 2
Quantos anagramas possui a palavra “louca”?
Solução
Como são 5 letras, existem 5 ! = 120 anagramas.
Observação
Note que, na palavra “louca”, as letras são todas distintas. 
Se ocorrer repetição de letras, não podemos utilizar a fórmula 
acima. Veremos a seguir como tratar desse caso.
Exemplo 3
Sejam A e B conjuntos tais que |A| = |B| = n. Quantas funções 
bijetoras ƒ : A → B existem?
Solução
Para uma enumeração a1, a2, ................, an qualquer dos 
elementos do conjunto A, temos que existem n possibilidades 
para o valor de ƒ(a1), n-1 possibilidades para o valor de ƒ(a2) 
29
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
(pois como ƒ é bijetora, não pode haver valores iguais para 
argumentos diferentes),................., 2 possibilidades para o valor 
de ƒ(an-1) e 1 possibilidade para o valor de ƒ(an). Portanto, pelo 
princípio fundamental da contagem, existem n! = n.(n-1)........2.1 
funções bijetoras.
n
ƒ(a1) ƒ(a2) ƒ(a3) ƒ(an-1) ƒ(an)
n-1 n-2 2 1
• • • • • • • • • • • • • • • •
• • • • • • • • • • • • • • • •
Exemplo 4
Um grupo de 10 pessoas, entre elas Madalena e Rodrigo, que 
são namorados, deve ficar em fila. Quantas filas distintas podem 
ser formadas se:
a) Madalena e Rodrigo ficarem juntos? 
b) Madalena e Rodrigo, após uma briga, ficarem separados? 
Solução
a) Um truque básico neste tipo de problema consiste em 
“amarrar” as duas pessoas que devem ficar juntas e 
considerá-las como uma única pessoa. Assim, Madalena 
e Rodrigo transformaram-se em um ente único, de forma 
que podemos pensar que as 10 pessoas tornaram-se 9. 
Poderíamos pensar, então, que a resposta seria 9!, mas 
assim esqueceríamos que Madalena e Rodrigo podem 
trocar de lugar entre si de 2! maneiras. A resposta correta 
é, portanto, 2!.9! filas.
b) No total, independentemente do fato de Madalena e 
Rodrigo ficarem juntos ou separados, existem 10! filas 
possíveis. Pelo item acima, como em 2!.9! filas estão 
30
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
juntos, nas filas restantes devem estar separados. Portanto 
existem 10! – 2!.9! filas.
Exemplo 5
Um grupo formado por 12 pessoas, entre elas 5 brasileiros, 
deve formar uma fila. Quantas filas distintas podem ser formadas 
se os brasileiros ficarem juntos?
Solução
Como no exemplo anterior, vamos “amarrar” os 5 brasileiros 
e considerá-los como se fossem uma única pessoa, de forma 
que podemos considerar que agora são apenas 8 pessoas (os 
7 restantes mais o “brasileirão monstro”). Além disso, como 
os 5 brasileiros podem trocar de lugar entre si de 5! maneiras, 
poderão ser formadas 5!.8! filas distintas.
3.3.4 Permutação com elementos repetidos
Seja S um conjunto com n elementos e S1 = {a1, ............., ak} 
um subconjunto de S, onde 1 ≤ k ≤ n. O número de n-uplas 
ordenadas de elementos de S sem repetição, mas considerando 
os elementos a1, ............. ak indistinguíveis entre si para uma 
determinada situação (ou seja, podem ser considerados iguais), 
é dado por:
P
n
kn
k = !
!
Observação 1
Tomemos por exemplo a palavra AMA.
Provisoriamente vamos considerar as duas letras “A” distintas 
entre si, e para distingui-las, vamos chamá-las de A1 e A2.
31
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Considerando então A1 e A2 distintas, teríamos 3! Permutações, 
a saber:
A1 M A2
A2 M A1
A1 A2 M
A2 A1 M
M A1 A2
M A2 A1 
Porém, como A1 e A2 são na realidade indistinguíveis, sabemos 
que A1 M A2 e A2 M A1 são a mesma palavra, da mesma forma 
que A1 A2 M e A2 A1 M, bem como M A1 A2 e M A2 A1.
Devemos então “descontar” as palavras repetidas. Como a 
letra “A” aparece duas vezes, temos que o número de anagramas, 
nesse caso, é dado por: P3
2 3
2
3= =!
!
Exemplo 1
Quantos anagramas possui a palavra “sarabanda”?
Solução
No total temos 9 letras, dentre as quais 4 letras “A”.
Portanto existem P9
4 9
4
15120= =!
!
 anagramas.
Observação 
A permutação com elementos repetidos pode ser generalizada 
para mais elementos repetidos. Assim, se em um conjunto S 
existem n1 elementos indistinguíveis entre si, outros n2 elementos 
indistinguíveis entre si,..........,nk elementos indistinguíveis entre 
sí, com n1 + n2 +.......+ nk = n (nesta definição consideramos a 
possibilidade de ni = 1), então o número de permutações de 
32
Unidade IRe
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
elementos de S, levando-se em conta a indistinguibilidade de 
alguns dos elementos será dado por:
 P
n
n n nn
n nk
k
1
1 2
,.... !
! . ! ........ !
=
Exemplo 2
Quantos anagramas possui a palavra “assassinato”?
Solução
No total temos 11 letras, dentre as quais 3 letras “A” e 4 
letras “S”
Portanto existem P11
34 11
3 4
277200,
!
! . !
= = anagramas.
Exemplo 3
Quantos anagramas possui a palavra “inconstitucional”?
Solução
No total temos 16 letras, dentre as quais 2 letras “c”, 3 
letras “i”, 3 letras “n”, 2 letras “o” e 2 letras “t”. Portanto existem 
P16
222 33 16
2 2 2 3 3
, , , , !
! . ! . ! . ! . !
= anagramas.
Exemplo 4
Um comerciante vende apenas três tipos de pizza: mussarela, 
atum e calabresa. De quantas formas uma pessoa pode comprar 
5 pizzas ?
Solução
Vamos utilizar o seguinte truque para a solução deste problema:
33
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
No esquema abaixo, devemos distribuir 5 pontinhos nas 
divisões separadas por uma barra. A 1ª divisão representa as 
pizzas de mussarela, a 2ª divisão as pizzas de atum e a 3ª divisão 
as pizzas de calabresa. O número de pontinhos em cada divisão 
representa o número de pizzas do tipo correspondente. 
Por exemplo, observe as situações abaixo:
Situação 1: foram escolhidas 2 pizzas de mussarela, 1 de 
atum e 2 de calabresa.
Situação 2: foram escolhidas 1 pizza de mussarela, nenhuma 
de atum e 4 de calabresa.
Situação 3: todas as 5 pizzas escolhidas foram de atum.
mussarela atum calabresa
situação 1 • • • • •
mussarela atum calabresa
situação 2 • • • • •
mussarela atum calabresa
situação 3 • • • • •
Percebemos, então, que cada configuração representa uma 
diferente escolha das 5 pizzas, de forma que se quero saber de 
quantas formas posso escolher 5 pizzas entre mussarela, atum 
e calabresa, basta saber quantas configurações do tipo acima 
existem.
34
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
E quantas configurações existem? Basta notar que cada 
configuração é uma permutação de 7 símbolos, dos quais 5 são 
pontinhos e 2 são barras, de forma que utilizaremos a fórmula 
da permutação com elementos repetidos.
Portanto, podemos escolher as pizzas de 
7
2 5
21
!
!. !
= maneiras 
diferentes.
3.3.5 Permutações circulares
Definição
Seja S um conjunto com n elementos, e sejam 
α = (a1, a2............., an) e β = (b1, b2............., bn) n-uplas ordenadas de 
elementos de S sem repetição.
Então a1 = bj0 para algum j0. 
Dizemos então que α e β são equivalentes se 
a1+k (mod n) = bj0+k (mod n), ∀k ∈ N.
Exemplo
Seja S = {a,b,c}. Então (a,b,c), (c,a,b), (b,c,a) são todos 
equivalentes entre si.
Seja S = {a,b,c,d}. Então (b,d,a,c), (c,b,d,a), (a,c,b,d), (d,a,c,b) 
são todos equivalentes entre si.
Cálculo de permutações circulares
Seja C um conjunto maximal de n-uplas ordenadas de S, tais 
que duas n-uplas quaisquer de C não sejam equivalentes (cada 
n-upla de C será chamada de uma permutação circular de S). 
Então | C | = (n – 1)!
35
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Observação 1 
Embora a definição pareça complicada, a ideia por trás é 
simples: queremos dispor n elementos sobre uma circunferência. 
Por exemplo, queremos dispor 5 pessoas em uma mesa circular. 
A situação que descrevemos é quando não importa a particular 
cadeira em que a pessoa está sentada, mas sim as pessoas 
que estão sentadas do seu lado esquerdo e direito, embora 
consideremos direita e esquerda distintos.
Exemplo1
Queremos dispor 13 pessoas em uma mesa circular. De 
quantas maneiras isso pode ser feito?
Solução 
Como são 13 pessoas, então podemos dispô-las de (13 – 1)! 
= 12! maneiras.
Exemplo 2
Um grupo de 20 crianças precisa sentar em roda para uma 
brincadeira. De quantas formas isso pode ser feito ? 
Solução 
Como são 20 crianças, então podemos dispô-las de (20 – 1)! 
= 19! maneiras.
Exemplo 3
Queremos fazer um colar utilizando 6 tipos de pedras: 
diamante, esmeralda, rubi, opala, safira e ametista, e as pedras 
devem ficar distribuídas de forma equidistante na corda. Quantos 
colares podem ser feitos?
36
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Solução
Considerando o colar fixo em cima de uma mesa, 
como são 6 tipos de pedra, então poderíamos dispô-las de 
(6 – 1)! = 5 ! = 120 maneiras.
No entanto, como podemos virar o colar, metade 
das configurações serão repetidas, então podemos fazer 
5
2
120
2
60
! = = colares.
Observação 2 
Vamos ressaltar a diferença entre os exemplos 1 e 2 e o 
exemplo 3.
Nos exemplos 1 e 2, vemos o círculo apenas “de cima” ou 
apenas “de baixo”.
Já no exemplo 3, podemos ver o círculo (ou seja, o colar) pela 
“frente” ou por “trás”, e isso evidencia o que quisemos dizer com 
“embora consideremos direita e esquerda distintos“ que talvez 
tenha passado despercebido na observação 1.
Essa diferença de tratamento deve ser feita de acordo com a 
situação real envolvida no problema.
3.3.6 Combinação ( Cn,k)
Seja S um conjunto com n elementos. O número de 
subconjuntos de S com k elementos (1 ≤ k ≤ n) é dado 
por:
C
n
n k knk,
!
( )! . !
=
−
37
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Observação 1
Note que, para arranjos e permutações, a ordem dos 
elementos é essencial, enquanto na combinação não. Assim, 
por exemplo, em uma fila, as pessoas presentes são as mesmas, 
mas se a posição delas for mudada, consideramos que são filas 
distintas.
Em um outro exemplo, se com os algarismos 1,2,3,4,5,6,7,8,9 
queremos formar números de 4 dígitos, então os números 
2481 e 8241 são distintos, embora ambos utilizem os mesmos 
algarismos.
Já no caso de uma comissão, importa quem são as pessoas, 
e não a ordem em que foram escolhidas.
Observação 2
Como chegamos à essa fórmula?
Consideremos um conjunto S com n elementos e k um 
natural tal que 1 < k < n. Sabemos que o número de k-uplas 
ordenadas sem repetição é dado por 
 
 A
n
n knk,
!
( )!
=
−
Por outro lado, um pouco de reflexão mostra que podemos 
chegar ao conjunto de k-uplas ordenadas sem repetição da 
seguinte forma: escolhemos um subconjunto R de S com k 
elementos. Então existirão k! permutações com elementos 
de R.
Ora, se existem C subconjuntos de S com k elementos, e cada 
um desses subconjuntos gera k! permutações, então o número 
total de k-uplas ordenadas sem repetição de elementos de S 
38
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
será dado por C.k!, mas sabemos que esse número também é 
dado por A
n
n knk,
!
( )!
=
−
Portanto, C k
n
n k
. !
!
( )!
=
−
, ou seja, C
n
n k k
=
−
!
( )! . !Observação 3
A expressão 
n
n k k
!
( )! . !− pode também ser abreviada por 
n
k



 , 
e essa expressão é chamada de número binomial.
Exemplo 1
Uma classe com 10 alunos precisa formar uma comissão 
com três representantesde classe. Quantas comissões existem?
Solução
Existem C10 3
10
3
10
10 3 3
10
7 3
10 9 8
3 2
120,
!
( )! !
!
! . !
. .
.
= 



=
−
= = = 
comissões.
Exemplo 2
Um concurso de Miss Universo conta com a participação 
de moças de 50 países. Quantas possibilidades existem para o 
primeiro, segundo e terceiro lugares?
Solução 
Escrevemos este exemplo aqui para evidenciar que, 
neste caso, não devemos usar combinações, já que devemos 
escolher 3 moças. Mas, diferente de uma comissão, a 
ordem da escolha é importante. Por exemplo, Miss Brasil 
em primeiro, Miss Venezuela em segundo e Miss Argentina 
em terceiro é uma situação diferente de Miss Venezuela 
em primeiro, Miss Brasil em segundo e Miss Argentina em 
terceiro.
39
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Assim, a solução correta do problema é 
A30 3
30
30 3
30
27
30 29 28,
!
( )!
!
!
. .=
−
= =
 
2º lugar1º lugar
4950 48
3º lugar
Exemplo 3
De um grupo com 9 pessoas, queremos escolher 6 
para formar um time de vôlei. Quantos times podem ser 
formados? 
Solução
Podem ser formados C96
9
6
9
9 6 6
9
3 6
9 8 7
3 2
48,
!
( )! . !
!
! . !
. .
.
= 



=
−
= = = 
times.
Exemplo 4
Um time de futebol de salão é constituído por quatro 
jogadores e mais um goleiro. De um grupo com 12 pessoas, 
apenas Marcos joga no gol e, portanto, deve fazer parte de 
qualquer time escalado. Nessas condições, quantos times podem 
ser formados? 
Solução 
Como Marcos deve estar presente em todos os times, 
separamos Marcos e já o colocamos em um time. Como 
Marcos já está no time, resta escolher mais 4 das 11 pessoas 
restantes.
40
Unidade I
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
nd
ro
 -
 D
ia
gr
am
aç
ão
: F
ab
io
 -
 2
2/
02
/1
1
Portanto, podemos formar
 C114
11
4
11
11 4 4
11
7 4
1110 9 8
4 3 2
330,
!
( )! . !
!
! . !
. . .
. .
= 



=
−
= = = times.
Exemplo 5
Um barman tem à sua disposição 9 tipos de bebida, e ele 
pretende fazer um drink misturando 5 delas. Quantos drinks ele 
pode produzir, se duas, entre essas 9 bebidas, não podem ser 
misturadas por resultarem uma mistura tóxica?
Obs.: aqui supomos que a ordem em que as bebidas são 
misturadas é indiferente.
Solução
Aqui usaremos um truque muito utilizado em análise 
combinatória. A ideia é subtrair o número de drinks proibidos 
do total de drinks:
Quantidade total de drinks (sem restrição): 
9
5




Quantidade de drinks proibidos: 
9 2
5 2
7
3
−
−




= 



Portanto, o número de drinks pedidos será dado por:
9
5
7
3
9
5 4
7
4 3
126 35 91




− 



= − = − =!
! . !
!
! . !