PRINCIPIO DE INCLUSAO E EXCLUSAO

Prévia do material em texto

IRENE MAGALHÃES CRAVEIRO
MYRIAN PASTORE DA SILVA
APLICAÇÕES DO
PRINCÍPIO DE INCLUSÃO
E EXCLUSÃO
APLICAÇÕES DO
PRINCÍPIO DE INCLUSÃO
E EXCLUSÃO
1a edição
2016
Rio de Janeiro
IRENE MAGALHÃES CRAVEIRO
MYRIAN PASTORE DA SILVA
APLICAÇÕES DO
PRINCÍPIO DE INCLUSÃO
E EXCLUSÃO
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
Sumário
1 Introdução 3
2 O princípio da Inclusão e Exclusão 5
2.1 O princípio da inclusão . . . . . . . . . . . . . . . . . . . . . . . 7
3 Aplicações do princípio da inclusão e exclusão 11
3.1 Permutações caóticas . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Contando funções sobrejetivas de domínio finito . . . . . . . . . . 14
3.3 Divisibilidade e Números Primos. . . . . . . . . . . . . . . . . . 17
3.4 A Função ϕ de Euler . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5 Soluções de Equações lineares em N com coeficientes unitários . . 22
3
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
Prefácio
Neste minicurso apresentaremos e demonstraremos uma fórmula para a car-
dinalidade da união de um número finito de conjuntos finitos, conhecida como
o Princípio de Inclusão e Exclusão. Esse resultado é uma ferramenta útil para
resolver diversos problemas de contagem. Várias aplicações desse resultado se-
rão abordadas durante a execução desse trabalho, sendo alguns problemas práticos
de contagem, e aplicações desse princípio em permutações caóticas e no cálculo
do número de funções sobrejetivas cujo domínio e o contradomínio sejam finitos.
Também exploraremos o conceito de divisibilidade, números primos e a função ϕ
de Euler interligando com o princípio da inclusão e exclusão. Finalmente, iremos
abordar as equações lineares com coeficientes unitários, cujas soluções estão res-
tritas ao subconjunto dos números naturais e veremos diversos problemas dessa
natureza onde o princípio de inclusão e exclusão é de grande utilidade.
1
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
2 SUMÁRIO
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
Capítulo 1
Introdução
Os jogos de azar, tais como lançamentos de dados, jogos de cartas, loterias,
entre outros contribuíram para o desenvolvimento da Análise Combinatória. A ne-
cessidade de calcular o número de possibilidades nos jogos gerou o estudo dos
métodos de contagem. Essa tendência levou Euler e d’Alembert a escreverem pro-
blemas referentes a loterias, sendo que um deles Euler publicou no ano de 1765.
[...] Suponha que n bilhetes são numerados consecutivamente de 1 a
n e que três bilhetes são tirados ao acaso. Então a probabilidade de
que três números consecutivos sejam tirados é
2.3
n(n − 1)
([3], p.314).
Questões de contagem aparecem com frequência em Estatística, Física, Quí-
mica, Biologia, Informática e em várias outras áreas do conhecimento. Já os Pa-
râmetros Curriculares Nacionais [8], trazem a necessidade do estudo da Análise
Combinatória desde as séries iniciais do ensino fundamental. Segundo este do-
cumento, no Ensino Médio, deve-se ter em mente que as técnicas de contagem
estudadas em Matemática devem estar relacionadas entre as várias ciências.
[...] aplicar as ideias de probabilidade e combinatória a fenômenos
naturais e do cotidiano são aplicações da Matemática em questões do
mundo real que tiveram um crescimento muito grande e se tornaram
bastante complexas. Técnicas e raciocínios estatísticos e probabilís-
ticos são, sem dúvida, instrumentos tanto das ciências da Natureza
quanto das Ciências Humanas. Isto mostra como será importante uma
cuidadosa abordagem dos conteúdos de contagem, estatística e proba-
bilidades no Ensino Médio, ampliando a interface entre o aprendizado
da Matemática e das demais ciências e áreas ([8], p.44).
A ideia básica da combinatória enumerativa é desenvolver técnicas para quan-
tificar objetos de um dado conjunto finito sem a necessidade de listar todos os seus
elementos. Algumas dessas técnicas consistem em dividir um problema maior em
3
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
4 CAPÍTULO 1. INTRODUÇÃO
pequenos problemas similares. O princípio da inclusão e exclusão é uma ferra-
menta de grande utilidade na resolução de problemas de contagem.
Nos problemas de combinatória trabalhados no Ensino Médio os métodos mais
utilizados são o Princípio Multiplicativo, o Princípio Aditivo, os Arranjos e as
Combinações. No entanto, quanto mais se impõe restrições ao problema mais
difícil será chegar a sua solução. Diferentes técnicas podem ser aplicadas a um
mesmo problema. Dessa forma o princípio da inclusão e exclusão pode ser uma
ferramenta facilitadora na resolução de diversos problemas combinatórios.
Este minicurso é composto, essencialmente, de assuntos retirados de diversos
materiais bibliográficas que citamos durante o desenvolvimento deste trabalho; In-
troduzimos inicialmente o princípio da inclusão e exclusão para o caso particular
de dois conjuntos finitos e, em seguida apresentamos uma aplicação direta deste
resuldado e analisamos o caso do princípio de inclusão e exclusão para o caso mais
geral, ou seja, validamos a fórmula para o cálculo de uma união de número finito
de conjuntos finitos.
Os outros tópicos abordam importante aplicações, como por exemplo, uma
fórmula para determinar a quantidade de permutações caóticas.
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
Capítulo 2
O princípio da Inclusão e
Exclusão
O Princípio de Inclusão e Exclusão é uma generalização do princípio aditivo.
Um dos tópicos desse minicurso é a obtenção de uma fórmula para contar o número
de elementos de uma união finita de vários conjuntos finitos, não necessariamente
disjuntos, tal fórmula é denominada princípio de inclusão e exclusão. Iremos va-
lidar essa fórmula e em seguida abordaremos diversas aplicações desse resultado.
Dado um conjunto finito A, iremos denotar por n(A) o número de elementos de
A. Nesse capítulo nosso principal objetivo é validar a fórmula dada no teorema 1
e aplicar alguns exemplosimediatos.
Proposição 1. Considere A e B conjuntos finitos. Então:
n(A ∪ B) = n(A) + n(B) − n(A ∩ B).
Demonstração: A demonstração da proposição 1 que faremos consiste de ve-
rificar que n(A)+n(B)−n(A∩B) conta o número de elementos na união A∪B.
Ou seja, vamos mostrar n(A) + n(B) − n(A ∩ B) conta cada elemento x ∈ A ∪ B
exatamente uma vez. Um elemento x ∈ A ∪ B pode pertencer somente a um dos
dois conjuntos, ou exatamente dois deles.
1 caso) x pode pertencer somente a um dos dois conjuntos: Se x estiver em A e
x ̸∈ B, n(A) conta x uma vez, n(B) conta x zero e n(A ∩ B) conta x zero
vez. Logo x é contado por n(A)+n(B)−n(A∩B) uma vez. Analogamente
analisamos os casos em x estiver somente em B.
2 caso) x está em exatamente dois dos conjuntos: se x ∈ A ∩ B temos:
n(A) conta x uma vez;
n(B) conta x uma vez;
n(A∩B) conta x uma vez. Logo x é contado por n(A)+n(B)−n(A∩B) =
1 + 1 − 1 = 1 vez. Segue dos casos: 1 e 2 que:
n(A ∪ B) = n(A) + n(B) − n(A ∩ B).
5
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
6 CAPÍTULO 2. O PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
�
Exemplo 2.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 pelo menos uma língua dentre inglês
e alemão.
Solução 2.1. Vamos definir:
A= conjunto formado pelos alunos que falam inglês;
B= conjunto formado pelos alunos que falam alemão;
A ∩ B= conjunto formado pelos alunos que falam inglês e alemão.
Temos que n(A) = 14, n(B) = 5 e n(A ∩ B) = 3. Observe que:
n(A ∪ B) = n(A) + n(B) − n(A ∩ B) = 14 + 5 − 3 = 16.
Quando somamos 14 com 5, teremos contado duas vezes aqueles alunos que se
encontram em A ∩ B, ou seja, os que falam inglês e alemão.
Proposição 2. Considere três conjuntos A, B e C, tais que A, B e C são finitos.
Então:
n(A∪B∪C) = n(A)+n(B)−n(A∩B)−n(A∩C)−n(B∩C)+n(A∩B∩C).
Demonstração: A demonstração da proposição 2 que faremos consiste de ve-
rificar que n(A) + n(B) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C)
conta o número de elementos na união A ∪ B ∪ C. Ou seja, vamos mostrar
n(A) + n(B) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C) conta
cada elemento x ∈ A ∪ B ∪ C exatamente uma vez. Um elemento x ∈ A ∪ B ∪ C
pode pertencer somente a um dos três conjuntos, ou exatamente dois deles ou aos
três conjuntos.
1 caso) x pode pertencer somente a um dos três conjuntos: Se x estiver em A então:
n(A) conta x uma vez;
n(B) conta x zero vez;
n(C) conta x zero vez;
n(A ∩ B) conta x zero vez;
n(A ∩ C) conta x zero vez;
n(B ∩ C) conta x zero vez e
n(A ∩ B ∩ C) conta x zero vez.
Logo x é contado por n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) −
n(B ∩ C) + n(A ∩ B ∩ C) uma vez. Analogamente analisamos os casos em
x estiver somente em B ou x estiver somente C.
2 caso) x está em exatamente dois dos conjuntos: x ∈ A∩B e x ̸∈ C, ou x ∈ A∩C
e x ̸∈ B, ou x ∈ B ∩ C e x ̸∈ A.
Se x ∈ A ∩ B e x ̸∈ C, temos:
n(A) conta x uma vez;
n(B) conta x uma vez;
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
2.1. O PRINCÍPIO DA INCLUSÃO 7
n(C) conta x zero vez;
n(A ∩ B) conta x uma vez;
n(A ∩ C) conta x zero vez;
n(B ∩ C) conta x zero vez;
n(A ∩ B ∩ C) conta x zero vez.
Logo x é contado por n(A)+n(B)+n(C)−n(A∩B)−n(A∩C)−n(B ∩
C) + n(A ∩ B ∩ C) = 1 + 1 + 0 − 1 − 0 − 0 + 0 = 1 vez. Analogamente
analisamos os casos ou x ∈ A ∩ C e x ̸∈ B, ou x ∈ B ∩ C e x ̸∈ A.
3 caso) x está em exatamente três dos conjuntos: x ∈ A ∩ B ∩ C. Então:
n(A) conta x uma vez;
n(B) conta x uma vez;
n(C) conta x uma vez;
n(A ∩ B) conta x uma vez;
n(A ∩ C) conta x uma vez;
n(B ∩ C) conta x uma vez;
n(A ∩ B ∩ C) conta x uma vez.
Logo x é contado por n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) −
n(B ∩ C) + n(A ∩ B ∩ C) = 1 + 1 + 1 − 1 − 1 − 1 + 1 = 1 vez.
�
2.1 O princípio da inclusão
Agora faremos a generalização das proposições 1 e 2, nesses casos fizemos
demonstrações para o Princípio da Inclusão e Exclusão no caso particular em que
n = 2, 3 onde n denota a quantidade de conjuntos.
Teorema 1. Considere um coleção de conjuntos finitos A1, A2, A3, ..., An. Então:
n(A1 ∪ A2 ∪ A3 ∪ ... ∪ An) =
n∑
i=1
n(Ai) −
∑
1≤i1≤i2≤n
n(Ai1 ∩ Ai2)+
+
∑
1≤i1≤i2≤i3≤n
n(Ai1 ∩ Ai2 ∩ Ai3) + . . .
. . . + (−1)p−1
∑
1≤i1≤i2≤i3≤...≤ip≤n
n(Ai1 ∩ Ai2 ∩ Ai3 ∩ ... ∩ Aip)+
+... + (−1)n−1n(Ai1 ∩ Ai2 ∩ Ai3 ∩ ... ∩ Ain). (2.1)
Demonstração: Para provarmos o teorema 1, basta mostrar que dado p =
1, 2, 3, ..., n temos que cada elemento que pertence a p dos conjuntos A′is é contado
exatamente uma vez em 2.1. De fato, se x pertence a p dos conjuntos A′is ele será
contado:(
p
1
)
vezes em
∑n
i=1 n(Ai);
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
8 CAPÍTULO 2. O PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
(
p
2
)
vezes em
∑
1≤i1≤i2≤i3≤n n(Ai1 ∩ Ai2);(
p
3
)
vezes em
∑
1≤i1≤i2≤i3≤n n(Ai1 ∩ Ai2 ∩ Ai3);
...(
p
p
)
vezes em
∑
1≤i1≤i2≤i3≤...≤ip≤n n(Ai1 ∩ Ai2 ∩ Ai3 ∩ ... ∩ Aip);
E claro que a interseção de mais que p conjuntos dentre os A′is não fornecerá ne-
nhuma contribuição, uma vez que o elemento em questão x pertence a exatamente
p dos conjuntos dentre A1, A2, A3, ..., An. Somando todas as contribuições com
seus respectivos sinais temos:(
p
1
)
−
(
p
2
)
+
(
p
3
)
−
(
p
4
)
+ . . . + (−1)p−1
(
p
p
)
(2.2)
Queremos provar que a expressão dada em 2.2 é igual a 1.
Segue do Teorema binomial que para todo x ∈ R e p ∈ N que:
(x + 1)p =
(
p
0
)
+
(
p
1
)
x +
(
p
2
)
x2 +
(
p
3
)
x3 + . . . +
(
p
p
)
xp, e fazendo x = −1
temos: 0 =
(
p
0
)
−
(
p
1
)
+
(
p
2
)
−
(
p
3
)
+ . . . + (−1)p−1
(
p
p
)
, ou seja
(
p
0
)
=(
p
1
)
−
(
p
2
)
+
(
p
3
)
+. . .+(−1)p−1
(
p
p
)
. Como
(
p
0
)
= 1 , então segue o resultado.
�
Exemplo 2.2. Quantos são os anagramas da palavra PERDÃO em que P ocupa o
primeiro lugar ou R ocupa o segundo lugar ou D ocupa o sexto lugar?
Solução 2.2. Vamos usar o princípio da inclusão e exclusão, pois se trata de um
problema de contagem da cardinalidade da união de um número finito de conjuntos
finitos. Para isso, definimos: A1, A2, A3
A1= conjunto de todos os anagramas da palavra PERDÃO que começa com a
letra P;
A2= conjunto de todos os anagramas da palavra PERDÃO tendo a letra R na
segunda posição;
A3 = conjunto de todos os anagramas da palavra PERDÃO tendo a letra D na
sexta posição;
A1 ∩ A2= conjunto de todos os anagramas da palavra PERDÃO tendo as letras P
na primeira posição e R na segunda posição;
A1 ∩ A3= conjunto de todos os anagramas da palavra PERDÃO tendo as letras P
na primeira posição e D na sexta posição;
A2 ∩ A3= conjunto de todos os anagramas da palavra PERDÃO tendo as letras R
na segunda posição e D na sexta posição;
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
2.1. O PRINCÍPIO DA INCLUSÃO9
A1 ∩ A2 ∩ A3= conjunto de todos os anagramas da palavra PERDÃO tendo as
letras P na primeira posição, R na segunda posição e D na sexta posição.
Note que, para i = 1, 2, 3 cada elemento de Ai é uma permutação de 6 letras com
uma delas fixas. Portanto n(Ai) = 120. Temos que o número de anagramas da
palavra PERDÃO com duas letras fixas é igual a 24. Logo,
n(A1 ∩ A2) = n(A1 ∩ A3) = n(A2 ∩ A3) = 24.
Por último vamos contar a cardinalidade de, A1 ∩ A2 ∩ A3, n(A1 ∩ A2 ∩ A3) = 6
que é o total de anagramas da palavra PERDÃO com 3 letras fixas.
n(A1 ∪ A2 ∪ A3) = n(A1) + n(A2) + n(A3) − n(A1 ∩ A2) − n(A1 ∩ A3) −
−n(A2 ∩ A3) + n(A1 ∩ A2 ∩ A3)
= 3 · 120 − 3 · 24 + 6 = 294.
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
10 CAPÍTULO 2. O PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
Capítulo 3
Aplicações do princípio da
inclusão e exclusão
Neste capítulo apresentaremos diversas aplicações do princípio da inclusão e
exclusão exploradas em algumas bibliografias de matemática discreta. Estas apli-
cações podem ser encontradas em [5] e [7].
3.1 Permutações caóticas
Uma das aplicações do princípio de inclusão e exclusão [5], consiste em deter-
minar o número de permutações caóticas de um conjunto com n elementos. Apre-
sentaremos a demonstração de tal resultado, e em seguida faremos alguns exem-
plos práticos. O teorema 2 é tópico principal dessa seção e é uma das interessantes
aplicações do princípio de inclusão e exclusão que exibiremos.
Definição 3.1. Uma permutação de n objetos, a1, a2, a3, ...an, é chamada caótica
quando nenhum dos a′is se encontra na posição original, isto é na i- ésima posição.
Por exemplo, a2a1a5a3a4 e a5a4a1a2a3 são permutações caóticas. Temos que
a3a4a1a2a5 não é permutação caótica, pois existe i = 5 e a5 está na posição 5.
Exemplo 3.1. Determine o número de permutações simples dos elementos a1, a2, a3,
..., an, nas quais a1 está em primeiro lugar ou a2 está em segundo lugar.
Solução 3.1. Vamos definir: A1, A2.
A1= conjunto das permutações a1, a2, a3, ..., an, tal que a1 está em primeiro lu-
gar;
A2= conjunto das permutações a1, a2, a3, ..., an, tal que a2 está em segundo lu-
gar;
A1 ∩ A2= conjunto das permutações a1, a2, a3, ..., an, tal que a1 está em primeiro
lugar e a2 está em segundo lugar.
11
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
12CAPÍTULO 3. APLICAÇÕES DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
Temos que n(A1) = n(A2) = (n − 1)! e n(A1 ∩ A2) = (n − 2)!. Logo,
n(A1 ∪ A2) = n(A1) + n(A2) − n(A1 ∩ A2) = 2(n − 1)! − (n − 2)!
= 2(n − 1)(n − 2)! − (n − 2)! = (n − 2)!(2(n − 1) − 1)
= (n − 2)!(2n − 3).
Nesse exemplo as permutações contadas aqui não são caóticas.
Exemplo 3.2. Dentre as permutações simples dos elementos a1, a2, a3, ..., an, de-
termine o número daquelas em que a1 não está em primeiro lugar, a2 não está em
segundo lugar e nem a3 não está em terceiro lugar.
Solução 3.2. Vamos definir para i = 1, 2, 3
Ai= conjunto das permutações de a1, a2, a3, ..., an em que ai está no i-ésimo lu-
gar;
Note que, para i = 1, 2, 3, cada elemento de Ai é uma permutação de n letras com
uma delas fixas. Portanto n(Ai) = (n − 1)!.
Temos que o número de permutações n letras com duas letras fixas é igual a
(n − 2)!. Logo,
n(A1 ∩ A2) = n(A1 ∩ A3) = n(A2 ∩ A3) = (n − 2)!.
Por último vamos contar a cardinalidade de A1 ∩ A2 ∩ A3,
n(A1 ∩ A2 ∩ A3) = (n − 3)!,
que é total de permutações de a1, a2, a3, ..., an com 3 letras fixas. O total de per-
mutações de a1, a2, a3, ..., an é n!. Dessa forma a solução do exemplo é:
n! − n(A1 ∪ A2 ∪ A3) = n! − n(A1) − n(A2) − n(A3) + n(A1 ∩ A2) + n(A1 ∩ A3) +
+n(A2 ∩ A3) − n(A1 ∩ A2 ∩ A3)
= n! − 3 · (n − 1)! + 3 · (n − 2)! − (n − 3)!.
Teorema 2. Se Dn é total de permutações caóticas de a1, a2, a3, ..., an, então
Dn = n!
(
1 − 1
1!
+ 1
2!
− 1
3!
+ ... + (−1)n 1
n!
)
.
Demonstração: Vamos definir para i = 1, 2, 3, ..., n:
Ai= conjunto das permutações de a1, a2, a3, ..., an em que ai está na i-ésima posi-
ção. Para calcularmos Dn devemos calcular o total de permutações de a1, a2, a3, ..., an
que não pertence a nenhum dos Ai’s, ou seja, o número de elementos no comple-
mentar da união dos Ai’s. Portanto,
Dn = n! −
n∑
i=1
n(Ai) +
∑
1≤i1≤i2≤n
n(Ai1 ∩ Ai2) −
∑
1≤i1≤i2≤i3≤n
n(Ai1 ∩ Ai2∩
∩Ai3) + ∩ . . . ∩ +(−1)nn(A1 ∩ A2 ∩ A3 + . . . + An).
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
3.1. PERMUTAÇÕES CAÓTICAS 13
Note que, para i = 1, 2, ..., n cada elemento de Ai é uma permutação de n letras
com uma delas fixas. Portanto n(Ai) = (n − 1)!. Temos que:
n(Ai ∩ Aj) = (n − 2)!, ∀1 ≤ i ≤ j ≤ n;
n(Ai ∩ Aj ∩ Ak) = (n − 3)!, ∀1 ≤ i ≤ j ≤ k ≤ n
...
n(A1 ∩ A2 ∩ ... ∩ An) = 1.
Temos
(
n
1
)
parcelas na soma:
∑n
i=1 n(Ai) e n(Ai) = n(A1) = (n − 1)!
Temos
(
n
2
)
parcelas na soma:
∑
1≤i1≤i2≤n n(Ai1 ∩Ai2) e n(Ai1 ∩Ai2) = n(A1 ∩
A2) = (n − 2)!
Temos
(
n
3
)
parcelas na soma:
∑
1≤i1≤i2≤i3≤n n(Ai1 ∩Ai2 ∩Ai3) e n(Ai1 ∩Ai2 ∩
Ai3) = n(A1 ∩ A2 ∩ A3) = (n − 3)!
...
n(A1 ∩ A2 ∩ ... ∩ An) = 1 =
(
n
n
)
Então:
Dn = n! −
(
n
1
)
n(Ai) +
(
n
2
)
n(Ai1 ∩ Ai2) −
(
n
3
)
n(Ai1 ∩ Ai2 ∩ Ai3) + . . . +
+(−1)nn(A1 ∩ A2 ∩ A3 + . . . + An)
= n! −
(
n
1
)
(n − 1)! +
(
n
2
)
(n − 2)!
(
n
3
)
(n − 3)! + . . . + (−1)n1
= n! − n!
1!(n − 1)!
(n − 1)! + n!
2!(n − 2)!
(n − 2)! − n!
3!(n − 3)!
(n − 3)! + . . . +
+(−1)n n!
n!(n − n)!
= n! − n!
1!
+ n!
2!
− n!
3!
+ . . . + (−1)n n!
n!
= n!
(
1 − 1
1!
+ 1
2!
− 1
3!
+ . . . + (−1)n 1
n!
)
.
�
Utilizando a fórmula do teorema 2, podemos ver que o número de permutações
caóticas de 3 objetos abc é:
D3 = 3!
( 1
1!
+ 1
2!
− 1
3!
)
= 6
(3 − 1
6
)
= 2.
As seis permutações abc, acb, bac, bca, cba e cab. Sendo as permutações caóticas
de abc: bca e cab.
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
14CAPÍTULO 3. APLICAÇÕES DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
Exemplo 3.3. Quantas permutações dos inteiros 1, 2, 3, 4, ..., 9, 10 tem exatamente
4 dos números em suas posições originais.
Solução 3.3. Como são fixados os 4 números dentre 1, 2, 3, 4, ..., 9, 10, que perma-
necem nas posições originais, então devemos escolher estes 4 números, o que pode
ser feito de
(
10
4
)
maneiras distintas, em seguida permutar os 6 números restantes
caoticamente. Logo a resposta do problema é:
(
10
4
)
· D6.
(
10
4
)
·D6 =
(
10
4
)
· 6! ·
(
1 − 1
1!
+ 1
2!
− 1
3!
+ 1
4!
− 1
5!
+ 1
6!
)
=
(
10
4
)
·
(
6! − 6!
1!
+ 6!
2!
− 6!
3!
+ 6!
4!
− 6!
5!
+ 6!
6!
)
=
(
10
4
)
· (6 · 5 · 4 · 3 − 6 · 5 · 4 + 6 · 5 − 6 + 1) = 55.650.
Exemplo 3.4. Uma professora distribui nove livros diferentes para nove crianças.
Um mês depois recolhe os livros e, novamente, distribui um livro para cada cri-
ança. De quantas maneiras os livros podem ser distribuídos de modo que somente
três crianças receba o mesmo livro desta vez?
Solução 3.4. Vamos escolher 3 crianças dentre as 9 para receber o mesmo livro,
que podemos fazer de
(
9
3
)
maneiras distintas. Daí restam 6 crianças que não
poderão receber o mesmo livro que podem ser distribuídos de D6 maneiras dife-
rentes. Portanto a solução para o problema é:(
9
3
)
· D6 =
(
9
3
)
· 6! ·
(
1 − 1
1!
+ 1
2!
− 1
3!
+ 1
4!
− 1
5!
+ 1
6!
)
=
(
9
3
)
· 265 = 22.260.
3.2 Contando funções sobrejetivas de domínio finito
Segue direto do princípio multiplicativo que o número de funções f de A em
B, onde n(A) = t e n(B) = k é kt.
Consideremos o caso k = t, ou seja, A = {a1, a2, a3, ..., ak} e
B = {b1, b2, b3, ..., bk} queremos determinar o número de funções f : A −→ B
bijetoras. De fato, temos k possíveis imagens para a1. Depois de escolhido a
imagem para a1, temos k − 1 imagens para a2, pois f é bijetora. Fazendo isso su-
cessivamente temos uma imagem para ak. Então segue do princípio multiplicativo
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
3.2. CONTANDO FUNÇÕES SOBREJETIVAS DE DOMÍNIO FINITO 15
que o número de funções bijetoras de A em B é k!.
No caso t ≤ k, então o número de funções injetoras de A em B é:
k(k − 1)...(k − t + 1).
De fato, se A = {a1, a2, a3, ..., at} e B = {b1, b2, b3, ..., bt, bt+1, ..., bk}. Te-
mos k possíveis imagens para a1. Como f : A −→ B é injetora então temos
k − 1 imagens para a2 depois de já ter escolhido imagens para a1. Fazendo isso
sucessivamente até o objeto at, vemos que há k − (t − 1) imagens possíveis para
at. Dessa forma, segue do princípio multiplicativo o resultado.
Considere A = {1, 2, 3, 4, 5, 6, 7, 8, 9} e B = {a, b, c, d}.
Vamos definir as funções f : A −→ B e g : A −→ B, tais que:
f(1) = f(2) = f(3) = f(4) = a; f(5) = f(6) = b; f(7) = f(8) = c e
f(9) = d;
g(1) = g(2) = g(3) = g(4) = a; g(5) = g(6) = b; g(7) = g(8) = g(9) = c;
Im(f) = B e f é sobrejetora.
Im(g) = {a, b, c} ̸= B e g não é sobrejetora.
Observe que g não é sobrejetora, pois dado d ∈ B não existe x ∈ A, tal que
d = g(x), ou seja, a equação d = g(x) não tem solução em B.
Dados A = {a1, a2, a3, ..., at}, B = {b1, b2, b3, ..., bk} e f : A −→ B, definimos:
f−1({bi}) = {x ∈ A; f(x) = bi}
Do exemplo anterior temos: f−1({a}) = {1, 2, 3, 4}; f−1({b}) = {5, 6};
f−1({c}) = {7, 8}; f−1({d}) = {9};
g−1({a}) = {1, 2, 3, 4}; g−1({b}) = {5, 6}; g−1({c}) = {7, 8, 9};
f−1({d}) = ∅.
Agora iremos contar as aplicações sobrejetoras f : A −→ B, onde n(A) = t e
n(B) = k, com t ≥ k.
Teorema 3. Para t ≤ k, o número de funções sobrejetoras f : A −→ B, onde
n(A) = t e n(B) = k, é dado por:
S(t, k) =
k∑
i=0
(−1)i
(
k
j
)
(k − i)t
Demonstração: Temos que existe kt funções f : A −→ B, então vamos
subtrair deste total o número de funções f : A −→ B que não são sobrejetoras.
Para isso, sejam A = {a1, a2, a3, ..., ak, a(k+1), ..., at}, B = {b1, b2, b3, ..., bk}.
Sabemos que uma função f : A −→ B é sobrejetora se, e somente se, para todo
b ∈ B, existe a ∈ A, tal que b = f(a), ou seja, a equação b = f(a) tem solução
em B. Dessa forma, vamos definir para todo 1 ≤ i ≤ k:
Ci= conjuntos de todas as funções f : A −→ B, tais que, f−1({bi}) = ∅, ou seja,
f(a) ̸= bi, ∀ a ∈ A.
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
16CAPÍTULO 3. APLICAÇÕES DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
Como uma função f : A −→ B que não é sobrejetora pertence a pelo menos
um dos C ′is, então o conjunto formado pelas funções f : A −→ B que não são
sobrejetoras é:
C1 ∪ C2 ∪ C3 ∪ ... ∪ Ck.
Segue do princípio da inclusão e exclusão que
n(C1 ∪ C2 ∪ C3 ∪ ... ∪ Ck) =
k∑
i=1
n(Ci) −
∑
1≤i1≤i2≤n
n(Ci1 ∩ Ci2)+
+
∑
1≤i1≤i2≤i3≤n
n(Ci1 ∩ Ci2 ∩ Ci3) + ... + (−1)n−1n(C1 ∩ C2 ∩ C3 ∩ ... ∩ Ck)
Queremos saber o total de funções f : A −→ B, tal que, o elemento bi não se
corresponde com elementos A. Nesse caso, esse número é n(Ci) = (k − 1)t,
para i = 1, 2, ..., k. Agora queremos calcular n(Ci ∩ Cj), que é o total de fun-
ções f : A −→ B, tal que, o elemento bi e bj não se corresponde com elementos
de A. Logo n(Ci ∩ Cj) = (k − 2)t para todo 1 ≤ i < j ≤ n. De maneira
análoga, temos n(Ci ∩ Cj ∩ Cl) = (k − 3)t para todo 1 ≤ i < j < l ≤ n. E
n(C1 ∩ C2 ∩ C3 ∩ ... ∩ Ck) = 0 = (k − k)t.
Além disso, temos:(
n
1
)
termos na soma
∑n
i=1 n(Ci) e n(Ci) = n(C1) = (k − 1)t(
n
2
)
termos na
∑
1≤i1≤i2≤n n(Ci1 ∩Ci2) e n(Ci1 ∩Ci2) = n(C1 ∩C2) = (k−2)
t(
n
3
)
termos em
∑
1≤i1≤i2≤i3≤n n(Ci1 ∩ Ci2 ∩ Ci3) e n(C1 ∩ C2 ∩ C3) = (k − 3)
t
...(
n
n
)
= 1 termo em (−1)n−1n(C1 ∩ C2 ∩ C3 ∩ ... ∩ Ck) = (k − k)t.
Portanto
n(C1 ∪ C2 ∪ C3 ∪ ... ∪ Ck) =
(
n
1
)
n(C1) −
(
n
2
)
n(C1 ∩ C2)+
+
(
n
3
)
n(C1 ∩ C2 ∩ C3) + ... + (−1)k−1n(C1 ∩ C2 ∩ ... ∩ Ck)
=
(
n
1
)
(k − 1)t −
(
n
2
)
(k − 2)t +
(
n
3
)
(k − 3)t + ...+
+(−1)k−1(k − k)t =
k∑
i=1
(−1)i−1
(
n
i
)
(k − i)t.
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
3.3. DIVISIBILIDADE E NÚMEROS PRIMOS. 17
Subtraindo n(C1 ∪ C2 ∪ C3 ∪ ... ∪ Ck) do total kt obtemos o resultado:
S(t, k) = kt −
k∑
i=1
(−1)i−1
(
n
i
)
(k − i)t
= kt +
k∑
i=1
(−1)i
(
n
i
)
(k − i)t =
k∑
i=0
(−1)i
(
n
i
)
(k − i)t.
�
3.3 Divisibilidade e Números Primos.
Iremos explorar, nesta seção seguindo as ideias dadas em [5] e [7] os conceitos
de divisibilidade, números primos e o máximo divisor comum e as suas respectivas
relações com o princípio de inclusão e exclusão. Para isso, usaremos a notação [x]
para indicar o maior inteiro menor do que ou igual ao número real x. Para qualquer
inteiro positivo a e b > 0, temos que existem inteiros q, r, tais que a = bq + r,
onde r = 0 ou r < b. Quando r = 0, dizemos que a é divisível por b, ou a é
múltiplo de b ou ainda, b é um divisor de a.
Observe que:
a
b
= q+ r
b
e
r
b
< 1. Logo,
[
a
b
]
=
[
q + r
b
]
= q, onde é chamado
de quociente da divisão de a por b.
Exemplo 3.5. Quantos são os inteiros entre 1 e 3.600, inclusive, que são divisíveis
por 3, 5 ou 7?
Solução 3.5. Para isso vamos definir:
A= conjunto dos números entre 1 e 3.600, inclusive, que são divisíveis por 3;
B= conjunto dos números entre 1 e 3.600, inclusive, que são divisíveis por 5;
C=conjunto dos números entre 1 e 3.600, inclusive, que são divisíveis por 7;
A ∩ B= conjunto dos números entre 1 e 3.600, inclusive, que são divisíveis por 3
e 5;
A ∩ C= conjunto dos números entre 1 e 3.600, inclusive, que são divisíveis por 3
e 7;
B ∩ C= conjunto dos números entre 1 e 3.600, inclusive, que são divisíveis por 5
e 7;
A∩B ∩C=conjunto dos números entre 1 e 3.600, inclusive, que são divisíveis por
3, 5 e 7.
Temos que:
n(A)=
[3600
3
]
= 1200; n(B) =
[3600
5
]
= 720; n(C) =
[3600
7
]
= 514;
n(A ∩ B) =
[3600
3 · 5
]
=
[3600
15
]
= 240;
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
18CAPÍTULO 3. APLICAÇÕES DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
n(A ∩ B) =
[3600
3 · 7
]
=
[3600
21
]
= 171;
n(B ∩ C) =
[3600
5 · 7
]
=
[3600
35
]
= 102;
n(A ∩ B ∩ C) =
[ 3600
3 · 5 · 7
]
=
[3600
105
]
= 34.
Portanto a resposta para o nosso exemplo é:
n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) +
+n(A ∩ B ∩ C)
= 1200 + 720 + 514 − 240 − 171 − 102 + 34 = 1955.
Usaremos o princípio de inclusão e exclusão para validar o caso geral do exem-
plo 3.5, que enunciamos no teorema 4:
Teorema 4. Dado um número inteiro m > 0 e sendo p1, p2, p3, ..., pr números me-
nores ou iguais m e primos entre si. Então a quantidade de inteiros positivos meno-
res ou iguais a m que não são divisíveis por nenhum dos números p1, p2, p3, ..., pr
é dada pela fórmula:
m −
r∑
i=1
[
m
pi
]
+
∑
1≤i≤j≤r
[
m
pipj
]
+ ... + (−1)r ·
[
m
p1, p2, ..., pr
]
Demonstração: A demonstração consiste em: dos números de 1 até m vamos
retirar todos aqueles que são divisíveis por p1 ou p2 ou p3 ou ... ou pr e assim
teremos todos aqueles que não são divisíveis por nenhum desses números. Para
isso vamos definir:
A = {1, 2, 3, ..., m};
A1 = {x ∈ A; x = p1k1, k1 ∈ N};
A2 = {x ∈ A; x = p2k2, k2 ∈ N};
A3 = {x ∈ A; x = p3k3, k3 ∈ N};
...
Ar = {x ∈ A; x = prkr, kr ∈ N};
De fato,
n(A) − n(A1 ∪ A2 ∪ A3 ∪ ... ∪ Ar) = m −
r∑
i=1
[
m
pi
]
+
∑
1≤i≤j≤r
[
m
pipj
]
+
+... + (−1)r ·
[
m
p1, p2, ..., pr
]
,
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
3.3. DIVISIBILIDADE E NÚMEROS PRIMOS. 19
Pois,
n(A1) =
[
m
p1
]
; n(A2) =
[
m
p2
]
; n(A3) =
[
m
p3
]
, ..., n(Ar) =
[
m
pr
]
n(Ai ∩ Aj) =
[
m
pipj
]
, ∀1 ≤ i < j ≤ r;
n(Ai ∩ Aj ∩ Al) =
[
m
pipjpl
]
, ∀1 ≤ i < j < l ≤ r;
...
n(A1 ∩ A2 ∩ A3 ∩ ... ∩ Ar) =
[
m
p1p2p3...pr
]
. �
Exemplo 3.6. Quantos são os inteiros entre 1 e 42.000, inclusive, que não são
divisíveis por 2, por 3 e nem por 7?
Solução 3.6. Para isso vamos definir:
A = {1, 2, 3, ..., 42000};
A1 = {x ∈ A; x = 2k, k ∈ N};
A2 = {x ∈ A; x = 3k, k ∈ N};
A3 = {x ∈ A; x = 7k, k ∈ N}.
A resposta do exemplo é: n(A) − n(A1 ∪ A2 ∪ A3). Temos que:
n(A1) =
[42000
2
]
= 21000; n(A2) =
[42000
3
]
= 14000; n(A3) =
[42000
7
]
=
6000.
n(A1 ∩ A2) =
[42000
2 · 3
]
=
[42000
6
]
= 7000;
n(A1 ∩ A3) =
[42000
2 · 7
]
=
[42000
14
]
= 3000;
n(A2 ∩ A3) =
[42000
3 · 7
]
=
[42000
21
]
= 2000;
n(A1 ∩ A2 ∩ A3) =
[ 42000
2 · 3 · 7
]
=
[42000
42
]
= 1000;
Portanto a resposta para o nosso exemplo é:
n(A) − n(A1 ∪ A2 ∪ A3) = n(A) − n(A1) − n(A2) − n(A3) + n(A1 ∩ A2)+
+n(A1 ∩ A3) + n(A2 ∩ A3) − n(A1 ∩ A2 ∩ A3)
= 42000 − 21000 − 14000 − 6000 + 7000 + 3000 + 2000 − 1000 = 12000
Usando o fato que um número inteiro composto é divisível por um número
primo não excedente a sua raiz quadrada podemos encontrar a quantidade de nú-
meros primos não excedentes a 100, por meio do princípio de inclusão e exclusão,
de acordo com exemplo dado em [7], essa ideia será explorada nesse trabalho.
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
20CAPÍTULO 3. APLICAÇÕES DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
Exemplo 3.7. Encontrar a quantidade de números primos não excedentes a 100.
Solução 3.7. Os números compostos não excedentes a 100 deve ter um fator primo
não excedente a 10. Desta forma precisamos encontrar a quantidade de inteiros
positivos menores ou iguais a 100 que não são divisíveis por nenhum dos primos
2, 3, 5 e 7 e depois somar esses 4 primos que não entraram nessa contagem.
A quantidade de inteiros positivos menores ou iguais a 100 que não são divisíveis
por nenhum dos primos 2, 3, 5 e 7 é:
100 −
[100
2
]
−
[100
3
]
−
[100
5
]
−
[100
7
]
+
[ 100
2 · 3
]
+
[ 100
2 · 5
]
+
[ 100
2 · 7
]
+
+
[ 100
3 · 5
]
+
[ 100
3 · 7
]
+
[ 100
5 · 7
]
−
[ 100
2 · 3 · 7
]
−
[ 100
2 · 5 · 7
]
−
[ 100
3 · 5 · 7
]
−
−
[ 100
2 · 3 · 5
]
+
[ 100
2 · 3 · 5 · 7
]
= 100 − 50 − 33 − 20 − 14 + 16 + 10 + 7 + 6 + 4 + 2 − 2 − 1 − 0 − 3 + 0 = 22.
Temos que 22 é o total de números não divisíveis por 2, 3, 5 e 7.
Como 1 não é primo e um entra nesse total 22, então temos 21 números primos
maiores do que 7 e menores do que 100.
Somando 21 com 4 que são os primos 2, 3, 5 e 7 que não entraram na contagem
acima temos no total 21 + 4 = 25 números primos que não excedem 100. A tabela
abaixo ilustra esses 25 primos que é o total que acabamos de encontrar.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
3.4 A Função ϕ de Euler
Definição 3.2. Chamamos de função ϕ de Euler a função que atribui a cada inteiro
positivo o número de inteiros menores ou iguais a m relativamente primos com m.
Ou seja, ϕ : N − {0} → N; ϕ(s) = n({x ∈ N; 1 ≤ x ≤ s e mdc(x, s) = 1})
Por meio do princípio de inclusão e exclusão iremos validar a fórmula para o
cálculo de ϕ(m), onde m é um natural maior do que 1 dado no Teorema 5.
Segue da definição que ϕ(1) = 1.
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
3.4. A FUNÇÃO ϕ DE EULER 21
Teorema 5. Seja m > 1 e m = pα11 p
α2
2 . . . p
αr
r a decomposição de m em fatores
primos. O valor de ϕ(m) é dado por:
ϕ(m) = m
(
1 − 1
p1
)(
1 − 1
p2
)
...
(
1 − 1
pr
)
.
Demonstração: A estratégia da demonstração consiste: dos números de 1 até
m, vamos retirar todos aqueles que são divisíveis por p1 ou p2 ou p3 ou ... ou pr e
assim teremos todos aqueles que não são divisíveis por nenhum desses números.
Para isso vamos definir:
A = {1, 2, 3, ..., m};
A1 = {x ∈ A; x = p1k1, k1 ∈ N};
A2 = {x ∈ A; x = p2k2, k2 ∈ N};
A3 = {x ∈ A; x = p3k3, k3 ∈ N};
...
Ar = {x ∈ A; x = prkr, kr ∈ N};
Como ϕ(m) é o número de elementos no complementar da união dos A′is em A,
temos:
ϕ(m) = m − n(A1 ∪ A2 ∪ A3 ∪ ... ∪ Ar) =
= m −
r∑
i=1
n(Ai) +
∑
1≤i<j≤r
n(Ai ∩ Aj) + ... + (−1)r · n(A1 ∩ A2 ∩ A3 ∩ ... ∩ Ar).
Temos que:
n(A1) =
m
p1
; n(A2) =
m
p2
; n(A3) =
m
p3
, ..., n(Ar) =
m
pr
n(Ai ∩ Aj) =
m
pi · pj
, ∀1 ≤ i < j ≤ r;
n(Ai ∩ Aj ∩ Al) =
m
pi · pj · pl
, ∀1 ≤ i < j < l ≤ r;
...
n(A1 ∩ A2 ∩ A3 ∩ ... ∩ Ar) =
m
p1 · p2 · p3...pr
.
Portanto
ϕ(m) = m −
r∑
i=1
m
p1
+
∑
1≤i<j≤r
m
pi · pj
+ ... + (−1)r · m
p1 · p2 · p3...pr
= m
1 − r∑
i=1
1
p1
+
∑
1≤i<j≤r
1
pi · pj
+ ... + (−1)r · 1
p1 · p2 · p3...pr

