APOSTILA-DE-MAT015-CCO

Prévia do material em texto

MATEMA´TICA DISCRETA
NOTAS DE AULA
LIVRO TEXTO:
Introduc¸a˜o a` Ana´lise Combinato´ria, Jose´ Pl´ınio de
Oliveira Santos, Margarida P. Mello, Idani T. C.
Murari, Editora Cieˆncia Moderna, Quarta edic¸a˜o.
Jair Cunha Filho
Suma´rio
1 Conjuntos e o Princ´ıpio da Induc¸a˜o 1
1.1 Conceitos e notac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Unia˜o, intersec¸a˜o e produto cartesiano . . . . . . . . . 2
1.2 Notac¸a˜o de somato´rio . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Notac¸a˜o de produto´rio . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 O princ´ıpio da induc¸a˜o matema´tica . . . . . . . . . . . . . . . 8
1.5.1 Primeira forma do Princ´ıpio da Induc¸a˜o Matema´tica . 8
1.5.2 Segunda forma do Princ´ıpio da Induc¸a˜o Matema´tica . . 12
2 Princ´ıpios Aditivo e Multiplicativo 14
2.1 Princ´ıpios aditivo e multiplicativo . . . . . . . . . . . . . . . . 14
2.2 Aplicac¸o˜es dos princ´ıpios aditivo e multiplicativo . . . . . . . . 14
2.3 Permutac¸o˜es simples . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Arranjos simples . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Combinac¸o˜es Simples . . . . . . . . . . . . . . . . . . . . . . . 26
3 Aplicac¸o˜es 32
3.1 Equac¸o˜es lineares com coeficientes unita´rios . . . . . . . . . . 32
3.2 Combinac¸o˜es com repetic¸a˜o . . . . . . . . . . . . . . . . . . . 34
3.3 Permutac¸o˜es com repetic¸a˜o . . . . . . . . . . . . . . . . . . . . 35
3.4 Arranjos com repetic¸a˜o . . . . . . . . . . . . . . . . . . . . . . 37
3.5 Permutac¸o˜es circulares . . . . . . . . . . . . . . . . . . . . . . 37
3.6 Coeficientes binomiais . . . . . . . . . . . . . . . . . . . . . . 39
4 O Princ´ıpio da Inclusa˜o e Exclusa˜o 44
4.1 Cardinalidade da unia˜o de n conjuntos . . . . . . . . . . . . . 44
4.2 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Permutac¸o˜es cao´ticas . . . . . . . . . . . . . . . . . . . . . . . 51
4.4 Contando o nu´mero de func¸o˜es . . . . . . . . . . . . . . . . . 54
i
5 Func¸o˜es Geradoras 57
5.1 Func¸a˜o geradora ordina´ria . . . . . . . . . . . . . . . . . . . . 57
5.1.1 Definic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.2 Ca´lculo de coeficientes de func¸o˜es geradoras . . . . . . 61
5.2 Func¸a˜o geradora exponencial . . . . . . . . . . . . . . . . . . . 69
5.2.1 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.2 Definic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3 Partic¸o˜es de um inteiro positivo . . . . . . . . . . . . . . . . . 74
5.3.1 Definic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3.2 Gra´fico de uma partic¸a˜o . . . . . . . . . . . . . . . . . 76
5.3.3 Func¸o˜es geradoras para partic¸o˜es . . . . . . . . . . . . 80
6 Resoluc¸a˜o de Relac¸o˜es de Recorreˆncia usando Func¸o˜es Ge-
radoras 88
7 Princ´ıpio da Casa dos Pombos 95
ii
Cap´ıtulo 1
Conjuntos e o Princ´ıpio da
Induc¸a˜o
1.1 Conceitos e notac¸o˜es
1.1.1 Conjuntos
Um conjunto e´ uma colec¸a˜o qualquer de objetos, chamados seus elementos.
Representamos um conjunto por letras maiu´sculas A, B, C, ... e os elementos
por letras minu´sculas a, b, c, ... .
Exemplo: Seja A o conjunto dos nu´meros pares positivos menores do que
10. Temos
1. A = {2, 4, 6, 8} (notac¸a˜o expl´ıcita).
2. A = {x | 0 < x < 10 e x e´ par} (notac¸a˜o impl´ıcita).
Observac¸o˜es:
1. A cardinalidade de um conjunto A e´ denotada por |A| e e´ o seu nu´mero
de elementos, podendo ser finito ou na˜o.
2. O conjunto vazio ({ } ou φ) e´ aquele que na˜o possui nenhum elemento.
3. O conjunto com apenas um elemento e´ chamado unita´rio.
4. Usamos a notac¸a˜o a ∈ A para indicar que a e´ um elemento do conjunto
A e a notac¸a˜o a 6∈ A para indicar que a na˜o e´ elemento de A.
1
5. Dizemos que A e´ subconjunto de B ou que A esta´ contido em B se todo
elemento de A e´ tambe´m elemento de B. Neste caso, escrevemos
A ⊂ B (A esta´ contido em B),
ou, ainda
B ⊃ A (B conte´m A).
Caso contra´rio, escrevemos
A 6⊂ B (ou B 6⊃ A).
6. φ ⊂ A, ∀A.
7. O conjunto de todos os subconjuntos de um conjunto A e´ chamado de
conjunto das partes de A e e´ indicado por P(A).
8. A = B ⇔ A ⊂ B e B ⊂ A.
9. O conjunto universo, representado por U , e´ aquele que, em cada exem-
plo, conte´m todos os elementos que esta˜o sendo considerados. Se A e
B sa˜o dois subconjuntos de U , definimos o conjunto diferenc¸a A − B
por
A−B = {x ∈ U | x ∈ A e x 6∈ B}.
Exemplo: Se A = {1, 3, 4, 5} e B = {1, 2, 4}, enta˜o
A−B = {3, 5} e B − A = {2}·
10. Seja A um subconjunto de U . O complementar de A em relac¸a˜o a U e´
indicado por A e e´ definido por
A = U − A = {x ∈ U | x 6∈ A}.
1.1.2 Unia˜o, intersec¸a˜o e produto cartesiano
Sejam A e B dois conjuntos. Temos
1. A unia˜o de A e B e´ denotada por A ∪ B e e´ o conjunto dos elementos
que pertencem a A ou a B, ou seja, que pertencem a pelo menos um
dos dois conjuntos. Assim
A ∪B = {x ∈ U | x ∈ A ou x ∈ B}.
De um modo geral, dados n conjuntos A1, A2, ..., An, temos
A1∪A2∪ ...∪An = {x ∈ U | x ∈ A1 ou x ∈ A2 ou ... ou x ∈ An}.
Exemplo: A = {1, 3, 5} e B = {2, 4, 6} ⇒ A ∪B = {1, 2, 3, 4, 5, 6}.
2
2. A intersec¸a˜o de A e B e´ denotada por A∩B e e´ o conjunto dos elementos
que pertencem a A e a B, ou seja, que pertencem simultaneamente aos
dois conjuntos. Assim
A ∩B = {x ∈ U | x ∈ A e x ∈ B}.
De um modo geral, dados n conjuntos A1, A2, ..., An, temos
A1 ∩ A2 ∩ ... ∩ An = {x ∈ U | x ∈ A1 e x ∈ A2 e ... e x ∈ An}.
Se A ∩B = φ, dizemos que A e B sa˜o disjuntos.
Exemplo: A = {1, 2, 3, 5} e B = {2, 6} ⇒ A ∩B = {2}.
3. O produto cartesiano A × B e´ o conjunto dos pares ordenados (a, b)
tais que a ∈ A e b ∈ B. Assim
A × B = {(a, b) | a ∈ A e b ∈ B}.
Dados n conjuntos A1, A2, ..., An, temos
A1 × A2 × · · · × An = {(a1, a2, ..., an) | a1 ∈ A1, a2 ∈ A2, ..., an ∈ An}.
4. As seguintes propriedades sa˜o va´lidas
(a) Para todo A ⊂ U , A ∪ φ = A e A ∩ φ = φ.
(b) A ⊂ B ⇔ A ∪B = B.
(c) A ⊂ B ⇔ A ∩B = A.
(d) A∪(B∪C) = (A∪B)∪C e A∩(B∩C) = (A∩B)∩C (associativa).
(e) A ∪B = B ∪ A e A ∩B = B ∩ A (comutativa).
(f) A∪ (B∩C) = (A∪B)∩ (A∪C) e A∩ (B∪C) = (A∩B)∪ (A∩C)
(distributiva).
(g) A ∪ A = U , A ∩ A = φ, φ = U e U = φ.
(h) A ∪B = A ∩B e A ∩B = A ∪B (leis de De Morgan).
1.2 Notac¸a˜o de somato´rio
Dados dois inteiros r e s, com r ≤ s, definimos a soma
s∑
i=r
ai = ar + ar+1 + · · ·+ as,
3
onde r e s sa˜o chamados limites inferior e superior, respectivamente, e i e´
chamado ı´ndice do somato´rio.
Exemplo:
7∑
i=1
(2i+ 3) = (2 · 1 + 3) + (2 · 2 + 3) + (2 · 3 + 3) + · · ·+ (2 · 7 + 3)
= 5 + 7 + 9 + · · ·+ 17
=
(5 + 17) · 7
2
= 77.
Observac¸a˜o: As seguintes propriedades sa˜o va´lidas
1.
n∑
i=1
k = nk, com k uma constante.
2.
n∑
i=1
kai = k
n∑
i=1
ai, com k uma constante.
3.
n∑
i=1
(ai ± bi) =
n∑
i=1
ai ±
n∑
i=1
bi.
4.
p∑
i=1
ai +
n∑
i=p+1
ai =
n∑
i=1
ai.
5.
n∑
i=1
m∑
j=1
aibj =
(
n∑
i=1
ai
)(
m∑
j=1
bj
)
.
6.
n∑
i=0
ap−i =
p∑
i=p−n
ai.
1.3 Notac¸a˜o de produto´rio
Dados dois inteiros r e s, com r ≤ s, definimos o produto
s∏
i=r
ai = ar · ar+1 · · · · · as,
4
onde r e s sa˜o chamados limites inferior e superior, respectivamente, e i e´
chamado ı´ndice do produto´rio.
Exemplo:
3∏
i=1
(2i) = (2 · 1)× (2 · 2)× (2 · 3)
= 2× 4× 6
= 48.
Observac¸a˜o: As seguintes propriedades sa˜o va´lidas
1.
n∏
i=1
k = kn, com k uma constante.
2.
n∏
i=1
kai = k
n
n∏
i=1
ai, com k uma constante.
3.
n∏
i=1
(aibi) =
(
n∏
i=1
ai
)(
n∏
i=1
bi
)
.
4.
n∏
i=1
aki =
(
n∏
i=n
ai
)k
, com k inteiro positivo.1.4 Exerc´ıcios
1. Avalie a soma
n∑
i=1
(ai − ai−1), considerando a0 = 0.
Soluc¸a˜o:
5
2. Usando o exerc´ıcio anterior, mostre que
(a)
n∑
i=1
i =
n(n+ 1)
2
·
Soluc¸a˜o:
(b)
n∑
i=1
i(i+ 1) =
n(n+ 1)(n+ 2)
3
·
Soluc¸a˜o:
6
3. Obter
n∑
i=1
i2, usando os resultados do exerc´ıcio anterior.
Soluc¸a˜o:
4. Obter o valor de
n∏
i=1
[
1− 1
(i+ 1)2
]
·
Soluc¸a˜o:
7
1.5 O princ´ıpio da induc¸a˜o matema´tica
1.5.1 Primeira forma do Princ´ıpio da Induc¸a˜o Matema´tica
Seja p(n) uma propriedade relativa aos inteiros. Se
1. p(n) e´ verdadeira para n = 1 e
2. p(k) verdadeira implica que p(k + 1) e´ verdadeira,
enta˜o p(n) e´ verdadeira para todo inteiro n ≥ 1.
Exemplos:
1. Fac¸a uma conjectura para a soma
n∑
i=1
(2i − 1) e confirme-a, usando o
princ´ıpio da induc¸a˜o matema´tica.
Soluc¸a˜o:
8
2. Mostrar que a soma dos cubos de treˆs inteiros positivos consecutivos e´
mu´ltiplo de 9.
Soluc¸a˜o:
9
3. Usando o princ´ıpio da induc¸a˜o matema´tica, mostre que
n∑
i=1
i3 =
(
n∑
i=1
i
)2
·
Soluc¸a˜o:
10
4. A sequ¨eˆncia de Fibonacci e´ definida recursivamente por
F1 = 1
F2 = 1
Fn = Fn−1 + Fn−2, n ≥ 3
Ou seja, e´ a sequ¨eˆncia
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...).
Fac¸a uma conjectura para a soma
n∑
i=1
Fi
e confirme-a, usando o princ´ıpio da induc¸a˜o matema´tica.
Soluc¸a˜o:
11
Observac¸a˜o: Nos exemplos anteriores, as sequ¨eˆncias envolvidas eram tais
que o n-e´simo termo pode ser obtido a partir de n e do predecessor imediato
na sequ¨eˆncia, tornando-se natural a aplicac¸a˜o da primeira forma do princ´ıpio
da induc¸a˜o matema´tica. Quando, por exemplo, a sequ¨eˆncia e´ definida re-
cursivamente de modo que o n-e´simo termo depende de dois ou mais termos
anteriores, e´ conveniente o uso da segunda forma do princ´ıpio da induc¸a˜o
matema´tica.
1.5.2 Segunda forma do Princ´ıpio da Induc¸a˜o Matema´-
tica
Seja p(n) uma propriedade relativa aos inteiros. Se
1. p(n) e´ verdadeira para n = 1 e
2. p(n) verdadeira para 1 < n ≤ k implica que p(k + 1) e´ verdadeira,
enta˜o p(n) e´ verdadeira para todo inteiro n ≥ 1.
Exemplos:
1. Sendo Fn o n-e´simo termo da sequ¨eˆncia de Fibonacci, mostrar que para
todo inteiro positivo n, tem-se
Fn <
(
7
4
)n
·
Soluc¸a˜o:
12
2. Sendo Fn o n-e´simo nu´mero de Fibonacci, mostrar que, para todo in-
teiro positivo n
Fn =
1√
5
[(
1 +
√
5
2
)n
−
(
1−√5
2
)n]
·
Soluc¸a˜o:
13
Cap´ıtulo 2
Princ´ıpios Aditivo e
Multiplicativo
2.1 Princ´ıpios aditivo e multiplicativo
1. Princ´ıpio aditivo: Sejam A e B dois conjuntos disjuntos, isto e´,
A ∩ B = φ. Se A tem p elementos e B tem q elementos, enta˜o A ∪ B
tem p+ q elementos.
De um modo geral, se A1, A2, ..., An sa˜o conjuntos disjuntos 2 a 2 e se
Ai tem ai elementos, enta˜o a unia˜o possui a1+ a2+ · · ·+ an elementos.
2. Princ´ıpio multiplicativo: Se um evento A pode ocorrer de m manei-
ras diferentes e, se para cada uma das m maneiras poss´ıveis de A ocor-
rer, um outro evento B pode ocorrer de n maneiras diferentes, enta˜o o
nu´mero de maneiras de ocorrer o evento A seguido do evento B e´ m ·n.
Em termos de conjuntos, se um conjunto A tem m elementos e um
conjunto B tem n elementos, enta˜o o produto cartesiano A × B tem
m · n elementos. De um modo geral, se A1, A2, ..., An sa˜o conjuntos e
Ai tem mi elementos, enta˜o
A1 × A2 × · · · × An tem m1 ·m2 · · ·mn elementos.
2.2 Aplicac¸o˜es dos princ´ıpios aditivo e multi-
plicativo
1. Dados 5 livros diferentes de matema´tica e 7 livros diferentes de f´ısica,
quantas escolhas podemos fazer para pegar um livro de cada disciplina?
14
Soluc¸a˜o:
2. De quantos modos pode-se dar 2 preˆmios a uma classe de 10 alunos,
de modo que na˜o sejam dados a um mesmo aluno?
Soluc¸a˜o:
15
3. Repita o exemplo anterior, se e´ permitido que ambos os preˆmios sejam
dados a um mesmo aluno.
Soluc¸a˜o:
4. Sejam dados 5 livros diferentes de matema´tica, 7 livros diferentes de
f´ısica e 10 livros diferentes de qu´ımica. De quantos modos podemos
escolher 2 livros, com a condic¸a˜o de que na˜o sejam da mesma mate´ria?
Soluc¸a˜o:
16
5. De quantos modos 2 pessoas podem estacionar seus carros numa gara-
gem com 6 vagas?
Soluc¸a˜o:
6. Quantos anagramas de 2 letras diferentes podemos formar com um al-
fabeto de 23 letras?
Soluc¸a˜o:
17
7. Quantos sa˜o os anagramas de 2 letras formadas por uma vogal e uma
consoante escolhidas dentre 18 consoantes e 5 vogais?
Soluc¸a˜o:
8. Ha´ 12 moc¸as e 10 rapazes, onde 5 deles (3 moc¸as e 2 rapazes) sa˜o filhos
da mesma ma˜e e os restantes na˜o possuem parentesco. Quantos sa˜o os
casamentos poss´ıveis?
Soluc¸a˜o:
18
9. Quantos sa˜o os nu´meros que podemos formar com todos os d´ıgitos
1,1,1,1,1,1,1,2 e 3?
Soluc¸a˜o:
10. Obter o nu´mero de divisores de 126.000.
Soluc¸a˜o:
19
Observac¸a˜o: De um modo geral, dado
N = pα11 · pα22 · · · pαnn ,
onde os p
′
is sa˜o primos distintos, o nu´mero de divisores de N e´
(α1 + 1)(α2 + 1) · · · (αn + 1).
11. Quantos subconjuntos possui um conjunto A com n elementos?
Soluc¸a˜o:
12. Quantos nu´meros de 3 algarismos distintos podemos formar com os
d´ıgitos 1, 2, 3, 4, e 5?
Soluc¸a˜o:
20
2.3 Permutac¸o˜es simples
Uma permutac¸a˜o de n objetos distintos e´ qualquer agrupamento ordenado
desses objetos. Denotando por Pn o nu´mero das permutac¸o˜es simples dos n
objetos, enta˜o, pelo princ´ıpio multiplicativo, temos
Pn = n(n− 1)(n− 2) · · · 3 · 2 · 1 = n! ·
Exemplos:
1. Quantos subconjuntos de 3 elementos possui o conjuntoA = {1, 2, 3, 4, 5}?
Soluc¸a˜o:
21
2. De quantos modos 6 carros podem ser estacionados numa garagem com
6 vagas?
Soluc¸a˜o:
3. De quantas maneiras 12 moc¸as e 12 rapazes podem formar pares para
uma danc¸a?
Soluc¸a˜o:
22
4. De quantos modos podemos distribuir 6 objetos diferentes entre 2 pes-
soas, de modo que cada uma receba pelo menos um objeto?
Soluc¸a˜o:
5. Quantos sa˜o os anagramas da palavra UNIFORMES que comec¸am
com consoante e terminam com vogal?
Soluc¸a˜o:
23
2.4 Arranjos simples
Arranjos simples de n elementos tomados p a p, onde n ≥ 1 e p ≤ n, sa˜o
todos os agrupamentos com p elementos distintos que diferem entre si pela
ordem e pela natureza dos elementos.
Denotando porApn o nu´mero de tais arranjos simples, temos, pelo princ´ıpio
multiplicativo, que
Apn = n(n− 1)(n− 2) · · · (n− (p− 1))
=
n(n− 1)(n− 2) · · · (n− (p− 1))(n− p)(n− p− 1) · · · 3 · 2 · 1
(n− p)(n− p− 1) · · · 3 · 2 · 1
Logo
Apn =
n!
(n− p)! ·
Exemplos
1. Quantos anagramas de 2 letras diferentes podemos formar com um
alfabeto de 23 letras?
Soluc¸a˜o:
2. Quantos nu´meros pares e quantos nu´meros ı´mpares entre 100 e 1.000
podemos formar com os algarismos 1, 2, 3, 4 e 5?
Soluc¸a˜o:
24
3. Quantos nu´meros pares com algarismos distintos existem entre 1.000 e
9.999?
Soluc¸a˜o:
4. Quantos nu´meros com 4 ou 5 algarismos, distintos e maiores do que
2000, podemos formar com 0, 1, 3, 5 e 7?
Soluc¸a˜o:
25
2.5 Combinac¸o˜es Simples
Combinac¸o˜es simples de n elementos tomados p a p, onde n ≥ 1 e p ≤ n, sa˜o
todas as escolhas na˜o ordenadas de p destes elementos.
Observac¸o˜es:
1. Usamos a notac¸a˜o Cpn =
(
n
p
)
·
2. Se p > n, define-se Cpn = 0.
3. Como, dada uma escolha na˜o ordenada de p dos n elementos, obtemos,
ao permutar os p elementos, p! arranjos simples, vem
Apn = p!C
p
n.
Logo
Cpn =
Apn
p!
=
n!
p!(n− p)! ·
Exemplos
1. Obter o nu´mero de anagramas formados por 2 vogais e 3 consoantes
dentre 18 consoantes e 5 vogais.
Soluc¸a˜o:
26
2. Quantos triaˆngulos diferentes podem ser trac¸ados, utilizando-se14 pon-
tos de um plano, na˜o havendo 3 pontos na˜o alinhados?
Soluc¸a˜o:
3. Obter o nu´mero de diagonais de um pol´ıgono convexo de n lados.
Soluc¸a˜o:
27
4. Mostrar que Cpn = C
n−p
n , onde C
n−p
n e´ chamada de combinac¸a˜o comple-
mentar de Cpn.
Soluc¸a˜o:
5. De quantas maneiras podemos arrumar em fila 5 sinais (−) e 7 sinais
(/)?
Soluc¸a˜o:
28
6. De quantas maneiras pode-se escoher 3 nu´meros distintos do conjunto
A = {1, 2, 3, ..., 50}, de modo que sua soma seja um mu´ltiplo de 3?
Soluc¸a˜o:
7. De quantos modos pode-se escolher 3 nu´meros do conjuntoA = {1, 2, 3, ..., 30},
de modo que sua soma seja par?
Soluc¸a˜o:
29
8. Dado A = {1, 2, 3, ..., n}, de quantos modos e´ poss´ıvel formar subcon-
juntos de p elementos, nos quais na˜o haja nu´meros consecutivos?
Soluc¸a˜o:
9. De quantos modos pode-se dispor 8 meninas e 12 meninos em fila, de
modo que na˜o haja 2 meninas lado a lado?
Soluc¸a˜o:
30
10. De quantos modos pode-se distribuir 8 bolas distintas entre 3 pessoas,
sendo que as 2 mais velhas recebam 3 bolas cada e a mais nova receba
2 bolas?
Soluc¸a˜o:
11. De quantos modos podemos separar 20 objetos distintos em 6 grupos,
sendo 2 grupos com 3 objetos, 3 grupos com 4 objetos e um grupo com
2 objetos?
Soluc¸a˜o:
31
Cap´ıtulo 3
Aplicac¸o˜es
3.1 Equac¸o˜es lineares com coeficientes unita´-
rios
Teorema: O nu´mero de soluc¸o˜es em inteiros positivos da equac¸a˜o
x1 + x2 + · · ·+ xp = n, n > 0,
e´ dado por Cp−1n−1.
Prova:
Escrevendo n como soma de p 1
′
s, vem
1 + 1 + · · ·+ 1 = n.
Como queremos expressar n como soma de p inteiros positivos, basta colo-
carmos p− 1 barras divisoras entre os m 1′s, conforme segue
1 + 1 + |1 + · · ·+ |1 + · · ·+ |1 + 1 + · · ·+ 1 = n,
onde x1 e´ o nu´mero de 1
′
s que antecedem a primeira barra, x2 e´ o nu´mero
de 1
′
s entre a primeira barra e a segunda barra, e assim por diante, ate´
obtermos xp, que e´ o nu´mero de 1
′
s apo´s a barra p − 1. Logo, o nu´mero de
soluc¸o˜es em inteiros positivos da equac¸a˜o dada e´ igual ao nu´mero de maneiras
de escolher p − 1 posic¸oes (os sinais + que separam os 1′s), para colocar as
barras divisoras, o que pode ser feito de Cp−1n−1 maneiras diferentes.
32
Exemplos
1. Obter o nu´mero de soluc¸o˜es em inteiros positivos da equac¸a˜o
x1 + x2 + x3 + x4 + x5 = 9.
Soluc¸a˜o:
2. Obter o nu´mero de soluc¸o˜es em inteiros na˜o negativos da equac¸a˜o
x1 + x2 + x3 + x4 = 11.
Soluc¸a˜o:
3. Obter o nu´mero de soluc¸o˜es em inteiros positivos maiores do que 3 da
equac¸a˜o
x1 + x2 + x3 = 17.
Soluc¸a˜o:
33
4. Obter o nu´mero de soluc¸o˜es em inteiros positivos da equac¸a˜o
x1 + x2 + x3 = 20,
onde x2 > 5.
Soluc¸a˜o:
3.2 Combinac¸o˜es com repetic¸a˜o
O nu´mero de combinac¸o˜es com repetic¸a˜o de n elementos tomados p a p
e´ indicado por CRpn e e´ o nu´mero de maneiras de selecionarmos p dos n
elementos, onde cada elemento pode ser tomado ate´ p vezes.
Denotando por a1, a2, ..., an os n elementos, seja xi o nu´mero de vezes em
que o elemento ai e´ tomado. Enta˜o
x1 + x2 + · · ·+ xn = p
e CRpn e´ o nu´mero de soluc¸o˜es em inteiros na˜o negativos da equac¸a˜o acima,
isto e´
CRpn = C
n−1
n+p−1 = C
p
n+p−1 .
Exemplos
1. De quantos modos podemos comprar 4 refrigerantes num local que
vende 2 tipos de refrigerantes?
Soluc¸a˜o:
34
2. De quantos modos podemos distribuir 10 objetos iguais em 4 caixas
diferentes?
Soluc¸a˜o:
3. Dispondo de 4 cores diferentes, de quantos modos podemos pintar 5
objetos ideˆnticos?
Soluc¸a˜o:
3.3 Permutac¸o˜es com repetic¸a˜o
O nu´mero de permutac¸o˜es com repetic¸a˜o de n elementos, onde n1 elementos
sa˜o iguais a a1, n2 elementos sa˜o iguais a a2, ..., nr elementos sa˜o iguais a ar,
com n1 + n2 + · · ·+ nr = n, e´ indicado por
PR(n;n1, n2, ..., nr)
e e´ igual ao nu´mero de maneiras de colocarmos em fila estes n elementos.
35
Para obtermos este nu´mero, precisamos escolher n1 lugares para a co-
locac¸a˜o dos a
′
1s. Dos n − n1 lugares restantes, devemos escolher n2 lugares
para a colocac¸a˜o dos a
′
2s, e assim por diante. Desse modo
PR(n;n1, n2, ..., nr) = C
n1
n C
n2
n−n1C
n3
n−n1−n2 · · ·Cnrn−n1−···−nr−1
=
n!
n1!(n− n1)! ×
(n− n1)!
n2!(n− n1 − n2)! ×
× (n− n1 − n2)!
n3!(n− n1 − n2 − n3)! × · · · ×
× (n− n1 − · · · − nr−1)!
nr!(n− n1 − · · · − nr)!
=
n!
n1!n2!n3! · · ·nr! ·
Exemplos
1. Quantos sa˜o os anagramas da palavra ARARAS?
Soluc¸a˜o:
2. Se um time de futebol jogou 13 partidas em um campeonato, tendo
perdido 5 jogos, empatado 2 e vencido 6 jogos, de quantos modos isto
pode ter ocorrido?
Soluc¸a˜o:
36
3.4 Arranjos com repetic¸a˜o
O nu´mero de arranjos com repetic¸a˜o de n elementos distintos, tomados p a
p e´ indicado por ARpn e e´ o nu´mero de agrupamentos ordenados de p destes
elementos, sendo permitidas repetic¸o˜es. Pelo princ´ıpio multiplicativo, temos
ARpn = n× n× n× · · · × n (p vezes)
= np .
Exemplo: Obter o nu´mero de placas de carros que podem ser constru´ıdas,
com 3 letras seguidas por 4 algarismos.
Soluc¸a˜o:
3.5 Permutac¸o˜es circulares
O nu´mero de permutac¸o˜es circulares de n objetos distintos e´ indicado por
PCn e e´ o nu´mero de maneiras de dispor os n objetos em torno de um c´ırculo.
Observac¸a˜o: Duas distribuic¸o˜es onde uma pode ser obtida a partir da outra
por uma simples rotac¸a˜o sa˜o consideradas ideˆnticas.
Exemplo: Consideremos todas as permutac¸o˜es simples de a, b e c e colo-
quemos cada uma delas em um c´ırculo, conforme ilustrac¸a˜o
37
onde observamos que tanto na primeira linha quanto na segunda, cada uma
das 3 figuras pode ser obtida por uma simples rotac¸a˜o das outras. Pore´m,
nenhuma das 3 figuras da primeira linha pode ser obtida, por rotac¸a˜o de
nenhuma das 3 figuras da segunda linha.
Logo, ha´ apenas 2 permutac¸o˜es circulares dos objetos a, b e c, que esta˜o
ilustradas abaixo
Como 3 permutac¸o˜es simples distintas geram a mesma permutac¸a˜o circular,
vem
PC3 =
3!
3
= 2.
Para o caso de permutac¸o˜es circulares de n objetos, teremos
PCn =
n!
n
= (n− 1)! .
Exemplos
1. O nu´mero de permutac¸o˜es circulares de 7 objetos e´
PC7 = (7− 1)! = 6! = 120.
2. De quantos modos 8 pessoas podem se reunir em torno de uma mesa
circular, se duas determinadas delas ficam sempre lado a lado?
Soluc¸a˜o:
38
3.6 Coeficientes binomiais
Seja
(a+ b)n = (a+ b)(a+ b) · · · (a+ b) (n vezes).
Na expansa˜o acima, cada termo sera´ da forma aibn−i, que ira´ aparecer para
cada escolha da letra a em i dos n fatores, i = 0, 1, 2, ..., n. Como isto pode
ser feito de C in maneiras diferentes, obtemos a conhecida expansaa˜o binomial
(a+ b)n = C0na
0bn + C1na
1bn−1 + · · ·+ Cnnanb0
=
n∑
i=0
Cina
ibn−i ·
Observac¸o˜es:
1. O nu´mero Cin =
(
n
i
)
e´ chamado coeficiente binomial.
2. O i-e´simo termo da expansa˜o e´ dado por
Ti+1 = C
i
na
ibn−i .
3. Trocando b por a, obtemos
(b+ a)n =
n∑
i=0
Cinb
ian−i ·
Como o coeficiente de an−ibi e´ Cn−in , temos
C in = C
n−i
n ,
isto e´, os coeficientes dos termos equidistantes dos extremos sa˜o iguais.
4. Listamos abaixo algumas expanso˜es de (a+ b)n
(a+ b)0 = 1
(a+ b)1 = a+ b
(a+ b)2 = a2 + 2ab+ b2
(a+ b)3 = a3 + 3a2b+ 3ab2 + b3
(a+ b)4 = a4 + 4a3b+ 6a2b2 + 4ab3 + b4
(a+ b)5 = a5 + 5a4b+ 10a3b2 + 10a2b3 + 5ab4 + b5
(a+ b)6 = a6 + 6a5b+ 15a4b2 + 20a3b3 + 15a2b4 + 6ab5 + b6
O triaˆngulo formado pelos coeficientes das expanso˜es acima e´ chamado
de triaˆngulo de Pascal, ou seja
39
linha 0 → 1
linha 1 → 1 1
linha 2 → 1 2 1
linha 3 → 1 3 3 1
linha 4 → 1 4 6 4 1
linha 5 → 1 5 10 10 5 1
linha 6 → 1 6 15 20 15 6 1
...
...
...
...
...
...
...
col. 0 col. 1 col. 2 col. 3 col. 4 col. 5 col.6
ou ainda
linha 0 → C00
linha 1 → C01 C11
linha 2 → C02 C12 C22
linha 3 → C03 C13 C23 C33
linha 4 → C04 C14 C24 C34 C44
linha 5 → C05 C15 C25 C35 C45 C55
linha 6 → C06 C16 C26 C36 C46 C56 C66
...
...
...
...
...
...
...
col. 0 col. 1 col. 2 col. 3 col. 4 col. 5 col. 6
5. Fazendo a = b = 1 em
(a+ b)n =
n∑
i=0
Cina
ibn−i,
obtemos
n∑
i=0
Cin = 2
n,
isto e´, a soma dos elementos da n-e´sima linha e´ 2n.
6. A seguinte identidade vale
Cpn + C
p+1
n = C
p+1
n+1 .
De fato:
Seja um conjunto A com n + 1 elementos e a um desses n elementos.
Quando tomamos um subconjunto arbitra´rio dos Cp+1n+1 subconjuntos de
A que conteˆm exatamente p+1 elementos, temos 2 possibilidades com
40
relac¸a˜o a` presenc¸a de a: ou esta´ presente ou na˜o esta´ presente. Logo,
a soma do nu´mero de subconjuntos que conteˆm a, que e´
cpn
com o nu´mero de subconjuntos que na˜o conteˆm a, que e´
Cp+1n
e´ i gual ao nu´mero de subconjuntos com p+ 1 elementos.
Exemplos
1. Obter o quarto termo na expansa˜o de (1+x)8, segundo poteˆncias cres-
centes de x.
Soluc¸a˜o:
2. Obter o sexto termo na expansa˜o de (x − 5y)10, segundo poteˆncias
crescentes de x.
Soluc¸a˜o:
41
3. Obter o termo independente de x na expansa˜o de(
x2 +
1
x
)6
·
Soluc¸a˜o:
4. Mostrar que
Cpp + C
p
p+1 + C
p
p+2 + · · ·+ Cpp+n = Cp+1p+n+1 .
Soluc¸a˜o:
42
5. Mostrar que
1 + 2 + 3 + · · ·+ n = n(n+ 1)
2
·
Soluc¸a˜o:
6. Expressar em func¸a˜o de n a soma
n∑
i=1
i(i+ 1) .
Soluc¸a˜o:
43
Cap´ıtulo 4
O Princ´ıpio da Inclusa˜o e
Exclusa˜o
4.1 Cardinalidade da unia˜o de n conjuntos
Teorema 1.1 (Princ´ıpio da Inclusa˜o e Exclusa˜o.) O nu´mero de ele-
mentos na unia˜o de n conjuntos finitos A1, A2, ..., An sera´ denotado por
n(A1 ∪ A2 ∪ ... ∪ An), que e´ dado por
n(A1 ∪ A2 ∪ ... ∪ An) =
n∑
i=1
n(Ai)−
∑
1≤i<j≤n
n(Ai ∩ Aj)
+
∑
1≤i<j<k≤n
n(Ai ∩ Aj ∩ Ak)
−
∑
1≤i<j<k<p≤n
n(Ai ∩ Aj ∩ Ak ∩ Ap) + · · ·
+ (−1)n−1 · n(A1 ∩ A2 ∩ ... ∩ An)
Exemplos:
1. n(A1 ∪ A2) = n(A1) + n(A2)− n(A1 ∩ A2).
Ilustrac¸a˜o:
44
2. n(A1 ∪A2 ∪A3) = n(A1)+n(A2)+n(A3)−n(A1 ∩A2)−n(A1 ∩A3)−
n(A2 ∩ A3) + n(A1 ∩ A2 ∩ A3).
Ilustrac¸a˜o:
4.2 Exerc´ıcios
1. Quantos nu´meros de 1 a 3.600 na˜o sa˜o divis´ıveis por 3, 5 ou 7?
Soluc¸a˜o:
45
.
2. Obter o nu´mero de permutac¸o˜es das letras da palavra BRASIL em
que o B ocupa o primeiro lugar, ou o R o segundo lugar, ou L o sexto
lugar.
Soluc¸a˜o:
46
3. Dentre os nu´meros de 1 a 1.000.000, quantos na˜o sa˜o quadrados per-
feitos, cubos perfeitos nem quartas poteˆncias perfeitas?
Soluc¸a˜o:
47
4. De quantos modos 6 casais podem sentar-se ao redor de uma mesa
circular, de modo que marido e mulher na˜o fiquem juntos?
Soluc¸a˜o:
48
5. Func¸a˜o φ de Euler: A func¸a˜o φ de Euler e´ a func¸a˜o que a cada inteiro
positivo m associa o nu´mero de inteiros positivos menores do que ou
iguais a m e relativamente primos com m.
Exemplos:
(a) m = 1 ⇒ φ(1) = 1: 1
(b) m = 2 ⇒ φ(2) = 1: 1
(c) m = 3 ⇒ φ(3) = 2: 1, 2
(d) m = 4 ⇒ φ(4) = 2: 1, 3
(e) m = 5 ⇒ φ(5) = 4: 1, 2, 3, 4
Note que se m e´ primo, enta˜o φ(m) = m− 1.
Mostre que φ(m) e´ dado por
φ(m) =
(
1− 1
p1
)(
1− 1
p2
)
· · ·
(
1− 1
pr
)
,
onde p1, p2, ..., pr sa˜o os divisores primos de m, isto e´, os primos na
decomposic¸a˜o de m em fatores primos:
m = pα11 p
α2
2 · · · pαrr ·
Soluc¸a˜o:
49
.
50
4.3 Permutac¸o˜es cao´ticas
Uma permutac¸a˜o de a1, a2, ..., an e´ dita ser cao´tica (ou desarranjo) se nenhum
dos a
′
is se encontra na posic¸a˜o original, isto e´ na i-e´sima posic¸a˜o.
Exemplo: Dentre as 6 permutac¸o˜es de a, b, c
abc bca
acb cab
bac cba
apenas bca e cab sa˜o cao´ticas.
O nu´mero de permutac¸o˜es cao´ticas de n elementos a1, a2, ..., an e´ denotado
por Dn e e´ dado por
Dn = n!
(
1− 1
1!
+
1
2!
− 1
3!
+ · · ·+ (−1)n · 1
n!
)
·
De fato:
51
.
Exemplos:
1. Se n = 5, temos
D5 = 5!
(
1− 1
1!
+
1
2!
− 1
3!
+
1
4!
− 1
5!
)
=
5
2!
− 5
3!
+
5
4!
− 1
= 60− 20 + 5− 1
= 44
2. Obter o nu´mero de permutac¸o˜es de 1, 2, 3, ..., 10 que teˆm exatamente 4
nu´meros em suas posic¸o˜es originais.
Soluc¸a˜o:
52
3. Obter o nu´mero de permutac¸o˜es cao´ticas de a1, a2, a3, ..., a8, com a
condic¸a˜o de que os 4 primeiros elementos sa˜o transformados
(a) no conjunto {a5, a6, a7, a8} em alguma ordem;
(b) no conjunto {a1, a2, a3, a4} em alguma ordem.
Soluc¸a˜o:
Observac¸a˜o: Para todo inteiro positivo n, temos
Dn =
{
n!
e
}
,
onde {x} denodta o inteiro mais pro´ximo de x.
De fato:
53
4.4 Contando o nu´mero de func¸o˜es
Sejam os conjuntos A e B, com n(A) = n e n(B) = k. Temos
1. Se n = k, o nu´mero de func¸o˜es bijetoras f : A→ B e´ n!.
De fato:
2. Se n ≤ k, o nu´mero de func¸o˜es injetoras f : A→ B e´
k(k − 1)(k − 2) · · · ((k − (n− 1)) = k!
(k − n)! = A
n
k .
3. Se n ≥ k, o nu´mero de func¸o˜es sobrejetoras f : A→ B e´
T (n, k) =
k∑
i=0
(−1)i
(
k
i
)
(k − i)n .
De fato:
54
.
55
Exemplo: Obter o nu´mero de maneiras em que 9 motoristas podem se
agrupar para levar 4 carros de uma cidade A para uma cidade B, na˜o consi-
derando quem dirige no caso de 2 ou mais pessoas estiverem no mesmo carro.
Soluc¸a˜o:
56
Cap´ıtulo 5
Func¸o˜es Geradoras
5.1 Func¸a˜o geradora ordina´ria
5.1.1 Definic¸a˜o
Se ar, r = 0, 1, 2, ..., e´ o nu´mero de soluc¸o˜es de um problema de combinato´ria,
a func¸a˜o geradora ordina´ria para este problema e´ a se´rie de poteˆncias
a0 + a1x+ a2x
2 + · · · =
∞∑
n=0
anx
n . (1)
Observac¸a˜o: Mais geralmente, dada a sequeˆncia (ar), a func¸a˜o geradora
para ela e´ a se´rie de poteˆncias estabelecida em (1).
Exemplos
1. Obter a func¸a˜o geradora ordina´ria para a sequeˆncia (ar), com ar = 1,
r = 0, 1, 2, ... .
Soluc¸a˜o:
Nota: Sabemos que para |x| < 1, tem-se
f(x) =
1
1− x ·
No contexto de func¸o˜es geradoras, estaremos interessados apenas nos
coeficientes da se´rie de poteˆncias e nunca precisaremos atribuir valores
a` varia´vel x. Por este motivo, manipularemos tais se´ries sem preocu-
parmos com questo˜es de convergeˆncia.
57
2. Obter a func¸a˜o geradora ordina´ria para a sequeˆncia (ar) = (0, 0, 1, 1, 1, ...).
Soluc¸a˜o:
3. Obter a sequeˆncia cuja func¸a˜o geradora ordina´ria e´
f(x) =
1
1− x2 ·
Soluc¸a˜o:
4. Obter a sequeˆncia cuja func¸a˜o geradora ordina´ria e´
f(x) = x2 + x3 + ex .
Soluc¸a˜o:
58
5. Obter a func¸a˜o geradora ordina´ria na qual o coeficiente ar de x
r e´ o
nu´mero de soluc¸o˜es em inteiros positivos de
x1 + x2 + x3 = r,
onde
2 ≤ x1 ≤ 4, 2 ≤ x2 ≤ 4, 5 ≤ x3 ≤ 7 e r ∈ {9, 10, 11, 12, 13, 14, 15} .
Soluc¸a˜o:
Observac¸a˜o: O nu´mero de soluc¸o˜es do tipo acima de x1+x2+x3 = 13
e´ o coeficiente de x13, isto e´, 6.
6. Encontrar a func¸a˜o geradora ordina´ria para o problema de obter o
nu´mero de soluc¸o˜es em inteiros na˜o negativos da equac¸a˜o
2x+ 3y + 7z = r.
Soluc¸a˜o:
59
Observac¸a˜o: O coeficiente de x6 e´ 2, que e´ obtido tomando
(a) x6 no primeiro fator e 1 nos segundo e terceiro fatores:
x1 = 6, x2 = x3 = 0⇒ x = 3, y = 0, z = 0.
(b) x6 no segundo fator e 1 nos primeiro e terceiro fatores:
x1 = 0, x2 = 6, x3 = 0⇒ x = 0, y = 2, z = 0.
7. Obter o coeficiente de x23 na expansa˜o de (1 + x5 + x9)6.
Soluc¸a˜o:
60
Observac¸a˜o: (1 + x5 + x9)6 e´ a func¸a˜o geradora ordina´ria para o
nu´mero de soluc¸o˜es em inteiros na˜o negativos da equac¸a˜o
x1 + x2 + x3 + x4 + x5 + x6 = 23, xi ∈ {0, 5, 9}.
5.1.2 Ca´lculo de coeficientes de func¸o˜es geradoras
Teorema 1: Se f(x) e g(x) sa˜o as func¸o˜es geradoras para as sequeˆncias (ar)
e (br),respectivamente, e A e B sa˜o duas constantes, enta˜o
1. Af(x) + Bg(x) e´ a func¸a˜o geradora para a sequeˆncia (Aar +Bbr).
2. f(x)g(x) =
∞∑
n=0
(
n∑
k=0
akbn−k
)
xn .
3. A func¸a˜o geradora para a sequeˆncia (cr), com cr = a0 + a1 + · · · + ar,
isto e´
(a0, a0 + a1, a0 + a1 + a2, ...)
e´
(1 + x+ x2 + · · · )f(x) = 1
1− xf(x) .
4. A func¸a˜o geradora para a sequeˆncia dr, com dr = rar, isto e´
(dr) = (0a0, 1a1, 2a2, ...)
e´ xf
′
(x).
5.
∫
f(x)dx =
∞∑
n=0
an
n+ 1
xn+1 .
Prova de (1), (2) e (3):
61
.
62
Exemplos
1. Obter a func¸a˜o geradora para a sequeˆncia ar, com ar = r, r = 0, 1, 2, ... .
Soluc¸a˜o:
2. Obter a func¸a˜o geradora para a sequeˆncia ar, com ar = r
2, r =
0, 1, 2, ... .
Soluc¸a˜o:
63
3. Obter a func¸a˜o geradora para a sequeˆncia ar, com ar = 2r + 3r
2, r =
0, 1, 2, ... .
Soluc¸a˜o:
Teorema 2: (Teorema binomial) Se |x| < 1 e u ∈ R, enta˜o
(1 + x)u = 1 + ux+
u(u− 1)
2!
x2 + · · ·+ u(u− 1) · · · (u− r + 1)
r!
xr + · · · ·
Observac¸o˜es:
1. Denotando por
(
u
r
)
=

u(u−1)···(u−r+1)
r!
, r > 0
1 , r = 0
podemos escrever
(1 + x)u =
∞∑
r=0
(
u
r
)
xr .
2. O nu´mero
(
u
r
)
e´ chamado coeficiente binomial generalizado.
64
3. Se u for um inteiro positivo n, enta˜o
(
u
r
)
sera´ o conhecido coeficiente
binomial
(
n
r
)
.
De fato:
4. Considerando a observac¸a˜o anterior, como
(
n
r
)
= 0 para r > n, a
expansa˜o acima se reduzira´ a` expansa˜o binomial usual
(1 + x)u =
n∑
r=0
(
n
r
)
xr .
5. Se u = −n, com n inteiro positivo, enta˜o( −n
r
)
= (−1)r ·
(
n+ r − 1
r
)
·
65
De fato:
Por exemplo ( −5
4
)
= (−1)4 ·
(
5 + 4− 1
4
)
=
(
8
4
)
= 70
66
Exemplos
1. Mostrar que o nu´mero de soluc¸o˜es em inteiros na˜o negativos de
x1 + x2 + · · ·+ xn = p
e´ Cpn+p−1 .
Soluc¸a˜o:
2. Obter uma fo´rmula para a soma
12 + 22 + · · ·+ n2 .
Soluc¸a˜o:
67
.
3. Obter o nu´mero de maneiras de obter 17 pontos no lanc¸amento de 4
dados distintos.
Soluc¸a˜o:
68
5.2 Func¸a˜o geradora exponencial
5.2.1 Introduc¸a˜o
Seja o problema de obter o nu´mero de maneiras de retirar 4 livros e coloca´-los
em ordem numa prateleira, dispondo de 3 tipos de livros a, b, c, sendo que o
livro a pode ser retirado no ma´ximo 1 vez, o livro b no ma´ximo 3 vezes e o
livro c no ma´ximo 2 vezes.
Temos
1. As retiradas poss´ıveis sa˜o
a, b, b, b
b, b, b, c
a, b, b, c
b, b, c, c
a, b, c, c
Ordenando, temos que o nu´mero de maneiras e´
N =
4!
1!3!
+
4!
3!1!
+
4!
1!2!1!
+
4!
2!2!
+
4!
1!1!2!
= 4 + 4 + 12 + 6 + 12
= 38
2. A func¸a˜o geradora ordina´ria que fornece as poss´ıveis escolhas, sem con-
siderar a ordem, e´
g1(x) = (1 + ax)(1 + bx+ b
2x2 + b3x3)(1 + cx+ c2x2)
= 1 + (a+ b+ c)x+ (b2 + ab+ bc+ ac+ c2)x2 +
+ (b3 + ab2 + ac2 + b2c+ abc+ bc2)x3 +
+ (ab3 + b3c+ ab2c+ b2c2 + abc2)x4 +
+ (ab3c+ b3c2 + ab2c2)x5 +
+ ab3c2x6
69
3. Introduzindo no coeficiente de xn o fator 1
n!
, obtemos
g2(x) =
(
1 +
a
1!
x
)(
1 +
b
1!
x+
b2
2!
x2 +
b3
3!
x3
)(
1 +
c
1!
x+
c2
2!
x2
)
= 1 +
(
a
1!
+
b
1!
+
c
1!
)
x+
(
b2
2!
+
ab
1!1!
+
bc
1!1!
+
ac
1!1!
+
c2
2!
)
x2 +
+
(
b3
3!
+
ab2
1!2!
+
ac2
1!2!
+
b2c
2!1!
+
abc
1!1!1!
+
bc2
1!2!
)
x3 +
+
(
ab3
1!3!
+
b3c
3!1!
+
ab2c
1!2!1!
+
b2c2
2!2!
+
abc2
1!1!2!
)
x4 +
+
(
ab3c
1!3!1!
+
b3c2
3!2!
+
ab2c2
1!2!2!
)
x5 +
+
ab3c2
1!3!2!
x6
4. Multiplicando e dividindo cada termo em xn por n! e fazendo a = b =
c = 1, obtemos a func¸a˜o geradora para o problema
g2(x) =
(
1 +
x
1!
)(
1 +
x
1!
+
x2
2!
+
x3
3!
)(
1 +
x
1!
+
x2
2!
)
= 1 + 3 · x
1!
+
(
2!
2!
+
2!
1!1!
+
2!
1!1!
+
2!
1!1!
+
2!
2!
)
x2
2!
+
+
(
3!
3!
+
3!
1!2!
+
3!
1!2!
+
3!
2!1!
+
3!
1!1!1!
+
3!
1!2!
)
x3
3!
+
+
(
4!
1!3!
+
4!
3!1!
+
4!
1!2!1!
+
4!
2!2!
+
4!
1!1!2!
)
x4
4!
+
+
(
5!
1!3!1!
+
5!
3!2!
+
5!
1!2!2!
)
x5
5!
+
+
6!
1!3!2!
· x
6
6!
e a resposta ao problema e´ o coeficiente de x
4
4!
·
70
5.2.2 Definic¸a˜o
A func¸a˜o geradora exponencial para a sequeˆncia (ar), r = 0, 1, 2, ..., e´ a se´rie
de poteˆncias
a0 + a1
x
1!
+ a2
x2
2!
+ · · · =
∞∑
n=0
an
xn
n!
·
Observac¸a˜o: Usamos a func¸a˜o geradora exponencial quando a ordem dos
elementos deve ser considerada. Caso contra´rio, usamos a func¸a˜o geradora
ordina´ria.
Exemplos
1. Obter a func¸a˜o geradora exponencial para as sequeˆncias
(a) (1, 1, 1, ...).
Soluc¸a˜o:
(b) (ak), com ak = 2
k, k = 0, 1, 2, ....
Soluc¸a˜o:
71
2. Obter a func¸a˜o geradora exponencial para encontrar o nu´mero de sequeˆn-
cias de k letras (k ≤ 6) formadas pelas letras a, b, c, onde a letra a ocorre
no ma´ximo 1 vez, a letra b no ma´ximo 2 vezes e a letra c no ma´ximo 3
vezes.
Soluc¸a˜o:
72
3. Obter o nu´mero de r-sequeˆncias quaterna´rias que conteˆm um nu´mero
par de zeros.
Obs.: uma sequeˆncia quaterna´ria e´ uma r-upla formada somente pelos
d´ıgitos 0,1,2 e 3.
Soluc¸a˜o:
73
5.3 Partic¸o˜es de um inteiro positivo
5.3.1 Definic¸a˜o
Uma partic¸a˜o de um inteiro positivo n e´ uma representac¸a˜o de n na forma
n = λ1 + λ2 + · · ·+ λr,
onde λ1, λ2, ..., λr sa˜o inteiros positivos chamados partes da partic¸a˜o.
Por exemplo:
1. Temos 1 partic¸a˜o de 1: 1
2. Temos 2 partic¸o˜es de 2:
2
2 + 1
3. Temos 3 partic¸o˜es de 3:
3
2 + 1
1 + 1 + 1
4. Temos 5 partic¸o˜es de 4:
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
5. Temos 7 partic¸o˜es de 5:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
74
Observac¸o˜es:
1. Embora a ordem das partes seja irrelevante, e´ comum escreveˆ-las em
ordem na˜o crescente.
2. Denotamos o nu´mero de partic¸o˜es de n por p(n). Assim
p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5 e p(5) = 7.
3. Definimos p(0) = 1, com a observac¸a˜o de que a u´nica partic¸a˜o de n = 0
e´ a partic¸a˜o vazia φ.
4. O nu´mero de partic¸o˜es de n cresce rapidamente com o aumento de n.
Por exemplo 
p(20) = 627
p(100) = 190.569.292
p(200) = 3.972.999.029.388
Exemplos
1. O nu´mero de partic¸o˜es de n = 10 tendo k = 3 como maior parte e´ 8,
as quais sa˜o
3 + 3 + 3 + 1
3 + 3 + 2 + 2
3 + 3 + 2 + 1 + 1
3 + 3 + 1 + 1 + 1 + 1
3 + 2 + 2 + 2 + 1
3 + 2 + 2 + 1 + 1 + 1
3 + 2 + 1 + 1 + 1 + 1 + 1
3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2. O nu´mero de partic¸o˜es de n = 10 em exatamente k = 3 partes e´ 8, as
quais sa˜o
8 + 1 + 1
7 + 2 + 1
6 + 3 + 1
6 + 2 + 2
5 + 4 + 1
5 + 3 + 2
4 + 4 + 2
4 + 3 + 3
75
Observac¸a˜o: Notemos que o nu´mero de partic¸o˜es do primeiro tipo e´ igual
ao nu´mero de partic¸o˜es do segundo tipo. Isto e´ verdade para toto k e todo
n. Este resultado e va´rios outros podem ser demonstrados atrave´s da ma-
nipulac¸a˜o do diagrama de Ferrers, que e´ uma representac¸a˜o gra´fica de uma
partic¸a˜o.
5.3.2 Gra´fico de uma partic¸a˜o
O diagrama de Ferrers de uma partic¸a˜o de um inteiro positivo n e´ a sua
representac¸a˜o gra´fica por meio de n pontos no plano, colocando-se em cada
linha e em ordem na˜o crescente um nu´mero de pontos igual a cada uma de
suas partes.
Abaixo, apresentamos o diagrama de Ferrers da partic¸a˜o 3+3+2+2+1 de
n = 11:
◦ ◦ ◦
◦ ◦ ◦
◦ ◦
◦ ◦
◦
Observac¸o˜es:
1. A conjugada de uma partic¸a˜o de n e´ a partic¸a˜o obtida quando trocamosas linhas pelas colunas. Por exemplo
Partic¸a˜o Partic¸a˜o conjugada
5+2+1 3+2+1+1+1
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦
◦ ◦
◦
◦
e a conjugada da partic¸a˜o 5+ 3+ 2+1+1, cujo diagrama de Ferrers e´
◦ ◦ ◦ ◦ ◦
◦ ◦ ◦
◦ ◦
◦
◦
e´ igual a ela pro´pria.
76
2. Dizemos que uma partic¸a˜o e´ autoconjugada se ela for igual a` sua con-
jungada. Assim, a partic¸a˜o 5 + 3 + 2 + 1 + 1 e´ autoconjugada.
Exemplos
1. Mostrar que o nu´mero de partic¸o˜es de n cuja maior parte e´ k e´ igual
ao nu´mero de partic¸o˜es de n em exatamente k partes.
Por exemplo, para n = 7 e k = 3, temos
Soluc¸a˜o:
77
2. Mostrar que o nu´mero de partic¸o˜es de n em que cada parte aparece pelo
menos 2 vezes e´ igual ao nu´mero de partic¸o˜es de n em partes maiores
do que ou iguais a 2, sem inteiros consecutivos aparecendo como partes.
Por exemplo, para n = 8, as partic¸o˜es do primeiro tipo sa˜o
4 + 4
3 + 3 + 1 + 1
2 + 2 + 2 + 2
2 + 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
e as do segundo tipo sa˜o
2 + 2 + 2 + 2
4 + 2 + 2
4 + 4
6 + 2
8
Soluc¸a˜o:
78
3. Mostrar que o nu´mero de partic¸o˜es autoconjugadas de n e´ igual ao
nu´mero de partic¸o˜es de n em partes ı´mpares distintas.
Por exemplo, para n = 16, temos 4 partic¸o˜es autoconjugadas
8 + 2 + 1 + 1 + 1 + 1 + 1 + 1
7 + 3 + 2 + 1 + 1 + 1 + 1
6 + 4 + 2 + 2 + 1 + 1
5 + 5 + 2 + 2 + 2
e as correspondentes partic¸o˜es em partes ı´mpares distintas
15 + 1
13 + 3
11 + 5
9 + 7
Soluc¸a˜o:
79
5.3.3 Func¸o˜es geradoras para partic¸o˜es
A func¸a˜o geradora para a sequeˆncia (p(0), p(1), p(2), ..., p(n), ...), onde p(n)
e´ o nu´mero de partic¸o˜es de n, e´ a se´rie de poteˆncias
p(0) + p(1)q + p(2)q2 + · · · =
∞∑
n=0
p(n)qn .
Olhando para o produto
∞∏
n=1
1
1− qn
como
∞∏
n=1
1
1− qn =
1
1− q1 ×
1
1− q2 ×
1
1− q3 · · ·
= (1 + q1 + q1+1 + q1+1+1 + · · · )×
× (1 + q2 + q2+2 + q2+2+2 + · · · )×
× (1 + q3 + q3+3 + q3+3+3 + · · · )× · · · ,
temos que a func¸a˜o geradora para as partic¸o˜es de n e´
∞∑
n=0
p(n)qn =
∞∏
n=1
1
1− qn ·
Exemplo: O coeficiente do termo em q3 e´ 3, que e´ o nu´mero de partic¸o˜es
de 3. Os termos em q3 sa˜o
1. q3, obtido tomando q3 no terceiro fator e 1 nos restantes, que nos fornece
a partic¸a˜o
3
2. q1 · q2 = q2+1, obtido tomando q1 no primeiro fator, q2 no segundo e 1
no terceiro, que nos fornece a partic¸a˜o
2+1
3. q1+1+1, obtido tomando q1+1+1 no primeiro fator e 1 nos restantes, que
nos fornece a partic¸a˜o
1+1+1
80
Observac¸a˜o: Dependendo do problema a ser analisado via partic¸o˜es, res-
tric¸o˜es com relac¸a˜o a`s partes devem ser consideradas. Apresentamos abaixo
algumas func¸o˜es geradoras, descrevendo partic¸o˜es com restric¸o˜es.
1.
∞∏
n=1
1
1− q2n e´ a func¸a˜o geradora para partic¸o˜es em partes pares, uma
vez que
∞∏
n=1
1
1− qn =
1
1− q2 ×
1
1− q4 ×
1
1− q6 × · · ·
= (1 + q2 + q2+2 + q2+2+2 + · · · )×
× (1 + q4 + q4+4 + q4+4+4 + · · · )×
× (1 + q6 + q6+6 + q6+6+6 + · · · )× · · ·
2.
∞∏
n=1
1
1− q2n−1 e´ a func¸a˜o geradora para partic¸o˜es em partes ı´mpares.
3.
∞∏
n=1
(1+qn) = (1+q1)(1+q2)(1+q3)... e´ a func¸a˜o geradora para partic¸o˜es
em partes distintas.
4.
∞∏
n=1
(1+q2n) e´ a func¸a˜o geradora para partic¸o˜es em partes pares distintas.
5.
∞∏
n=1
1 + q2n−1
1− q2n e´ a func¸a˜o geradorta para partic¸o˜es onde as partes ı´mpares
sa˜o distintas, na˜o havendo restric¸o˜es quanto a`s partes pares.
6. Seja
∞∏
n=1
1 + qn
1− q2n . Temos
∞∏
n=1
1 + qn
1− q2n = (1 + q
1)(1 + q2)(1 + q3)(1 + q4) · · · ×
× (1 + q2 + q2+2 + · · · )(1 + q4 + q4+4 + · · · ) · · ·
Assim, se trata da func¸a˜o geradora para partic¸o˜es onde as partes ı´mpares
sa˜o distintas e a primeira ocorreˆncia de cada parte par pode ser mar-
cada.
Por exemplo, as partic¸o˜es deste tipo para n = 4 sa˜o
81
4
4
3 + 1
2 + 2
2 + 2
Exerc´ıcios
1. Mostrar que todo inteiro positivo pode ser expresso de maneira u´nica
como soma de poteˆncias distintas de 2.
Soluc¸a˜o:
82
2. Mostrar que o nu´mero de partic¸o˜es de n em partes distintas e´ igual ao
nu´mero de partic¸o˜es de n em partes ı´mpares.
Por exemplo, as partic¸o˜es do primeiro tipo para n = 6 sa˜o
6
5 + 1
4 + 2
3 + 2 + 1
e a partic¸o˜es do segundo tipo sa˜o
5 + 1
3 + 3
3 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
Soluc¸a˜o
83
Observac¸a˜o: Abaixo apresentamos uma demonstrac¸a˜o feita por Euler,
que apresentou uma bijec¸a˜o entre estas duas classes de partic¸o˜es.
84
3. Mostrar que o nu´mero de partic¸o˜es de n em exatamente 2 partes e´⌊n
2
⌋
.
Soluc¸a˜o:
85
4. Mostrar que o nu´mero de partic¸o˜es de n em partes distintas, nenhuma
mu´ltiplo de 3, e´ igual ao nu´mero de partic¸o˜es de n em partes da forma
6j − 1 ou 6j − 5.
Soluc¸a˜o:
86
5. Obter a func¸a˜o geradora para o nu´mero de triaˆngulos na˜o semelhantes
de per´ımetro n e lados inteiros.
Soluc¸a˜o:
Observac¸a˜o: Existe uma fo´rmula fechada para este nu´mero de triaˆngulos:{
n2
12
}
−
⌊n
4
⌋
·
⌊
n+ 2
4
⌋
87
Cap´ıtulo 6
Resoluc¸a˜o de Relac¸o˜es de
Recorreˆncia usando Func¸o˜es
Geradoras
Nosso problema e´, dada uma sequeˆncia (a0, a1, a2, ...), definida por uma
relac¸a˜o de recorreˆncia, obter uma fo´rmula fechada para o n-e´simo termo
an. Para isto, lembrando que
f(x) =
∞∑
n=0
anx
n
e´ a func¸a˜o geradora para a sequeˆncia, seguimos os passos
1. multiplicamos, membro a membro, a relac¸a˜o de recorreˆncia por xn e
somamos membro a membro em n, onde n esta´ definido na tal relac¸a˜o;
2. nas somas, fazemos aparecer
∞∑
n=0
anx
n, que substituimos por f(x);
3. isolamos f(x) e desenvolvemos f(x) em se´rie de poteˆncias;
4. an sera´ o coeficiente de x
n na se´rie de poteˆncias obtida.
Exemplos
1. Seja {Fn}n≥0 a sequeˆncia de Fibonacci dada por
F0 = 0, F1 = 1 e Fn = Fn−2 + Fn−1, n ≥ 2.
Obter uma fo´rmula para Fn.
88
Soluc¸a˜o:
Multiplicando, membro a membro, a relac¸a˜o de recorreˆncia por xn e
somando em n para n ≥ 2, vem
∞∑
n=2
Fnx
n =
∞∑
n=2
Fn−2xn +
∞∑
n=2
Fn−1xn .
Da´ı
∞∑
n=0
Fnx
n − F0 − F1x = x2
∞∑
n=2
Fn−2xn−2 + x
∞∑
n=2
Fn−1xn−1
= x2
∞∑
n=0
Fnx
n + x
∞∑
n=1
Fnx
n
= x2
∞∑
n=0
Fnx
n + x
( ∞∑
n=0
Fnx
n − F0
)
Desse modo, sendo F0 = 0 e F1 = 1
f(x)− x = x2f(x) + xf(x).
Isolando f(x)
f(x) =
−x
x2 + x− 1
=
−x(
x− −1−
√
5
2
)(
x− −1+
√
5
2
)
=
−x[
−−1−
√
5
2
(
1− x−1−√5
2
)][
−−1+
√
5
2
(
1− x−1+√5
2
)]
=
−x
1−5
4
(
1− 2x−√5−1
)(
1− 2x√
5−1
)
=
x(
1− 1−
√
5
2
x
)(
1− 1+
√
5
2
x
)
=
A
1− 1−
√
5
2
x
+
B
1− 1+
√
5
2
x
89
Tirando o mmc e identificando os numeradores, obtemos
x ≡ A
(
1− 1 +
√
5
2
x
)
+B
(
1− 1−
√
5
2
x
)
≡ A+B +
(
−1 +
√
5
2
A− 1−
√
5
2
B
)
De onde obtemos {
A+B = 1
−1+
√
5
2
A− 1−
√
5
2
B = 1
Resolvendo o sistema, obtemos
A = − 1√
5
e B =
1√
5
·
Logo
f(x) =
1√
5
(
1
1− 1+
√
5
2
x
− 1
1− 1−
√
5
2
x
)
=
1√
5
[ ∞∑
n=0
(
1 +
√
5
2
x
)n
−
∞∑
n=0
(
1−√5
2
x
)n]
=
1√
5
∞∑
n=0
[(
1 +
√
5
2
)n
−
(
1−√5
2
)n]
xn
Portanto
Fn =
1√
5
[(
1 +
√
5
2
)n
−
(
1−√5
2
)n]
·
2. A sequeˆncia {pn}n≥0 de Pell e´ definida por
p0 = 1
p1 = 2
pn = 2pn−1 + pn−2, n ≥ 2
Obter uma fo´rmula para pn, para todo n.
90
Soluc¸a˜o:
Seja f(x) =
∞∑
n=0
pnx
n a func¸a˜o geradora para a sequeˆncia {pn}n≥0 de
Pell. Sabemos que
pn = 2pn−1 + pn−2, n ≥ 2.
Multiplicando membro a membro por xn e somando em n, para n≥ 2,
vem ∞∑
n=2
pnx
n = 2
∞∑
n=2
pn−1xn +
∞∑
n=2
pn−2xn ·
Isto e´
∞∑
n=0
(pnx
n − p0 − p1x) = 2x
( ∞∑
n=0
pnx
n − p0
)
+ x2
∞∑
n=0
pnx
n ·
Da´ı
f(x)− 1− 2x = 2x(f(x)− 1) + x2f(x) ·
Isolando f(x), obtemos
f(x) =
−1
x2 + 2x− 1 ·
Decompondo f(x) em frac¸o˜es parciais, obtemos
f(x) =
− 1
2
√
2
x− (−1 +√2) +
1
2
√
2
x− (−1−√2)
= − 1
2
√
2
× −1−1 +√2 ×
1
1− 1−1+√2x
+
1
2
√
2
× 1
1 +
√
2
× 1
1− 1−1−√2x
=
1
4− 2√2
∞∑
n=0
(
1
−1 +√2
)n
xn +
1
4 + 2
√
2
∞∑
n=0
(
1
−1−√2
)n
xn
=
2 +
√
2
4
×
∞∑
n=0
(1 +
√
2)nxn +
2−√2
4
×
∞∑
n=0
(1−
√
2)nxn
=
∞∑
n=0
[
2 +
√
2
4
(1 +
√
2)n +
2−√2
4
(1−
√
2)n
]
xn·
91
Desse modo
pn =
2 +
√
2
4
(1 +
√
2)n +
2−√2
4
(1−
√
2)n ·
3. Os nu´meros pentagonais sa˜o dados por 1, 5, 12, 22, ..., conforme ilus-
trac¸a˜o
Obter uma fo´rmula para pn, o n-e´simo nu´mero pentagonal.
Soluc¸a˜o:
Temos 
p1 = 1
p2 = 1 + 2 + 2× 1
p3 = 5 + 3 + 2× 2
p4 = 12 + 4 + 2× 3
...
Da´ı
pn = pn−1 + n+ 2(n− 1) = pn−1 + 3n− 2 .
Assim, definindo p0 = 0, os nu´meros pentagonais sa˜o dados por
p0 = 0, p1 = 1 e pn = pn−1 + 3n− 2, n ≥ 2 .
Multiplicando, membro a membro, a relac¸a˜o de recorreˆncia por xn e
somando em n para n ≥ 2, vem
∞∑
n=2
pnx
n =
∞∑
n=2
pn−1xn + 3
∞∑
n=2
nxn − 2
∞∑
n=2
xn .
92
Da´ı
∞∑
n=0
pnx
n − p0 − p1x = x
∞∑
n=2
pn−1xn−1 + 3
∞∑
n=2
nxn − 2
∞∑
n=2
xn
= x
∞∑
n=1
pnx
n + 3
( ∞∑
n=0
nxn − p0 − p1x
)
+
− 2 · x
2
1− x
= x
∞∑
n=0
(pnx
n − p0) + 3
[
x ·
(
1
1− x
)′
− p0 − p1x
]
+
− 2x
2
1− x
Desse modo, sendo p0 = 0 e p1 = 1
f(x)− x = xf(x) + 3x
(1− x)2 − 3x−
2x2
1− x ·
Da´ı
f(x) =
3x
(1− x)3 −
2x
1− x −
2x2
(1− x)2
= 3x(1− x)−3 − 2x(1− x)−1 − 2x2(1− x)−2
= 3x
∞∑
r=0
( −3
r
)
(−1)rxr − 2x
∞∑
r=0
( −1
r
)
(−1)rxr
− 2x2
∞∑
r=0
( −2
r
)
(−1)rxr
93
Logo, sendo pn o coeficiente de x
n, temos
pn = 3
( −3
n− 1
)
(−1)n−1 − 2
( −1
n− 1
)
(−1)n−1
− 2
( −2
n− 2
)
(−1)n−2
= 3
(
n+ 1
n− 1
)
− 2
(
n− 1
n− 1
)
− 2
(
n− 1
n− 2
)
= 3 · (n+ 1)n
2
− 2− 2(n− 1)
=
3n(n+ 1)
2
− 2n
=
n(3n+ 3− 4)
2
=
n(3n− 1)
2
·
Observac¸a˜o: Dizemos que (a1, a2, ...an) e´ uma progressa˜o aritme´tica
de segunda ordem se (a2 − a1, a3 − a2, ..., an − an−1) e´ uma progressa˜o
aritme´tica. Pode-se mostrar que, neste caso
an = an
2 + bn+ c.
Como as diferenc¸as entre dois termos consecutivos da sequeˆncia pn
formam uma progressa˜o aritme´tica de primeiro termo 4 e raza˜o 3, vem
pn = an
2 + bn+ c.
Da´ı 
p1 = a · 12 + b · 1 + c
p2 = a · 22 + b · 2 + c
p3 = a · 32 + b · 3 + c
⇒

a+ b+ c = 1 (1)
4a+ 2b+ c = 5 (2)
9a+ 3b+ c = 12 (3)
De (2)− (1) e (3)− (2), obtemos{
3a+ b = 4
5a+ b = 7
Assim
a =
3
2
, b = −1
2
e c = 0
e, enta˜o
pn =
3
2
n2 − 1
2
n =
n(3n− 1)
2
·
94
Cap´ıtulo 7
Princ´ıpio da Casa dos Pombos
O princ´ıpio da casa dos pombos estabelece que
Se n + 1 pombos sa˜o colocados em n gaiolas, enta˜o pelo menos uma gaiola
devera´ conter pelo menos 2 pombos.
Observac¸o˜es:
1. Este princ´ıpio tambe´m e´ conhecido como princ´ıpio das gavetas de Di-
richlet, sendo usualmente enunciado como: ”se colocarmos n objetos
em r gavetas (r < n), enta˜o pelo menos uma gaveta devera´ conter pelo
menos 2 objetos”.
2. Este princ´ıpio e´ u´til na resoluc¸a˜o de problemas de existeˆncia.
Exemplos
1. Em um local com mais de 12 pessoas, pelo menos 2 nasceram no mesmo
meˆs. Ale´m disso, existira˜o pelo menos 2 nascidas no mesmo dia da
semana.
2. Mostrar que todo subconjunto de A = {1, 2, 3, ..., 2n}, contendo n + 1
elementos, possui um par de elementos primos entre si.
Soluc¸a˜o:
95
3. Mostrar que, dentre 9 pontos quaisquer de um cubo de aresta 2, exis-
tem pelo menos 2 pontos que se encontram a uma distaˆncia menor do
que ou igual a
√
3 um do outro.
Soluc¸a˜o:
Observac¸o˜es:
(a) Sejam os conjuntos
C0 = {...,−9,−6,−3, 0 , 3, 6, 9, ...} = {3k : k ∈ Z}
C1 = {...,−8,−5,−2, 1, 4, 7, ...} = {3k + 1 : k ∈ Z}
C2 = {...,−7,−4,−1, 2, 5, 8, ...} = {3k + 2 : k ∈ Z}
Temos
i. C0, C1 e C2 sa˜o disjuntos 2 a 2 e C0 ∪ C1 ∪ C3 = Z. Isto
e´ consequeˆncia do fato de que quando um inteiro qualquer e´
dividido por 3, so´ existem 3 poss´ıveis restos que sa˜o 0, 1 e 2.
ii. Estes conjuntos sa˜o chamados de classes de congrueˆncia mo´dulo
3. Os elementos de Ci sa˜o ditos congruentes a i mo´dulo 3 e a
diferenc¸a entre 2 nu´meros quaisquer de uma mesma classe e´
mu´ltiplo de 3.
iii. Segue do princ´ıpio da casa dos pombos que, dados 4 ou mais
nu´meros inteiros, pelo menos 2 deles esta˜o na mesma classe.
(b) De um modo geral, dado um inteiro positivo n, temos n−1 classes
de congrueˆncia mo´dulo n.
96
4. Mostrar que todo inteiro positivo n possui um mu´ltiplo que se escreve
na base 10, somente com os d´ıgitos 0 e 1.
Soluc¸a˜o:
97
5. Provar que 7 divide infinitos nu´meros da forma 252525...25.
Soluc¸a˜o:
98
6. Mostrar que dados α ∈ R e n > 1 um inteiro, existe um racional p
q
,
com 1 ≤ q ≤ n, tal que ∣∣∣∣α− pq
∣∣∣∣ ≤ 1nq ·
Soluc¸a˜o:
Observac¸a˜o: Isto significa que dado qualquer real x, existe um raci-
onal ta˜o pro´ximo de x quanto quizermos, isto e´, que o conjunto dos
nu´meros racionais e´ denso no conjunto dos nu´meros reais.
99