14 - O princípio da Inclusão e Exclusão

Prévia do material em texto

5/16/2019 1Análise Combinatória - Princípio da Inclusão e Exclusão
Professor: Luiz Augusto Laranjeira
luiz.laranjeira@gmail.com
AULA 14
Matemática Discreta 1
O Princípio da Inclusão e Exclusão
5/16/2019 2Análise Combinatória - Princípio da Inclusão e Exclusão
Nesta aula estamos interessados em 
obter uma fórmula que nos dê o número 
total dos elementos da união de um 
número finito de conjuntos.
OBJETIVO
5/16/2019 3Análise Combinatória - Princípio da Inclusão e Exclusão
ESTUDO DE CASO 1
Numa classe de 30 alunos, 14 falam inglês, 5 falam alemão e 3 falam
inglês e alemão. Quantos alunos falam inglês e/ou alemão?
{ A, n(A) } = conjunto dos alunos que falam inglês e o seu número
{ B, n(B) } = conjunto dos alunos que falam alemão e o seu número
Dados n(A), n(B) e n(A∩B), desejamos saber o valor de n(A∪B).
n(A∪B) = n(A) + n(B) – n(A∩B) porque subtrair n(A∩B)?
Porque quando somamos n(A) e n(B) contamos n(A∩B) duas vezes.
Logo: n(A∪B) = 14 + 5 – 3 = 16
A B
A∩B
5/16/2019 4Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 1
Dentreosnúmerosde1a3600inclusive,quantossãodivisíveispor3oupor7?
3600/3 = 1200sãodivisíveispor3 3600/7 = 514sãodivisíveispor7
3600/21 = 171sãodivisíveispor3epor7
Quando somamos 1200 + 514 contamos duas vezes os que sao divisíveis por 3 e
por 7, isto é, aqueles divisíveis por 21.
Assim, a resposta correta N ao problema proposto é:
1200 + 514 – 171 = 1543
𝑁 = 1543
Numa classe de 30 alunos, 14 falam inglês, 5 falam alemão e 7 falam
francês. Sabendo-se que 3 falam inglês e alemão, 2 falam inglês e
francês, 2 falam alemão e francês e 1 fala as três línguas, determinar
o número daqueles que falam pelo menos uma destas três línguas.
n(A) = 14; n(B) = 5; n(C) = 7; n(A∩B) = 3; n(A∩C) = 2; n(B∩C) = 2;
n(A∩B ∩C) = 1.
Pelo diagrama vê-se que a resposta
correta é dada por:
14 + 5 + 7 – 3 – 2 – 2 + 1 = 20 isto é,
n(A) + n(B) + n(C) – n(A∩B) – n(A∩C) – n(B∩C) + n(A∩B ∩C)
5/16/2019 5Análise Combinatória - Princípio da Inclusão e Exclusão
ESTUDO DE CASO 2
A B
C
2
1
1 1
1
4
10
5/16/2019 6Análise Combinatória - Princípio da Inclusão e Exclusão
ESTUDO DE CASO 2 (cont.)
n(A) + n(B) + n(C) – n(A∩B) – n(A∩C) – n(B∩C) + n(A∩B ∩C) (1)
Para provarmos que a formula(1) está correta precisamos mostrar que ela conta
um dado elemento exatamento uma vez. Vamos analisar 3 casos distintos:
1) Se um elemento pertence a somente 1 dos conjuntos (A, por exemplo) a formula o
considerará somente 1 vez, em n(A), e nenhuma vez nos outros termos.
2) Se um elemento pertence a 2 conjuntos (i.e. A e B) a formula o considerará 1 vez em
n(A), outra vez em n(B) e uma contribuição negativa em n(A∩B), dando 1+1–1 = 1.
3) Se um elemento pertence aos 3 conjuntos teremos contribuições
positivas de n(A), n(B) e n(C), negativas de n(A∩B), n(A∩C)
e n(B∩C) , e uma positiva de n(A∩B ∩C), resultando em:
1 + 1 + 1–1–1–1 + 1 = 1
A B
C
5/16/2019 7Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 2
Dentre os números de 1 a 3600 inclusive, quantos são divisíveis por 3, 5
ou por 7?
n(A) = 3600/3 = 1200 n(B) = 3600/5 = 720 n(C) = 3600/7 = 514
n(A∩B)= 3600/15 = 240 n(A∩C)= 3600/21 = 171 n(B∩C)= 3600/35 = 102
n(A∩B∩C) = 3600/105 = 34
Logo, o número dado pela formula (1) é igual a:
N = n(A) + n(B) + n(C) – n(A∩B) – n(A∩C) – n(B ∩C) + n(A∩B∩C)
N = 1200 + 720 + 514 – 240 – 171 – 102 + 34 = 1955
Assim, a resposta correta ao problema proposto é:
𝑁 = 1955
5/16/2019 8Análise Combinatória - Princípio da Inclusão e Exclusão
CASO GERAL: PRINCÍPIO DA 
INCLUSÃO E EXCLUSÃO
Teorema 1:
O número de elementos na união de n conjuntos finitos A1, A2, A3, … , An 
é dado pela expressão:
𝑛(𝐴1 ∪𝐴2 ∪𝐴3 ∪…∪ 𝐴𝑛) = σ𝑖=1
𝑛 𝑛(𝐴𝑖) − σ1≤𝑖≤𝑗≤𝑛𝑛 𝐴𝑖 ∩𝐴𝑗 +
+ σ1≤𝑖<𝑗<𝑘≤𝑛𝑛 𝐴𝑖 ∩𝐴𝑗∩𝐴𝑘
− σ1≤𝑖<𝑗<𝑘<𝑝≤𝑛𝑛 𝐴𝑖 ∩𝐴𝑗∩𝐴𝑘∩𝐴𝑝 + …
+(−1)𝑛−1 𝑛 𝐴1 ∩𝐴2∩𝐴3∩⋯∩𝐴𝑛 (2)
Isto é, as contribuições ímpares (conjuntos individuais 1 a 1, intercessão de conjuntos 3 a 3, 5 a 5, 
etc) são positivas e as pares (intercessão de conjuntos 2 a 2, 4 a 4, etc) são negativas.
5/16/2019 9Análise Combinatória - Princípio da Inclusão e Exclusão
PARÊNTESE MATEMÁTICO
Na aula anterior usamos o Teorema do Binômio para provar que
C(n,0) – C(n,1) + C(n,2) – ... + (–1)
n
C(n,n) = 0 (3)
0 = (1 – 1)
n
(1 – 1)
n
= ∑ C(n, k) 1
k 
(–1)
n-k 
0 = C(n,0) – C(n,1) + C(n,2) – ... + (–1)nC(n,n)
k=0
n
5/16/2019 10Análise Combinatória - Princípio da Inclusão e Exclusão
DEMONSTRAÇÃO DO PRINCÍPIO 
DA INCLUSÃO E EXCLUSÃO
Para provarmos a expressão (2) precisamos mostrar que um dado
elemento que pertença a p dos conjuntos Ai‘s, para p=1,2,3,…,n, é
contado por esta expressão exatamente uma vez.
Considerando um elemento pertencente a exatamente p conjuntos temos:
1) Em σ𝑖=1
𝑝
𝑛(𝐴𝑖) este elemento será contado C(p, 1) = p vezes.
2) Em σ1≤𝑖<𝑗≤𝑝𝑛 𝐴𝑖 ∩𝐴𝑗 ele será contado C(p, 2) vezes.
3) Em σ1≤𝑖<𝑗<𝑘≤𝑝𝑛 𝐴𝑖 ∩𝐴𝑗 ∩𝐴𝑘 ele será contado C(p, 3) vezes.
4) E assim sucessivamente até o termo 𝑛 𝐴𝑖1 ∩𝐴𝑖2∩⋯∩𝐴𝑖𝑝 em que 
este elemento será contado C(p, p) = 1 vez.
Somando todas as contribuições, o elemento em foco será contado N vezes:
N = C(p,1) – C(p,2) + C(p,3) – ... + (–1)
p-1
C(p,p)
O valor total das contribuições N é igual a:
N = C(p,1) – C(p,2) + C(p,3) – ... + (–1)
p-1
C(p,p)
Queremos mostrar que N = 1.
De (3) temos que:
C(p,0) – C(p,1) + C(p,2) – ... + (–1)
p
C(p,p) = 0 notar (–1)
p
Que pode ser reescrita como:
C(p,0) – [ C(p,1) – C(p,2) + ... + (–1)
p-1
C(p,p) ] = 0 notar (–1)
p-1
1 – [ C(p,1) – C(p,2) + ... + (–1)
p-1
C(p,p) ] = 0
N
Daí: 1 – N = 0 ==> N = 1 CQD
5/16/2019 11Análise Combinatória - Princípio da Inclusão e Exclusão
DEMONSTRAÇÃO DO PRINCÍPIO 
DA INCLUSÃO E EXCLUSÃO (cont.)
5/16/2019 12Análise Combinatória - Princípio da Inclusão e Exclusão
Parêntese Matemático
Suponhamos 2 conjuntosAe B. Pelo Princípio da Inclusão-Exclusão temos:
𝑛 𝐴∪𝐵 = 𝑛 𝐴 +𝑛 𝐵 −𝑛(𝐴∩𝐵)
𝑛 𝐴∪𝐵 = 𝑛 ҧ𝐴 ∩ ത𝐵 = 𝑛 𝑈 −𝑛 𝐴∪𝐵
𝑛 ҧ𝐴 ∩ ത𝐵 = 𝑛(𝑈)− 𝑛 𝐴 +𝑛 𝐵 −𝑛(𝐴∩𝐵) (4)
Generalizando para𝑛 conjuntos temos:
𝑛 𝐴1 ∩𝐴2 ∩⋯∩𝐴𝑛 = 𝑛(𝑈)− [𝑛 𝐴1 ∪𝐴2 ∪⋯∪𝐴𝑛 ] (5)
em que o número de elementos da união dos 𝑛 conjuntos 𝑛 𝐴1 ∪𝐴2 ∪⋯∪𝐴𝑛 é
dado peloTeorema 1, expressão(2)ou seja, pelo Princípio da Inclusão-Exclusão.
5/16/2019 13Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 3
Dentre os números de 1 a 1.000.000 inclusive, quantos não são
quadrados perfeitos, cubos perfeitos e nem 4as potências perfeitas ?
A = {1, 2, 3, …, 1.000.000} A1 = { x ∈ A | x é quadrado perfeito}
A2 = { x ∈ A | x é cubo perfeito} A3 = { x ∈ A | x é 4
apotência perfeita}
Buscamos o valor de 𝑁=𝑛 𝐴1 ∩𝐴2 ∩𝐴3 = 𝑛 𝐴 − n(𝐴1 ∪ 𝐴2 ∪𝐴3)
Como x4 = (x2)2, a 4apotência é também quadrado perfeito, logo A3⊂ A1 e
𝐴1 ∪𝐴2 ∪𝐴3 = 𝐴1 ∪𝐴2 e N = n(A) – n(𝐴1 ∪𝐴2 ∪𝐴3) = n(A) – n(𝐴1 ∪ 𝐴2)
Tem-se: n(𝐴1) = 106 = 1000 n(𝐴2) =
3
106 = 100 n(𝐴1 ∩𝐴2) =
6
106 = 10
Daí: N = n(𝐴) – n(𝐴1 ∪𝐴2) = 1.000.000 – [ n(𝐴1) + n(𝐴2) – n(𝐴1 ∩𝐴2) ]
N = 1.000.000 – [ 1000 + 100 – 10 ] = 1.000.000 – 1090
𝑁 = 998.910
5/16/2019 14Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 4
De quantos modos 6 casais podem sentar-se ao redor de uma mesa
circular sem que nenhum marido e mulher fiquem juntos?
Vamos definir Ai como o conjunto das permutações circulares das 12 pessoas nas quais o
i ésimo casal esteja junto, para i = 1, 2, 3, 4, 5, 6.
Buscamos o número N de elementos do conjunto complementar à união de todos os conjuntos
Ai, isto é, buscamos o valor de𝑁 = 𝑛 𝐴1
′ ∩𝐴2
′ ∩𝐴3
′ ∩𝐴4
′ ∩𝐴5
′ ∩𝐴6
′ dadopela expressão(5).
Se o i ésimo casal está junto temos 11 elementos no círculo (1 casal + 10 pessoas):
𝑛 𝐴𝑖 = 2
1.10! = 2 .10! (temos C6,1 possibilidades)
Se o i ésimo e o j ésimo casais estão juntos temos 10 elementos no círculo (2 casais + 8 pessoas):
𝑛 𝐴𝑖 ∩𝐴𝑗 = 2
2 .9! = 4 .9! (temos C6,2 possibilidades)
Se o iésimo, o jésimo e o késimo casaisestão juntos temos9 elementos no círculo (3 casais+ 6 pessoas):
𝑛 𝐴𝑖 ∩𝐴𝑗 ∩𝐴𝑘 = 2
3 .8! = 8 .8! (temos C6,3 possibilidades)
Se 4 casais estão juntos temos 8 elementos no círculo (4 casais + 4 pessoas):
𝑛 𝐴𝑖 ∩𝐴𝑗 ∩𝐴𝑘 ∩𝐴𝑝 = 2
4 .7! = 16 .7! (temos C6,4 possibilidades)
5/17/2019 15Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 4 (cont.)
De quantos modos 6 casais podem sentar-se ao redor de uma mesa
circular sem que nenhum marido e mulher fiquem juntos?
Se 5 casais estão juntos temos 7 elementos no círculo (5 casais + 2 pessoas):
𝑛 𝐴𝑖 ∩𝐴𝑗 ∩𝐴𝑘 ∩𝐴𝑝∩𝐴𝑛 =2
5 .6! = 32.6! (temos C6,5 possibilidades)
Se 6 casais estão juntos temos 6 elementos no círculo (6 casais):
𝑛 𝐴1∩𝐴2∩𝐴3∩𝐴4∩𝐴5∩𝐴6 =2
6 .5! = 64.5! (temos C6,6 possibilidades)
Buscamos : N = 11! – 𝑛 𝐴1∪𝐴2∪𝐴3∪𝐴4∪𝐴5∪𝐴6
Pelo princípio da inclusao e exclusão temos que:
N = 11! – [ C6,1(2.10!) – C6,2(4.9!) + C6,3(8.8!) – C6,4(16.7!) + C6,5(32.6!) – C6,6(64.5!) ] 
N = 11! – [ 6(2.10!) – 15(4.9!) + 20(8.8!) – 15(16.7!) + 6(32.6!) – 1(64.5!) ] 
N = 11! – [ 43.545.600 – 21.772.800 + 4.838.400 – 1.209.600 + 138.240 – 7.680 ]
N = 11! – 25.532.160 N = 14.384.640
5/16/2019 16Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 5
Determine o número de permutações simples dos elementos a1, a2,…, an,
nas quais a1está em primeiro lugar ou a2está em segundo lugar.
Definimos A1 como o conjunto das permutações em que a1está em primeiro lugar e
A2 como o conjunto das permutações em que a2 está em segundo lugar.
É claro que: n(A1) = n(A2) = (n –1)! e n(A1 ∩ A2) = (n –2)!
O que procuramos é simplesmente n(A1 ∪ A2) que é igual a:
n(A1 ∪ A2) = n(A1) + n(A2) – n(A1 ∩ A2)
= (n –1)! + (n –1)! – (n –2)!
= 2(n –1)! – (n –2)!
= 2(n –1)(n –2)! – (n –2)!
= (n –2)! (2n– 2 – 1) = (2n– 3) (n –2)!
𝑁 = 𝑛 𝐴1 ∪ 𝐴1 = 2𝑛 − 3 𝑛 − 2 !
5/16/2019 17Análise Combinatória - Princípio da Inclusão e Exclusão
A Função Φ de Euler
Definição 1:
Chamamos de função ϕ de Euler a função que atribui a cada inteiro positivo
m o número de inteiros positivos menores do que m que sejam relativamente
primos com m.
Uma simples aplicação do princípio da inclusão e exclusão nos permite obter a 
fórmula para o cálculo de ϕ(m) e enunciar o seguinte teorema:
Teorema 2:
O valor de ϕ(m) é dado por: 𝜙 𝑚 =𝑚 1−
1
𝑝1
1−
1
𝑝2
… 1−
1
𝑝𝑟
(6)
onde p1, p2, p3, …, pr, são os divisores primos de m, isto é:
𝑚 = 𝑝1
𝛼1 𝑝2
𝛼2 … 𝑝𝑟
𝛼𝑟
5/16/2019 18Análise Combinatória - Princípio da Inclusão e Exclusão
Demo da Fórmula da Função Φ de Euler
Demonstração: 𝜙 𝑚 =𝑚 1−
1
𝑝1
1−
1
𝑝2
… 1−
1
𝑝𝑟
(6)
onde p1, p2, p3, …, pr, são os divisores primos de m.
Consideremos os seguintes conjuntos:
A = { 1, 2, 3, …, m } A1 = { x A | x é mútiplo de p1}
A2 = { x ∈ A | x é mútiplo de p2} … Ar = { x ∈ A | x é mútiplo de pr}
Como o valor de ϕ(m) é o no de elementos do conj. complementarà união dos Ai’s emA, vem:
𝜙 𝑚 = 𝑛 𝐴 −𝑛(𝐴1 ∪𝐴2 ∪𝐴3 ∪…∪𝐴𝑟)
𝜙 𝑚 = 𝑛 𝐴 − σ𝑖=1
𝑟 𝑛(𝐴𝑖) −σ1≤𝑖<𝑗𝑛 𝐴𝑖 ∩𝐴𝑗 +σ1≤𝑖<𝑗<𝑘𝑛 𝐴𝑖 ∩𝐴𝑗∩𝐴𝑘 +⋯+
+ (−1)𝑟−1 𝑛 𝐴1 ∩𝐴2∩𝐴3∩⋯∩𝐴𝑟
𝜙 𝑚 = 𝑛 𝐴 −σ𝑖=1
𝑟 𝑛 𝐴𝑖 +σ1≤𝑖<𝑗𝑛 𝐴𝑖 ∩𝐴𝑗 −σ1≤𝑖<𝑗<𝑘𝑛 𝐴𝑖 ∩𝐴𝑗∩𝐴𝑘 +⋯+
+ (−1)𝑟 𝑛 𝐴1 ∩𝐴2∩𝐴3∩⋯∩𝐴𝑟
5/16/2019 19Análise Combinatória - Princípio da Inclusão e Exclusão
𝜙 𝑚 = 𝑛 𝐴 −σ𝑖=1
𝑟 𝑛 𝐴𝑖 +σ1≤𝑖<𝑗𝑛 𝐴𝑖 ∩𝐴𝑗 −σ1≤𝑖<𝑗<𝑘𝑛 𝐴𝑖 ∩𝐴𝑗∩𝐴𝑘 +⋯+
+ (−1)𝑟 𝑛 𝐴1 ∩𝐴2∩𝐴3∩⋯∩𝐴𝑟
Como: 𝑛 𝐴 = 𝑚 𝑛(𝐴𝑖) =
𝑚
𝑝𝑖
𝑛 𝐴𝑖 ∩𝐴𝑗 =
𝑚
𝑝𝑖𝑝𝑗
𝑛 𝐴𝑖 ∩𝐴𝑗∩𝐴𝑘 =
𝑚
𝑝𝑖𝑝𝑗𝑝𝑘
… 𝑛 𝐴𝑖 ∩𝐴𝑗∩𝐴𝑘∩⋯∩𝐴𝑟 =
𝑚
𝑝𝑖𝑝𝑗𝑝𝑘…𝑝𝑟
Segue que:
𝜙 𝑚 =𝑚−σ𝑖=1
𝑟 𝑚
𝑝𝑖
+σ1≤𝑖<𝑗
𝑚
𝑝𝑖𝑝𝑗
−σ1≤𝑖<𝑗<𝑘
𝑚
𝑝𝑖𝑝𝑗𝑝𝑘
+⋯+ (−1)𝑟
𝑚
𝑝𝑖𝑝𝑗𝑝𝑘
𝜙 𝑚 =𝑚 1− σ𝑖=1
𝑟 1
𝑝𝑖
+ σ1≤𝑖<𝑗
1
𝑝𝑖𝑝𝑗
−σ1≤𝑖<𝑗<𝑘
1
𝑝𝑖𝑝𝑗𝑝𝑘
+⋯+ (−1)𝑟
1
𝑝𝑖𝑝𝑗𝑝𝑘…𝑝𝑟
(7)
𝜙 𝑚 =𝑚 1−
1
𝑝1
1−
1
𝑝2
… 1−
1
𝑝𝑟
CQD
Demo da Fórmula da Função Φ de Euler
BM
BM: banalidade matemática
5/17/2019 20Análise Combinatória - Princípio da Inclusão e Exclusão
𝜙 𝑚 =𝑚 1−
1
𝑝1
1−
1
𝑝2
… 1−
1
𝑝𝑟
(6)
𝜙 𝑚 =𝑚 1− σ𝑖=1
𝑟 1
𝑝𝑖
+ σ1≤𝑖<𝑗
1
𝑝𝑖𝑝𝑗
−σ1≤𝑖<𝑗<𝑘
1
𝑝𝑖𝑝𝑗𝑝𝑘
+⋯+ (−1)𝑟
1
𝑝𝑖𝑝𝑗𝑝𝑘…𝑝𝑟
(7)
Dadas as expressões (6) e (7)acima, vamos mostrar para r = 3 que, fatorando-se a 
expressão que multiplica m em(7), chega-se na expressão que multiplica m em (6).
1− σ𝑖=1
3 1
𝑝𝑖
+ σ1≤𝑖<𝑗
1
𝑝𝑖𝑝𝑗
−
1
𝑝1𝑝2𝑝3
= 1−
1
𝑝1
−
1
𝑝2
−
1
𝑝3
+
1
𝑝1𝑝2
+
1
𝑝2𝑝3
+
1
𝑝1𝑝3
1−
1
𝑝1
−
1
𝑝2
−
1
𝑝3
+
1
𝑝1𝑝2
+
1
𝑝2𝑝3
+
1
𝑝1𝑝3
= 1−
1
𝑝1
−
1
𝑝2
1−
1
𝑝1
−
1
𝑝3
1−
1
𝑝1
−
1
𝑝2𝑝3
1−
1
𝑝1
= 1−
1
𝑝1
1−
1
𝑝2
−
1
𝑝3
−
1
𝑝2𝑝3
= 1−
1
𝑝1
1−
1
𝑝2
−
1
𝑝3
1−
1
𝑝2
= 1−
1
𝑝1
1−
1
𝑝2
1−
1
𝑝3
1− ෍
𝑖=1
3
1
𝑝𝑖
+ ෍
1≤𝑖<𝑗
1
𝑝𝑖𝑝𝑗
−
1
𝑝1𝑝2𝑝3
= 1−
1
𝑝1
1−
1
𝑝2
1−
1
𝑝3
Demo da Fórmula da Função Φ de Euler
CQD
5/16/2019 21Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 6
Calcular ϕ(m) para m = 2100.
𝑚 = 22. 3. 52. 7
𝜙 𝑚 = 2100 1 −
1
2
1−
1
3
1 −
1
5
1−
1
7
𝜙 𝑚 = 2100
1
2
2
3
4
5
6
7
= 2100
8
35
𝜙 𝑚 = 480
5/16/2019 22Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 7
Quantas soluções existem para 𝒙𝟏 + 𝒙𝟐+ 𝒙𝟑 = 𝟏𝟏, em que 𝒙𝟏, 𝒙𝟐 e 𝒙𝟑
são números inteiros não negativos com 𝒙𝟏 ≤ 𝟑, 𝒙𝟐 ≤ 𝟒 e 𝒙𝟑 ≤ 𝟔?
5/16/2019 23Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 7
Quantas soluções existem para 𝒙𝟏 + 𝒙𝟐+ 𝒙𝟑 = 𝟏𝟏, em que 𝒙𝟏, 𝒙𝟐 e 𝒙𝟑
são números inteiros não negativos com 𝒙𝟏 ≤ 𝟑, 𝒙𝟐 ≤ 𝟒 e 𝒙𝟑 ≤ 𝟔?
Considere:
𝑁 o número de todas as possíveis soluções da equação acima, isto é, 𝑁 = 𝑛 𝑈
𝑃1
′ como o conjunto das soluções que têm a propriedade 𝑥1 ≤ 3
𝑃1 como o conjunto das soluções que têm a propriedade 𝑥1 > 3 (𝑥1≥ 4)
𝑃2
′ como o conjunto das soluções que têm a propriedade 𝑥2 ≤ 4
𝑃2 como o conjunto das soluções que têm a propriedade 𝑥2 > 4 (𝑥2 ≥ 5)
𝑃3
′ como o conjunto das soluções que têm a propriedade 𝑥3 ≤ 6
𝑃3 como o conjunto das soluções que têm a propriedade 𝑥3 > 6 (𝑥3 ≥ 7)
O que buscamos é 𝑛(𝑃1
′ ∩ 𝑃2
′ ∩ 𝑃3
′) que é dado por:
𝑛(𝑃1
′ ∩ 𝑃2
′ ∩ 𝑃3
′) = 𝑁 − 𝑛 𝑃1 ∪ 𝑃2 ∪ 𝑃3
= 𝑁 − [
]
𝑁 𝑃1 + 𝑁 𝑃2 + 𝑁 𝑃3 − 𝑁 𝑃1 ∩ 𝑃2 − 𝑁 𝑃2 ∩ 𝑃3 −
− 𝑁 𝑃1 ∩ 𝑃3 + 𝑁 𝑃1 ∩ 𝑃2 ∩ 𝑃3
5/16/2019 24Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 7 (cont.)
Inserindo estes valores na fórmula para 𝑁(𝑃1
′ ∩ 𝑃2
′ ∩ 𝑃3
′) obtemos o resultado que o número 
de soluções com 𝑥1 ≤ 3, 𝑥2 ≤ 4 e 𝑥3 ≤ 6 é igual a:
𝑁(𝑃1
′ ∩ 𝑃2
′ ∩ 𝑃3
′) = 78 − 36 + 28 + 15 − 6 − 1 − 0 + 0 = 6
𝑁(𝑃1
′ ∩ 𝑃2
′∩ 𝑃3
′) = 6
5/16/2019 25Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 8
Quantas soluções em inteiros não negativos há para 𝒙 + 𝒚 + 𝒛 = 𝟐𝟒, 
onde 𝒙 ≤ 𝟒, 𝒚 ≤ 𝟏𝟐 e 𝒛 ≥ 𝟑?
5/16/2019 26Análise Combinatória- Princípio da Inclusão e Exclusão
Exemplo 8
Quantas soluções em inteiros não negativos há para 𝒙 + 𝒚 + 𝒛 = 𝟐𝟒, 
onde 𝒙 ≤ 𝟒, 𝒚 ≤ 𝟏𝟐 e 𝒛 ≥ 𝟑?
𝑃1 = 𝑥 𝑥 ≤ 4 𝑃2 = 𝑦 𝑦 ≤ 12 𝑃3 = 𝑧 𝑧 ≥ 3
𝑃1
′ = 𝑥 𝑥 ≥ 5 𝑃2
′ = 𝑦 𝑦 ≥ 13 𝑃3
′ = 𝑧 𝑧 ≤ 2
Queremos calcular 𝑛(𝑃1 ∩ 𝑃2 ∩ 𝑃3). Sendo N o n
o de todas as possíveis soluções da equação acima:
𝑛(𝑃1 ∩ 𝑃2 ∩ 𝑃3) = 𝑁 − 𝑛 𝑃1
′ ∪ 𝑃2
′ ∪ 𝑃3
′
= 𝑁 − [𝑛 𝑃1
′) + 𝑛 𝑃2
′ + 𝑛(𝑃3
′ − 𝑛 𝑃1
′ ∩ 𝑃2
′ − 𝑛 𝑃2
′ ∩ 𝑃3
′ −
− 𝑛 𝑃1
′ ∩ 𝑃3
′ + 𝑛(𝑃1
′ ∩ 𝑃2
′ ∩ 𝑃3
′)]
Cálculo de 𝑁: 𝑁 = 𝐶24
24+3−1 = 𝐶24
26 =
26!
2!24!
=
26×25
2
= 325
Cálculo de 𝑛 𝑃1
′ :
Fazendo a substituição 𝑥 = 𝑤 + 5 temos: 𝑤 + 𝑦 + 𝑧 = 19 𝑛 𝑃1
′ = 𝐶19
21 =
21×20
2
= 210
Cálculo de 𝑛 𝑃2
′ :
Fazendo a substituição y= 𝑡 + 13 temos: 𝑥 + 𝑡 + 𝑧 = 11 𝑛 𝑃2
′ = 𝐶11
13 =
13×12
2
= 78
5/16/2019 27Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 8 (cont.)
Quantas soluções em inteiros não negativos há para 𝒙 + 𝒚 + 𝒛 = 𝟐𝟒, 
onde 𝒙 ≤ 𝟒, 𝒚 ≤ 𝟏𝟐 e 𝒛 ≥ 𝟑?
Cálculo de 𝑛 𝑃3
′ : como 𝑛 𝑃3
′ = 𝑁 − 𝑛(𝑃3), vamos calcular 𝑛(𝑃3).
Fazendo a substituição z= 𝑣 + 2 temos: 𝑥 + 𝑦 + 𝑣 = 22 𝑛(𝑃3) = 𝐶22
24 =
24×23
2
= 276
Daí: 𝑛 𝑃3
′ = 325 − 276 = 49
Cálculo de 𝑛 𝑃1
′ ∩ 𝑃2
′ : 
Substituindo 𝑥 = 𝑤 + 5 e y= 𝑡 + 13 temos 𝑤 + 𝑡 + 𝑧 = 6 𝑛 𝑃1
′ ∩ 𝑃2
′ = 𝐶6
8 =
8×7
2
= 28
Cálculo de 𝑛 𝑃2
′ ∩ 𝑃3
′ : 
𝑃2
′ = {13, 14, 15, … , 23, 24} (12 termos) 𝑃3
′ = {0, 1, 2}
Se todos os pares (𝑦, 𝑧) 𝑦 ∈ 𝑃2
′ ∧ 𝑧 ∈ 𝑃3
′ levassem a soluções teríamos 12 × 3 = 36 soluções.
Porém precisamos eliminar os pares { 24, 1 , 24, 2 , 23, 2 }. Daí: 𝑛 𝑃1
′ ∩ 𝑃3
′ = 36 − 3 = 33
Cálculo de 𝑛 𝑃1
′ ∩ 𝑃3
′ : 
𝑃1
′ = {5, 6, 7, … , 23, 24} (20 termos) 𝑃3
′ = {0, 1, 2}
Se todos os pares (𝑥, 𝑧) 𝑥 ∈ 𝑃1
′ ∧ 𝑧 ∈ 𝑃3
′ levassem a soluções teríamos 20 × 3 = 60 soluções.
Porém precisamos eliminar os pares { 24, 1 , 24, 2 , 23, 2 }. Daí: 𝑛 𝑃1
′ ∩ 𝑃3
′ = 60 − 3 = 57
5/17/2019 28Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 8 (cont.)
Quantas soluções em inteiros não negativos há para 𝒙 + 𝒚 + 𝒛 = 𝟐𝟒, 
onde 𝒙 ≤ 𝟒, 𝒚 ≤ 𝟏𝟐 e 𝒛 ≥ 𝟑?
Cálculo de 𝑛 𝑃1
′ ∩ 𝑃2
′ ∩ 𝑃3
′ : 
𝑃1
′ = {5, 6, 7, … , 23, 24} (20 termos) 𝑃2
′ = {13, 14, 15, … , 23, 24} (12 termos) 𝑃3
′ = {0, 1, 2}
Vamos enumerar os 36 pares (𝑦, 𝑧) 𝑦 ∈ 𝑃2
′ ∧ 𝑧 ∈ 𝑃3
′ e inspecionar quais deles levam a soluções com 𝑥 ∈ 𝑃1
′.
Temos os seguintes pares (𝑦, 𝑧) 𝑦 ∈ 𝑃2
′ ∧ 𝑧 ∈ 𝑃3
′ :
{ 13, 0 , 13, 1 , 13, 2 , 14, 0 , 14, 1 , 14, 2 , 15, 0 , 15, 1 , 15, 2 , 16, 0 , 16, 1 , 16, 2 ,
17, 0 , 17, 1 , 17, 2 , 18, 0 , 18, 1 , 18, 2 , 19, 0 , 19, 1 , 19, 2 , 20, 0 , 20, 1 , 20, 2 ,
21, 0 , 21, 1 , 21, 2 , 22, 0 , 22, 1 , 22, 2 , 23, 0 , 23, 1 , 23, 2 , 24, 0 , 24, 1 , 24, 2 }
Os 15 pares (𝑦, 𝑧) em preto dão solução da equação, e os 18 pares vermelhos não dão, não importa o valor de 𝑥 ∈ 𝑃1
′.
𝑛 𝑃1
′ ∩ 𝑃2
′ ∩ 𝑃3
′ = 15
Finalmente:
𝑛(𝑃1 ∩𝑃2 ∩ 𝑃3) = 𝑁− [𝑛 𝑃1
′)+𝑛 𝑃2
′ +𝑛(𝑃3
′ −𝑛 𝑃1
′ ∩𝑃2
′ −𝑛 𝑃2
′ ∩𝑃3
′ − 𝑛 𝑃1
′ ∩𝑃3
′ +𝑛(𝑃1
′ ∩𝑃2
′ ∩𝑃3
′)]
𝑛(𝑃1 ∩𝑃2 ∩ 𝑃3) = 325 − [210 + 78 + 49 − 28 − 33 − 57 + 15] = 325 − 257
𝑛(𝑃1 ∩ 𝑃2 ∩ 𝑃3) = 91
5/16/2019 29Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 9
Quantas soluções em inteiros há para 𝒙 + 𝒚 + 𝒛 = 𝟐𝟓, onde 𝟐 ≤ 𝒙 ≤ 𝟒, 
𝟑 ≤ 𝒚 ≤ 𝟔 e 𝟒 ≤ 𝒛 ≤ 𝟖?
5/16/2019 30Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 9
Quantas soluções em inteiros há para 𝒙 + 𝒚 + 𝒛 = 𝟐𝟓, onde 𝟐 ≤ 𝒙 ≤ 𝟒, 
𝟑 ≤ 𝒚 ≤ 𝟔 e 𝟒 ≤ 𝒛 ≤ 𝟖?
X = {2, 3, 4} Y = {3, 4, 5, 6} Z = {4, 5, 6, 7, 8}
Nota-se que mesmo usando o maior elemento de X (4), o maior elemento de Y (6) e o maior
elemento de Z (8), a soma dos três não chega a 25. Portanto o número de soluções Ns é:
Ns = 0
5/16/2019 31Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 10
De quantas maneiras podemos ordenar as letras a, a, b, b, b, c, c, d, d de 
forma que letras iguais nunca estejam juntas? 
(Exercício 4 do Capítulo 4 do livro do José Plínio O. Santos)
5/16/2019 32Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 10 
De quantas maneiras podemos ordenar as letras a, a, b, b, b, c, c, d, d de 
forma que letras iguais nunca estejam juntas?
Vamos chamar:
Sa o conjunto das ordenações em que as duas letras a estão juntas;
Sbb+ o conjunto das ordenações em que pelo menos duas letras b estão juntas;
Sc o conjunto das ordenações em que as duas letras c estão juntas;
Sd o conjunto das ordenações em que as duas letras d estão juntas.
O conjunto Sbb+ merece especial atenção, pois ele é formado pela união de dois conjuntos disjuntos:
Sbb o conjunto das ordenações em que duas letras b estão juntas, mas não três;
Sbbb o conjunto das ordenações em que três letras b estão juntas.
Estamos interessados em calcular 𝑛(ഥ𝑆𝑎 ∩𝑆𝑏𝑏+ ∩ ഥ𝑆𝑐 ∩ 𝑆𝑑 ), o que pela expressão (5) é dado por:
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ ഥ𝑆𝑐 ∩ 𝑆𝑑 = 𝑁− [ 𝑛 𝑆𝑎 + 𝑛 𝑆𝑏𝑏+ + 𝑛 𝑆𝑐 + 𝑛(𝑆𝑑) +
−𝑛 𝑆𝑎 ∩𝑆𝑏𝑏+ −𝑛 𝑆𝑎 ∩𝑆𝑐 −𝑛 𝑆𝑎 ∩𝑆𝑑 −𝑛 𝑆𝑐 ∩𝑆𝑏𝑏+ −𝑛 𝑆𝑐 ∩𝑆𝑑 −𝑛 𝑆𝑑 ∩𝑆𝑏𝑏+
+𝑛 𝑆𝑎 ∩𝑆𝑏𝑏+ ∩𝑆𝑐 +𝑛 𝑆𝑎 ∩𝑆𝑐 ∩𝑆𝑑 +𝑛 𝑆𝑐 ∩𝑆𝑏𝑏+ ∩𝑆𝑑 +𝑛(𝑆𝑎 ∩𝑆𝑏𝑏+ ∩𝑆𝑑)+
+ 𝑛(𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ 𝑆𝑐 ∩ 𝑆𝑑)]
5/16/2019 33Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 10 (cont.)
Vamos aos cálculos dos valores intermediários:
Cálculo de N: 𝑁 = 𝑃𝑅 9; 3,2,2,2 =
9!
3!2!2!2!
= 7560
Cálculo de n(Sbbb): 𝑛(𝑆𝑏𝑏𝑏) = 𝑃𝑅 7; 2,2,2 =
7!
2!2!2!
= 630
Cálculo de n(Sbb): _ bb _ _ _ _ _ _ ou bb _ _ _ _ _ _ _ (8 elementos/posições) 
𝑛(𝑆𝑏𝑏) = 6 ×
5×6!
2!2!2!
+ 2 ×
6×6!
2!2!2!
= 30 ×
6!
8
+ 12 ×
6!
8
= 42 × 90 = 3780
Cálculo de n(Sbb+): 𝑛(𝑆𝑏𝑏+) = 𝑛(𝑆𝑏𝑏𝑏) + 𝑛(𝑆𝑏𝑏) = 630 + 3780 = 4410
Cálculo de 𝑛 𝑆𝑎 ∩ 𝑆𝑐 : 𝑛 𝑆𝑎 ∩ 𝑆𝑐 =
7!
3!2!
= 420
Cálculo de 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ : 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ = 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 + 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏𝑏
Cálculo de 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 : _ bb _ _ _ _ _ ou bb _ _ _ _ _ _ (7 elementos/posições) 
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 = 5 ×
4×5!
2!2!
+ 2 ×
5×5!
2!2!
= 20 ×
5!
4
+ 10 ×
5!
4
= 30 ×
5!
4
= 900
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏𝑏 =
6!
2!2!
= 180
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ = 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 + 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏𝑏 = 900 + 180 = 1080
5/16/2019 34Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 10 (cont.)
Continuando os cálculos dos valores intermediários:
Cálculo de 𝑛 𝑆𝑎 ∩ 𝑆𝑐 ∩ 𝑆𝑑 : 𝑛 𝑆𝑎 ∩ 𝑆𝑐 ∩ 𝑆𝑑 =
6!
3!
= 120
Cálculo de 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ 𝑆𝑐 : 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ 𝑆𝑐 = 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 ∩ 𝑆𝑐 + 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏𝑏 ∩ 𝑆𝑐
Cálculo de 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 ∩ 𝑆𝑐 : _ bb _ _ _ _ ou bb _ _ _ _ _ (6 elementos/posições)
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 ∩ 𝑆𝑐 = 4 ×
3×4!
2!
+ 2 ×
4×4!
2!
= 6 × 4! + 4 × 4! = 10 × 4! = 240
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏𝑏 ∩ 𝑆𝑐 =
5!
2!
= 60
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ 𝑆𝑐 = 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 + 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏𝑏 = 240 + 180 = 60
Cálculo de 𝑛 𝑆𝑎 ∩𝑆𝑏𝑏+ ∩𝑆𝑐 ∩𝑆𝑑 : 𝑛 𝑆𝑎∩𝑆𝑏𝑏+∩𝑆𝑐 ∩𝑆𝑑 =𝑛 𝑆𝑎 ∩𝑆𝑏𝑏∩𝑆𝑐 ∩𝑆𝑑 +𝑛 𝑆𝑎 ∩𝑆𝑏𝑏𝑏∩𝑆𝑐 ∩𝑆𝑑
Cálculo de 𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 ∩ 𝑆𝑐 ∩𝑆𝑑 : _ bb _ _ _ ou bb _ _ _ _ (5 elementos/posições)
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏 ∩ 𝑆𝑐 ∩ 𝑆𝑑 = 3 × 2 × 3! + 2 × 3 × 3! = 12 × 3! = 10 × 4! = 72
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏𝑏 ∩ 𝑆𝑐 ∩ 𝑆𝑑 = 4! = 24
𝑛 𝑆𝑎 ∩𝑆𝑏𝑏+ ∩𝑆𝑐 ∩𝑆𝑑 = 𝑛 𝑆𝑎 ∩𝑆𝑏𝑏 ∩𝑆𝑐 ∩𝑆𝑑 +𝑛𝑆𝑎 ∩𝑆𝑏𝑏𝑏 ∩𝑆𝑐 ∩𝑆𝑑 = 72+24 = 96
5/16/2019 35Análise Combinatória - Princípio da Inclusão e Exclusão
Exemplo 10 (cont.)
Cálculo final:
A expressão do cálculo final é dada por:
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ ഥ𝑆𝑐 ∩ 𝑆𝑑 = 𝑁− [ 𝑛 𝑆𝑎 + 𝑛 𝑆𝑏𝑏+ + 𝑛 𝑆𝑐 + 𝑛(𝑆𝑑) +
−𝑛 𝑆𝑎 ∩𝑆𝑏𝑏+ −𝑛 𝑆𝑎 ∩𝑆𝑐 −𝑛 𝑆𝑎 ∩𝑆𝑑 −𝑛 𝑆𝑐 ∩𝑆𝑏𝑏+ −𝑛 𝑆𝑐 ∩𝑆𝑑 −𝑛 𝑆𝑑 ∩𝑆𝑏𝑏+
+𝑛 𝑆𝑎 ∩𝑆𝑏𝑏+ ∩𝑆𝑐 +𝑛 𝑆𝑎 ∩𝑆𝑐 ∩𝑆𝑑 +𝑛 𝑆𝑐 ∩𝑆𝑏𝑏+ ∩𝑆𝑑 +𝑛(𝑆𝑎 ∩𝑆𝑏𝑏+ ∩𝑆𝑑)+
+ 𝑛(𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ 𝑆𝑐 ∩ 𝑆𝑑)]
Por motivos de simetria esta expressão pode ser reescrita como:
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ ഥ𝑆𝑐 ∩ 𝑆𝑑 = 𝑁−[3×𝑛 𝑆𝑎 +𝑛 𝑆𝑏𝑏+ − 3×𝑛 𝑆𝑎 ∩𝑆𝑏𝑏+ −3×𝑛 𝑆𝑎 ∩𝑆𝑐 +
+3×𝑛 𝑆𝑎 ∩𝑆𝑏𝑏+∩𝑆𝑐 +𝑛 𝑆𝑎 ∩𝑆𝑐 ∩𝑆𝑑 + 𝑛(𝑆𝑎 ∩𝑆𝑏𝑏+∩𝑆𝑐 ∩𝑆𝑑)]
Finalmente, substituindo-se os valores intermediários previamente calculados temos:
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ ഥ𝑆𝑐 ∩ 𝑆𝑑 = 7560−[3×1680+4410−3×1080−3×420+3×300+120−96]
𝑛 𝑆𝑎 ∩ 𝑆𝑏𝑏+ ∩ ഥ𝑆𝑐 ∩ 𝑆𝑑 = 1686