= m
(
1 − 1
p1
)(
1 − 1
p2
)
...
(
1 − 1
pr
)�
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
22CAPÍTULO 3. APLICAÇÕES DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
3.5 Soluções de Equações lineares em N com coeficientes
unitários
Para finalizar o trabalho, iremos abordar as equações lineares com coeficientes
unitários, cujas soluções estão restritas a subconjunto dos números naturais e ve-
remos diversos problemas dessa natureza enfatizando a utilidade do princípio da
inclusão nesse contexto.
A ideia dessa seção é baseada em [5], inclusive alguns exemplos e a demons-
trações de certos resultados foram retirados dessa bibliografia.
Para isso vamos descrever primeiramente, o número de solução inteiras de uma
equação da forma x1 + x2 + ... + xr = m, onde xi, para i = 1, 2, ..., r e m são
inteiros. Por exemplo,
x1 + x2 = 5.
Se exigirmos que x1, x2 sejam inteiros, não vamos ter um número finito de
soluções. Pois x1 = 5 − x2, fazendo x2 variar no conjunto dos inteiros temos uma
infinidade de valores para x1.
Se restringirmos as soluções ao conjunto dos inteiros positivos obtemos um
número finito de soluções, e as soluções inteiras positivas de x1 + x2 = 5:
(1, 4), (2, 3), (3, 2), (4, 1).
Nesse caso são quatro soluções.
Nosso próximo passo é determinar uma fórmula que faça essa contagem, para
isso vamos considerar em particular a equação:
x1 + x2 + x3 + x4 = 11, x1, x2, x3, x4 ≥ 1 (3.1)
Soluções inteiras para 3.1 são quádruplas ordenadas (x1, x2, x3, x4) de inteiros
positivos cuja soma é 11, por exemplo (2, 2, 4, 3), (1, 8, 1, 1), (3, 4, 2, 2).
Com objetivo de contar todas as soluções positivas de 3.1, vamos escrever 11
como soma de onze 1′s, ou seja,
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 11 (3.2)
Iremos separar 11 em parcelas de 1′s em quatro parcelas, sendo cada elas um
inteiro positivo. Para isso vamos colocar três barras (|) entre os 1′s em 3.2. Por
exemplo,
1 + 1︸ ︷︷ ︸
2
| +1 + 1︸ ︷︷ ︸
2
| +1 + 1 + 1 + 1︸ ︷︷ ︸
4
| +1 + 1 + 1︸ ︷︷ ︸
3
= 11,
e temos a solução (2, 2, 4, 3).
Observe que temos 10 sinais de + entre os onze 1′s e queremos colocar as 3
barras dentre os 10 sinais de + que separam os 1′s.
(1, 8, 1, 1) → 1| + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1| + 1| + 1 = 11
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
3.5. SOLUÇÕES DE EQUAÇÕES LINEARES EM N COM COEFICIENTES UNITÁRIOS23
(3, 4, 2, 2) → 1 + 1 + 1| + 1 + 1 + 1 + 1| + 1 + 1| + 1 + 1 = 11.
Portanto o nosso problema resume-se em escolhermos três dentro os 10 sinais ”+”
para colocarmos as 3 barras separadoras.
+ + + + + + + + +
Portanto a solução do problema é
(
10
3
)
Proposição 3. O número de soluções inteiras positivas da equação
x1 + x2 + ... + xr = m, (3.3)
onde xi, para i = 1, 2, ..., r e m são inteiros é igual a
(
m − 1
r − 1
)
.
Demonstração: Como estamos interessados em expressar o inteiro positivo m
como soma de r inteiros positivos basta colocarmos r − 1 barras divisoras entre os
m1′s. Como cada possível distribuição das barras corresponde uma única solução
para a equação 3.3, basta contarmos de quantas formas isto pode ser feito. Deve-
mos selecionar r − 1 dos m − 1 possíveis locais (os sinais ” + ” que separam os
1′s) para a colocação das barras divisoras, o que pode ser feito de
(m−1
r−1
)
maneiras
diferentes.�
O número de soluções positivas inteiras de x1 + x2 = 5 é
(
5 − 1
2 − 1
)
=
(
4
1
)
=
4, como tínhamos visto anteriormente.
Nossa próxima questão é determinar o número de soluções da equação 3.3
não negativas, ou seja, xi ≥ 0, para i = 1, 2, ..., r. Por exemplo, (5, 0) e (0, 5) são
soluções de x1 +x2 = 5. Nesse caso é 4+2 = 6 =
(
5 + 2 − 1
2 − 1
)
=
(
5 + 2 − 1
5
)
.
Proposição 4. Sejam xi e m inteiros. O número de soluçẽs inteiras não negativas
da equação
x1 + x2 + ... + xr = m, xi ≥ 0 (3.4)
é igual a
(
m + r − 1
r − 1
)
=
(
m + r − 1
r
)
.
Demostração:Some 1 em cada variável x1, x2, ..., xr e dai obtemos 3.4 é equi-
valente a
(x1 + 1) + (x2 + 1) + ... + (xr + 1) = m + r, xi + 1 ≥ 1.
Faça yi = xi + 1 e observe que yi ≥ 1.
Então 3.4 é equivalente a
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
F
R
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
F
R
J
-
24CAPÍTULO 3. APLICAÇÕES DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
y1 + y2 + ... + yr = m + r, yi ≥ 1 (3.5)
As soluções de 3.5 são soluçẽs de 3.4 e vice-versa. Portanto segue da proposi-
ção 4 que o número de soluçẽs de 3.4 é igual a
(
m + r − 1
r
)
. �
Exemplo 3.8. Encontrar o número de soluções em inteiros não negativos da equa-
ção
x1 + x2 + x3 = 16 onde xi ≤ 7. (3.6)
Solução 3.8. O número de soluções inteiras não negativas de x1 + x2 + x3 = 16
é
(
16 + 3 − 1
3 − 1
)
=
(
18
2
)
= 18!
16!2!
= 18 · 17
2
= 9 · 17 = 153. Queremos as
soluções (x1, x2, x3) tal que 0 ≤ xi ≤ 7.
Vamos calcular todas as soluções em que x1 > 7 ou x2 > 7 ou x3 > 7 e sub-
trair do total 153 e esse valor é total de soluções de 3.6. Para isso vamos definir:
A1= conjunto das soluçẽs (x1, x2, x3) de x1 + x2 + x3 = 16, com x1 > 7;
A2= conjunto das soluções (x1, x2, x3) de x1 + x2 + x3 = 16, com x2 > 7;
A3= conjunto das soluções (x1, x2, x3) de x1 + x2 + x3 = 16, com x3 > 7;
A1 ∩ A2= conjunto das soluções (x1, x2, x3) de x1 + x2 + x3 = 16, com x1 > 7
e x2 > 7;
A1 ∩ A3= conjunto das soluções (x1, x2, x3) de x1 + x2 + x3 = 16, com x1 > 7
e x3 > 7;
A2 ∩ A3=conjunto das soluções (x1, x2, x3) de x1 + x2 + x3 = 16, com x2 > 7 e
x3 > 7;
A1 ∩ A2 ∩ A3= conjunto das soluções (x1, x2, x3) de x1 + x2 + x3 = 16, com
x1 > 7, x2 > 7 e x3 > 7.
Vamos calcular n(A1)
x1 + x2 + x3 = 16, com x1 > 7 e x2, x3 ≥ 0. Os outros casos são análogos:
n(A2) e n(A3).
Faça y1 = x1 − 7 e y2 = x2; y3 = x3, então temos que nossa equação é equi-
valente a y1 + y2 + y3 = 9 com y1 > 0 e y2, y3 ≥ 0. Agora faça z1 = y1 − 1 e
z2 = z2; z3 = x3, então temos que nossa equação é equivalente a z1 +z2 +z3 = 8
com z1, z2, z3 ≥ 0.
O número de soluções inteiras não negativas de z1 +z2 +z3 = 8 é
(
8 + 3 − 1
3 − 1
)
=(
10
2
)
= 5 · 9 = 45. Logo n(A1) = 45.
Analogamente temos n(A2) = n(A3) = 45.
Vamos calcular n(A1 ∩ A2), os casos n(A1 ∩ A3) e n(A2 ∩ A3) são análogos.
n(A1 ∩ A2) é total de soluções de x1 + x2 + x3 = 16, com x1 > 7 e x2 > 7 e
x3 ≥ 0.
Faça y1 = x1 − 7 e y2 = x2 − 7; y3 = x3, então temos que nossa equação é
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
3.5. SOLUÇÕES DE EQUAÇÕES LINEARES EM N COM COEFICIENTES UNITÁRIOS25
equivalente a y1 + y2 + y3 = 2 com y1 > 0 e y2 > 0, y3 ≥ 0. Agora faça
z1 = y1 − 1, z2 = z2 − 1 e z3 = x3, então temos que nossa equação é equivalente
a z1 + z2 + z3 = 0 com z1, z2, z3 ≥ 0.
O número de soluções inteiras não negativas de z1+z2+z3 = 0 ’e
(
0 + 3 − 1
3 − 1
)
=(
2
2
)
= 1. Logo n(A1∩A2) = 1. Analogamente, n(A1∩A3) = n(A2∩A3) = 1. A
equação x1+x2+x3 = 16,onde xi > 7 não tem solução por 7+7+7 = 21 > 16,
logo n(A1 ∩ A2 ∩ A3) = 0.
A resposta do problema é 153 − 3 · 45 + 3 · 1 = 21.
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
26CAPÍTULO 3. APLICAÇÕES DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO
V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
ea
m
át
ic
a
-R
io
de
Ja
ne
ir
o
-R
J
-I
M
PA
/U
FR
J
-V
II
IB
ie
na
ld
a
So
ci
ed
ad
e
B
ra
si
le
ir
a
de
M
at
em
át
ic
a
R
io
de
Ja
ne
ir
o-
R
J
-I
M
PA
/U
FR
J
-
Referências Bibliográficas
[1] BURGER, M.; HACKL, B.; RING, W. Incorporating topological derivatives
into level set methods. Journal of Computational Physics, v. 194, n. 1, p.
344-362, 2004.
[2] LITTLE, R. W. Elasticity. New Jersey: Prentice-Hall, 1973.
[3] BOYER, CARL B. Historia da matemática. 3.ed. São Paulo: E. Blucher,
2010.
[4] HEFEZ, ABRAMO. Curso de Álgebra Volume 1. 3ed Rio de Janeiro. IMPA.
2002.
[5] SANTOS, J.P. O. E MURARI , I. T. C. Introdução à Análise Combinatória.
3 Ed. Editora da Unicamp. 2002.
[6] STANLEY, R.P. Enumerative Combinatorics, Vol II. Cambridge Studies in
Advanced Mathematics 49. Cambrige Univesity Press, New York, 1997.
[7] SANTOS, L. G.M. O Problema de Lucas, Monografia apresentada ao pro-
grama de Pós-graduação em Matemática do Departamento de Matemática da
UFMG, Belo Horizonte, 2011.
[8] MEC. PCN - PARAMETROS NACIONAIS
DO ENSINO MÉDIO.portal.mec.gov.br. 2000.
www.portal.mec.gov.br/seb/arquivos/pdf/ciencian.pdf
(acesso em 05 de agos. de 2015).
[9] MORGADO, AUGUSTO CEZAR DE O, et al. Análise Combinatória e Pro-
babilidade. Rio de Janeiro: SBM, 1991.
27
COLEÇÃO DO PROFESSOR DE MATEMÁTICA
•	 Logaritmos	- E. L. Lima
•	 Análise	Combinatória	e	Probabilidade	com	as	soluções	dos	exercícios	- A. C. Morgado, J. B. 
Pitombeira, P. C. P. Carvalho e P. Fernandez
•	 Medida	e	Forma	em	Geometria	(Comprimento,	Área,	Volume	e	Semelhança)	- E. L. Lima
•	 Meu	Professor	de	Matemática	e	outras	Histórias	- E. L. Lima
•	 Coordenadas	no	Plano			as	soluções	dos	exercícios	-	E. L. Lima com a colaboração de P. C. P. 
Carvalho
•	 Trigonometria,	Números	Complexos	-	M. P. do Carmo, A. C. Morgado e E. Wagner, Notas 
Históricas de J. B. Pitombeira
•	 Coordenadas	no	Espaço	-	E. L. Lima
•	 Progressões	e	Matemática	Financeira	- A. C. Morgado, E. Wagner e S. C. Zani
•	 Construções	Geométricas	- E. Wagner com a colaboração de J. P. Q. Carneiro
•	 Introdução	à	Geometria	Espacial	- P. C. P. Carvalho
•	 Geometria	Euclidiana	Plana	-	J. L. M. Barbosa
•	 Isometrias	- E. L. Lima
•	 A	Matemática	do	Ensino	Médio	Vol.	1	- E. L. Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
•	 A	Matemática	do	Ensino	Médio	Vol.	2	- E. L. Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
•	 A	Matemática	do	Ensino	Médio	Vol.	3	- E. L. Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
•	 Matemática	e	Ensino	- E. L. Lima
•	 Temas	e	Problemas	-	E. L. Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
•	 Episódios	da	História	Antiga	da	Matemática	- A. Aaboe
•	 Exame	de	Textos:	Análise	de	livros	de	Matemática	-	E. L. Lima
•	 A	Matemática	do	Ensino	Medio		Vol.	4	-	Exercicios	e	Soluções	- E. L. Lima, P. C. P. Carvalho, E. 
Wagner e A. C. Morgado
•	 Construções	Geométricas:	Exercícios	e	Soluções	- S. Lima Netto
•	 Um	Convite	à	Matemática	-	D.C de Morais Filho
•	 Tópicos	de	Matemática	Elementar	-	 Volume 1 - Números Reais - A. Caminha
•	 Tópicos	de	Matemática	Elementar	-		Volume 2 - Geometria Euclidiana Plana - A. Caminha
•	 Tópicos	de	Matemática	Elementar	- Volume 3 - Introdução à Análise - A. Caminha
•	 Tópicos	de	Matemática	Elementar	-	 Volume 4 - Combinatória - A. Caminha
•	 Tópicos	de	Matemática	Elementar	- Volume 5 - Teoria dos Números - A. Caminha
•	 Tópicos	de	Matemática	Elementar	- Volume 6 - Polinômios - A. Caminha
•	 Treze	Viagens	pelo	Mundo	da	Matemática	- C. Correia de Sa e J. Rocha (editores)
•	 Como	Resolver	Problemas	Matemáticos	-	T. Tao
•	 Geometria	em	Sala	de	Aula	- A. C. P. Hellmeister (Comitê Editorial da RPM)
•	 Números	Primos,	amigos	que	causam	problemas	-	P. Ribenboim
•	 Manual	de	Redação	Matemática - D.C de Morais Filho
COLEÇÃO PROFMAT
•	 Introdução	à	Álgebra	Linear	-	A. Hefez e C.S. Fernandez
•	 Tópicos	de	Teoria	dos	Números	-	C. G. Moreira , F. E Brochero e N. C. Saldanha
•	 Polinômios	e	Equações	Algébricas	-	A. Hefez e M.L. Villela
•	 Tópicos	de	Historia	de	Matemática	- T. Roque e J. Bosco Pitombeira
•	 Recursos	Computacionais	no	Ensino	de	Matemática	- V. Giraldo, P. Caetano e F. Mattos
•	 Temas	e	Problemas	Elementares	- E. L. Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
•	 Números	e	Funções	Reais	-	E. L. Lima
•	 Aritmética	-	A. Hefez
•	 Geometria	-	A. Caminha
•	 Avaliação	Educacional	- M. Rabelo
•	 Geometria	Analítica - J. Delgado, K. Frensel e L. Crissaff
•	 Matemática	Discreta	-	A. Morgado e P. C. P. Carvalho
•	 Matemática	e	Atualidade	-	Volume	1	- C. Rousseau e Y. Saint-Aubin
•	 Fundamentos	de	Cálculo	- A. C. Muniz Neto
•	 Matemática	e	Atualidade	-	Volume	2	- C. Rousseau e Y. Saint-Aubin
•	 Exercícios	Resolvidos	de	Álgebra	Linear	-	A. Hefez e C. de Souza Fernandez
•	 Exercícios	Resolvidos	de	Aritmética	- A. Hefez
COLEÇÃO INICIAÇÃO CIENTÍFICA
•	 Números	Irracionais	e	Transcendentes	- D. G. de Figueiredo
•	 Números	Racionais	e	Irracionais	- I. Niven
•	 Tópicos	Especiais	em	Álgebra	- J. F. S. Andrade
COLEÇÃO TEXTOS UNIVERSITÁRIOS
•	 Introdução	à	Computação	Algébrica	com	o	Maple	- L. N. de Andrade
•	 Elementos	de	Aritmética	-	A. Hefez
•	 Métodos	Matemáticos	para	a	Engenharia	-	E. C. de Oliveira e M. Tygel
•	 Geometria	Diferencial	de	Curvas	e	Superfícies	- M. P. do Carmo
•	 Matemática	Discreta	- L. Lovász, J. Pelikán e K. Vesztergombi
•	 Álgebra	Linear:	Um	segundo	Curso	- H. P. Bueno
•	 Introdução	às	Funções	de	uma	Variável	Complexa	-	C. S. Fernandez e N. C. Bernardes Jr.
•	 Elementos	de	Topologia	Geral	- E. L. Lima
•	 A	Construção	dos	Números	- J. Ferreira
•	 Introdução	à	Geometria	Projetiva	- A. Barros e P. Andrade
•	 Análise	Vetorial	Clássica	- F. Acker
•	 Funções,	Limites	e	Continuidade - P. Ribenboim
•	 Fundamentos	de	Análise	Funcional - G. Botelho, D. Pellegrino e E. Teixeira
•	 Teoria	dos	Números	Transcendentes	- D. Marques
•	 Introdução	à	Geometria	Hiperbólica	-	O	modelo	de	Poincaré	- P. Andrade
•	 Álgebra	Linear:	Teoria	e	Aplicações - T. P. de Araújo
•	 Introdução	à	Análise	Matemática	na	Reta - C. I. Doering
•	 Topologia	e	Análise	no	Espaço	Rn - R. Freire de Lima
•	 Equações	Ordinárias	e	Aplicações - B. Scárdua
COLEÇÃO MATEMÁTICA APLICADA
•	 Introdução	à	Inferência	Estatística	-	H. Bolfarine e M. Sandoval
•	 Discretização	de	Equações	Diferenciais	Parciais	- J. Cuminato e M. Meneguette
•	 Fenômenos	de	Transferência	–	com	Aplicações	às	Ciências	Físicas	e	à	Engenharia	volume	1:	
Fundamentos - J. Pontes e N. Mangiavacchi
COLEÇÃO OLIMPÍADAS DE MATEMÁTICA
•	 Olimpíadas	Brasileiras	de	Matemática,	1ª	a	8ª		- E. Mega e R. Watanabe
•	 Olimpíadas	Brasileiras	de	Matemática,	9ª	a	16ª		- C. Moreira e E. Motta, E. Tengan, L. Amâncio, 
N. C. Saldanha e P. Rodrigues
•	 21	Aulas	de	Matemática	Olímpica	- C. Y. Sh
•	 Iniciação	à	Matemática:	Um	Curso	com	Problemas	e	Soluções	- K. I. M. Oliveira e A. J. C. 
Fernández
•	 Olimpíadas	Cearenses	de	Matemática	1981-2005	Nível	Fundamental	-	E. Carneiro, O. Campos e 
M.Paiva
•	 Olimpíadas	Cearenses	de	Matemática	1981-2005	Nível	Médio	- E. Carneiro, O. Campos e M.Paiva
•	 Olimpíadas	Brasileiras	de	Matemática	-	17ª	a	24ª	- C. G. T. de A. Moreira, C. Y. Shine, E. L. R. 
Motta, E. Tengan e N. C. Saldanha
COLEÇÃO FRONTEIRAS DA MATEMÁTICA
•	 Fundamentos	da	TeoriaErgódica	-	M.Viana e K. Oliveira
•	 Tópicos	de	Geometria	Diferencial - A. C. Muniz Neto
•	 Formas	Diferenciais	e	Aplicações	- M. Perdigão do Carmo
COLEÇÃO MATEMÁTICA PARA O ENSINO
•	 Livro	do	Professor	de	Matemática	na	Educação	Básica	Volume	I	Números	Naturais	- C. Ripoll, L. 
Rangel e V. Giraldo
•	 Livro	do	Professor	de	Matemática	na	Educação	Básica	Volume	II	Números	Inteiros	-	C. Ripoll, L. 
Rangel e V. Giraldo