metodos finitos em matemática - contagem e grafos (1 de 3)

Prévia do material em texto

Métodos Finitos em Matemática
Mestrado em Matemática para Professores
Samuel A. Lopes
16 de Novembro de 2009
2
Conteúdo
1 Introdução 3
2 Métodos elementares de contagem 6
2.1 As leis da soma e do produto . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Bijecções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Convenções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Alguns exerćıcios de aquecimento . . . . . . . . . . . . . . . . . . . . . 11
2.5 Um trilema: três visões de um problema . . . . . . . . . . . . . . . . . 12
2.6 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.7 Permutações, arranjos, combinações . . . . . . . . . . . . . . . . . . . . 19
2.8 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.9 Os teoremas binomial e multinomial . . . . . . . . . . . . . . . . . . . . 28
2.10 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.11 O prinćıpio do pombal . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.12 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3 Introdução à Teoria de Grafos 38
3.1 Definições e exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2 O primeiro resultado . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Passeios em grafos e conexão . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Grafos Eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.6 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.7 Grafos Hamiltonianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.8 O Problema do Caixeiro Viajante . . . . . . . . . . . . . . . . . . . . . 72
3.9 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.10 Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.11 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.12 Fórmula de Euler e coloração de mapas . . . . . . . . . . . . . . . . . . 102
3.13 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
1
CONTEÚDO 2
Bibliografia 114
Caṕıtulo 1
Introdução
Estas notas foram compiladas como texto de apoio à disciplina “Métodos Finitos em
Matemática” da Pós-Graduação em Matemática para Professores (actualmente Mes-
trado em Matemática para Professores) no ano lectivo de 2007/2008. Uma das razões
que me levaram a escrevê-las foi permitir que os alunos se puessem concentrar mais na
aula em si e menos em anotar tudo o que era dito e escrito no quadro, especialmente
por a disciplina funcionar em horário pós-laboral. Penso que desta forma é – e foi –
posśıvel fomentar uma maior intervenção e discussão entre os alunos durante as au-
las bem como a sua participação activa no desenvolvimento dos resultados e das suas
provas.
Procurei que os tópicos escolhidos e a forma como foram abordados fossem espe-
cialmente adequados às necessidades de um professor de matemática do 3o ciclo do
Ensino Básico ou do Ensino Secundário. A primeira parte das notas cobre aspectos
básicos de combinatória enumerativa enquanto a segunda constitui uma introdução à
teoria de grafos. Tópicos mais espećıficos, como sejam a teoria das funções geradoras,
números de Catalan, Bell e Stirling, partições de um inteiro, emparelhamentos, redes
e fluxos, coloração (de vértices, arestas e de mapas em superf́ıcies), teoria de Ramsey,
etc. foram deixados como temas para os trabalhos dos alunos, a apresentar oralmente
e por escrito para avaliação.
A combinatória, em particular a teoria de grafos, é uma das áreas da matemática
cujo desenvolvimento foi, pelo menos parcialmente, motivado por problemas de natu-
reza recreativa. Com o decorrer do tempo, o número de aplicações desta teoria foi
crescendo e é actualmente uma das áreas da matemática com mais aplicações, que
incluem a programação e ciência de computdores, ciências sociais, biologia, qúımica,
desenho de redes e optimizaç ao industrial.
A combinatória ocupa-se da análise de estruturas discretas, como o estudo dos
posśıveis arranjos de objectos de um conjunto em determinados padrões. Frequente-
mente, estamos interessados em saber se determinada configuração de objectos e suas
relações é ou não posśıvel ou se podemos passar de um configuração a outra seguindo
3
CAPÍTULO 1. INTRODUÇÃO 4
determinadas regras. Um exemplo deste tipo de problema é o conhecido Jogo dos 15,
em que quinze peças numeradas de 1 a 15 deslizam horizontalmente e verticalmente
num tabuleiro 4!4 com uma casa vazia, como ilustra a figura abaixo.
O objectivo do jogo é passar desta configuração inicial para uma outra configuração
final dada, digamos por exemplo a seguinte:
Vejamos um outro exemplo simples. Temos um tabuleiro de xadrez de formato
8!8 que queremos cobrir completamente com 32 peças de dominó, cada peça cobrindo
exactamente dois quadrados adjacentes do tabuleiro sem que haja sobreposição de
peças. Uma tal cobertura é claramente posśıvel, portanto perguntamos: De quantas
maneiras distintas é posśıvel cobrir o tabulerio de xadrez desta forma? Para responder
a esta questão devemos primeiro estabelecer outra: O que é que consideramos formas
distintas de cobrir o tabulerio? Cada resposta distinta a esta última pergunta dá origem
a uma nova resposta à primeira pergunta. Podemos agora variar o problema criando
quadrados proibidos no tabuleiro, ou seja, quadrados que nõ podem ser cobertos por
nenhuma peça de dominó. Por exemplo, podemos tornar proibidos os quadrados de
dois cantos diametralmente opostos do tabuleiro, como na figura abaixo. Será que
ainda é posśıvel cobrir este tabuleiro?
Após algumas tentativas podemos começar a intuir que a reposta a esta última per-
gunta é negativa, mas será que podemos estar seguros desta resposta sem analizarmos
exaustivamente todas as possibilidades?
CAPÍTULO 1. INTRODUÇÃO 5
É de facto imposśıvel cobrir com peças de dominó o tabuleiro recortado acima,
e podemos prová-lo de uma forma muito simples e clara. Se, como é habitual, os
quadrados do tabuleiro original tiverem alternadamente as cores branco e preto, então
no tabuleiro recortado haverá 30 quadrados de uma das cores e 32 da outra, uma vez que
foram retirados ao tabuleiro original dois quadrados da mesma cor. Se observarmos
que cada peça de dominó cobre exactamente um quadrado de cada cor, concluimos
imediatamente que uma tal cobertura é imposśıvel pois para tal teriam de existir no
tabuleiro tantos quadrados de uma cor como da outra.
Outro problema envolvendo tabuleiros rectangulares com posições proibidas con-
siste em colocar num dos quadrados do tabuleiro dado um cavalo do jogo de xadrez.
O objectivo é que o cavalo percorra todos os quadrados não interditos do tabuleiro
exactamente uma vez, voltando possivelmente à posic cão inicial. Como no jogo de
xadrez, o cavalo só se pode movimentar de um quadrado a outro por um movimento
em formato de “L”, isto é, efectuando uma deslocação horizontal ou vertical de duas
posições seguida de uma deslocção de uma posição na direcção perpendicular. Este
problema pode ser estudado no contexto dos grafos hamiltonianos.
Caṕıtulo 2
Métodos elementares de contagem
2.1 As leis da soma e do produto
Entenda-se por um evento, algo que é pasśıvel de ocorrer. Por exemplo, escolher o
porta-voz de um grupo de pessoas, atribuir uma cor a uma face de um sólido, colocar
uma bola numa caixa, atribuir uma turma a um professor ou uma sala a uma turma.
Um evento pode ocorrer de uma ou mais formas distintas. Assim, num grupo de 20
pessoas, há 20 possibilidades para a escolha de um porta-voz se todas as pessoasdo
grupo forem eleǵıveis, etc.
Na presença de vários eventos, cada um podendo ocorrer de uma forma indepen-
dente dos restantes, usaremos os dois prinćıpios seguintes:
Prinćıpio da multiplicação. Se um evento pode ocorrer de m formas distin-
tas e outro, independente do primeiro, pode ocorrer de n formas distintas, então a
combinação dos dois eventos pode ocorrer de mn formas distintas.
Exemplo. Ao atirar ao ar uma moeda e lançar um dado, o número de resultados
distintos que é posśıvel obter é 2! 6 = 12, já que há dois resultados posśıveis ao atirar
a moeda ao ar e seis resultados posśıveis quando lançamos o dado.
Prinćıpio da adição. Se um evento pode ocorrer de m formas distintas e outro,
independente do primeiro, pode ocorrer de n formas distintas, então existem m + n
formas de um dos dois eventos ocorrer.
Exemplo. De entre as cinco letras romanas a, b, c, d, e, e as três letras gregas !, ",
#, há 5 + 3 formas de escolher uma letra e 5! 3 formas de escolher uma letra de cada
alfabeto.
Exemplo. Suponhamos que num determinado ano académico são oferecidas sete disci-
plinas de manhã e cinco disciplinas à tarde. Um estudante que se quer inscrever numa
6
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 7
disciplina de manhã e noutra de tarde tem 7 ! 5 = 35 escolhas posśıveis, ao passo
que um estudante que se tenha de inscrever em apenas uma disciplina à sua escolha,
independentemente de ser de manhã ou de tarde, tem 7 + 5 = 12 escolhas posśıveis.
Exemplo. Quantos inteiros entre 5000 e 10000 é que têm todos os seus algarismos (na
base 10) distintos?
Os inteiros pretendidos têm precisamente quatro algarismos. O algarismo dos mi-
lhares terá de ser 5, 6, 7, 8 ou 9. Escolhido este, há nove possibilidades para o algarismo
das centenas. De forma análoga, existem oito possibilidades para o algarismo das de-
zenas e sete para o das unidades. No total, há 5 ! 9 ! 8 ! 7 = 2520 números nas
condições pretendidas.
Note-se que a resolução deste problema se tornaria mais dif́ıcil de começássemos
por discutir um algarismo que não fosse o dos milhares.
Exemplo. Quantos pares distintos de inteiros a, b entre 1 e n é que existem com a " b?
Neste problema, os eventos “escolher a” e “escolher b” não são independentes,
portanto a resposta não é n2 nem n(n# 1).
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 8
2.2 Bijecções
Para cada inteiro positivo n, seja {1, 2, . . . , n} o conjunto dos inteiros entre 1 e n. Dado
um conjunto A, dizemos que A tem cardinalidade n e escrevemos |A| = n se existir
uma bijecção entre os conjuntos A e {1, 2, . . . , n}. Dizemos ainda que o conjunto A é
finito se |A| = n para algum n.
Os prinćıpios da adição e da multiplicação podem ser justificados à luz da seguinte
proposição:
Proposição 2.1. Sejam A e B conjuntos finitos. Então:
(a) |A $B| = |A| + |B|, se A %B = &;
(b) |A!B| = |A||B|.
Exemplo. Quando são lançados dois dados diferentes, de quantas formas pode ser
obtido um sete ou um oito?
A cada lançamento dos dados associamos um par ordenado (a, b), onde a é o resul-
tado do lançamento do primeiro dado e b o resultado do lançamento do segundo dado.
Sejam A e B os conjuntos dos pares ordenados que correspondem a um resultado de
sete e oito, respectivamente. Então:
A = {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)},
B = {(2, 6), (3, 5), (4, 4), (5, 3), (6, 2)}.
Como A % B = &, temos que |A $ B| = |A| + |B| = 6 + 5 = 11. Sendo assim, um
resultado de sete ou de oito pode ser obtido de 11 formas distintas.
Exemplo. Ao lançar uma moeda ao ar três vezes, de quantas formas se pode obter
uma, duas ou três caras?
Representemos um resultado de caras por C e um de coroas por M . Sejam A1, A2
e A3 os conjuntos formados pelos resultados “uma cara”, “duas caras” e “três caras”,
respectivamente. Temos:
A1 = {(C, M, M), (M, C, M), (M, M,C)},
A2 = {(C, C,M), (C, M, C), (M, C, C)},
A3 = {(C, C,C)}.
Como estes conjuntos são dois-a-dois disjuntos,
|A1 $ A2 $ A3| = |A1| + |A2| + |A3| = 3 + 3 + 1 = 7.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 9
Exemplo. Suponhamos que as matŕıculas dos véıculos num determinado páıs consis-
tem em sequências de duas letras seguidas de quatro algarismos, como acontece em
Portugal. Quantas placas de matŕıcula distintas é que podemos formar seguindo este
procedimento?
Seja A = {A, B, . . . , Z} o conjunto das letras do alfabeto (excluindo K, Y e W ) e
B = {0, . . . , 9} o conjunto dos algarismos posśıveis. O conjunto de todas as matŕıculas
posśıveis é A! A!B !B !B !B e
|A! A!B !B !B !B| = |A|2|B|4 = 232104 = 5290000.
Exemplo. Quantos pares distintos de inteiros a, b entre 1 e n é que existem com a " b?
Pretendemos calcular |A|, onde A = {(a, b) ' N2 | 1 " a, b " n e a " b}. Sejam
B = {(a, b) ' N2 | 1 " a, b " n + 1 e a < b} e C = {X ( {1, . . . , n + 1} | |X| = 2}.
Então (a, b)
f)* (a, b + 1) é uma bijecção de A em B e (x, y) g)* {x, y} é uma bijecção
de B em C. Logo, g + f é uma bijecção de A em C. Como veremos, |C| =
!
n+1
2
"
, logo
|A| = |C| = (n+1)n2 .
O seguinte resultado é por vezes útil em contagem:
Proposição 2.2. Sejam A e B conjuntos finitos.
(a) Se existir uma função injectiva A
f* B então |A| " |B|.
(b) Se existir uma função sobrejectiva A
f* B então |A| ,| B|.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 10
2.3 Convenções
De forma a evitar algumas ambiguidades que comummente ocorrem na formulação
de problemas de contagem, iremos aqui adaptar algumas convenções. O leitor deverá
no entanto conformar-se com a inevitabilidade da persistência de ambiguidades em
problemas de contagem. Evitá-lo implicaria frequentemente tornar o enunciado dos
problemas demasiado longo e complexo. Nestes casos, o leitor deverá indicar quais
foram as convenções que adoptou na resolução do problema e, se posśıvel, apresentar
soluções alternativas de forma a prever outras posśıveis interpretações.
Assumimos que é sempre posśıvel distinguir duas pessoas de um grupo. Por sua
vez, todas as laranjas são iguais, o mesmo acontecendo com maçãs, bolas amarelas, A’s,
moedas com o mesmo valor facial e dados, a menos que haja indicação em contrário.
Só consideramos a ordem das escolhas relevante se tal for explicitado no problema.
O alfabeto tem 23 letras, 5 das quais são vogais, sendo as restantes 18 consoantes. Uma
palavra é uma sequência (ordenada) de letras ou śımbolos. Um baralho de cartas tem
52 cartas, 13 de cada um dos 4 naipes, que são espadas, paus, copas e ouros. As caras
de espadas e de paus são pretas; as de copas e de ouros são vermelhas. Em cada naipe
há uma carta com cada um dos valores faciais 2, 3, . . . , 10, rainha, valete, rei e ás.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 11
2.4 Alguns exerćıcios de aquecimento
1. Em 8 minutos, responda às seguintes 10 questões de forma concisa mas completa.
Em caso de dúvida, deverá indicar quais foram os pressupostos assumidos.
(a) Quantas formas há de escolher uma pessoa de um grupo de 6 rapazes e 8
raparigas?
(b) Quantas formas há de escolher uma peça de fruta de 6 laranjas e 8 maçãs?
(c) Quantas formas há de escolher uma letra de 3 A’s, 5 B’s e 7 C’s?
(d) Quantas formas há de escolher duas letras de 3 B’s e 3 G’s?
(e) Quantas formas há de escolher duas pessoas de 3 rapazes e 3 raparigas?
(f) Quantas formas há de escolher 5 laranjas de um conjunto de 6 laranjas?
(g) Quantas formas há de escolher 5 raparigas de um conjunto de 6 raparigas?
(h) Quantas formas há de escolher 1 rapariga de um conjunto de 6 raparigas?
(i) Quantas formas há de escolher 5 peças de fruta de 7 laranjas e 8 maçãs?
(j) Quantas formas há de escolher algumas peças de fruta de 9 laranjas e 6
maçãs se pelo menos uma peça de fruta é escolhida?
2. Discuta as várias respostas posśıveis à questão: “Quantos resultados podem ser
obtidos ao lançar um par de dados?”
3. Um número de telefone é composto por sete d́ıgitos. Suponhamosque o primeiro
d́ıgito (da esquerda para a direita) é um algarismo entre 2 e 9, o segundo e o
terceiro são algarismos entre 1 e 9 e os restantes são algarismos entre 0 e 9.
Quantos números de telefone distintos podem ser formados nestas condições?
4. Uma empresa produz cadeados com combinação. Cada combinação consiste em
três números inteiros entre 0 e 99, mas nenhum número pode aparecer mais de
uma vez na combinação. Por exemplo, 23 # 2 # 3 é uma combinação posśıvel,
mas 23# 4# 23 não é. Quantas combinações distintas é posśıvel formar?
5. Uma companhia de computadores quer contratar um director e um subdirector
de entre um grupo de cinco candidatos já pré-seleccionados. De quantas formas
distintas o pode fazer? E se em vez de contratar um director e um sub-director
quiserem contratar dois sub-directores?
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 12
2.5 Um trilema: três visões de um problema
Problema. É Páscoa e a professora Celeste quer colorir com os seus alunos k ovos da
Páscoa, dispondo para tal de tintas de n cores diferentes. De quantas formas distintas
é que o podem fazer?
Nota. A resposta não é nk! Por exemplo, se n = k = 2, então as possibilidades são: os
dois ovos da cor 1, os dois ovos da cor 2 ou um ovo de cada cor. Neste caso a resposta
é 3 -= 22.
Seja xi = número de ovos a ser pintados da cor i. Então, queremos saber quantas
soluções tem a equação
x1 + x2 + · · · + xn = k,
com xi um inteiro não negativo. Denotamos este número por f(n, k).
1 o processo
Comecemos por usar um método heuŕıstico, estudando alguns casos particulares.
1. Se só há uma cor (i.e., n = 1) então só há uma forma de pintar os ovos. Logo,
f(1, k) = 1 .k , 1.
2. Se só há um ovo (i.e., k = 1) então há tantas formas de o pintar como o número
de cores. Logo,
f(n, 1) = n .n , 1.
3. Como já observámos, f(2, 2) = 3.
Em geral, não é dif́ıcil de calcular f(n, k) para valores pequenos de n e k. Será que
conseguimos encontrar uma fórmula que permita calcular f(n, k) a partir de valores
menores de n e k?
Exemplo. Seja
!
n
k
"
o número de formas de escolher k objectos de um conjunto de n
objectos distintos. Sabemos que
#
n
k
$
=
#
n# 1
k
$
+
#
n# 1
k # 1
$
,
e esta igualdade pode ser deduzida sem usar a fórmula expĺıcita para
!
n
k
"
, como vamos
agora recordar. Fixemos um dos n objectos, que designaremos por objecto especial.
Quando escolhemos k dos n objectos, podemos ou não escolher o objecto especial. Se
optarmos por não o escolher, temos de escolher k objectos de entre os n#1 restantes, o
que podemos fazer de
!
n!1
k
"
formas distintas. Caso contrário, se optarmos por escolher
o objecto especial, teremos ainda de escolher k # 1 objectos dos restantes n # 1, que
poderemos fazer de
!
n!1
k!1
"
formas distintas. Pelo prinćıpio da adição, temos
!
n!1
k
"
+
!
n!1
k!1
"
formas de escolher k objectos de um conjunto de n objectos distintos.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 13
Tentemos proceder com f(n, k) de forma análoga ao que fizémos no exemplo an-
terior. Fixemos então uma cor, que designaremos por cor especial. Quando pintamos
os k ovos, podemos usar ou não a cor especial. Existem f(n # 1, k) formas de pintar
os ovos sem usar a cor especial. Quantas formas existem de os pintar usando a cor
especial? Temos de pintar pelo menos um com a cor especial, e restam k# 1 ovos, que
podemos pintar com as n cores de f(n, k # 1) formas diferentes. Logo,
f(n, k) = f(n, k # 1) + f(n# 1, k).
Assim, por exemplo,
f(4, 3) = f(4, 2) + f(3, 3)
= f(4, 1) + f(3, 2) + f(2, 3) + f(3, 2)
= 2(f(2, 2) + f(3, 1)) + f(4, 1) + f(2, 2) + f(1, 3)
= 3f(2, 2) + 2f(3, 1) + f(4, 1) + f(1, 3)
= 3! 3 + 2! 3 + 4 + 1
= 20.
Em geral, a relação de recorrência f(n, k) = f(n, k # 1) + f(n # 1, k) permite-nos
calcular, recursivamente, todos os valores de f(n, k), conhecendo as condições iniciais
f(1, k) = 1 e f(n, 1) = n, para n, k , 1. No entanto, este processo pode ser bastante
moroso.
Um exemplo bem conhecido de uma relação de recorrência é a sucessão de Fibonacci,
definida por
an = an!1 + an!2, n , 2,
com condições iniciais a0 = a1 = 1. Desta relação de recorrência não é de todo óbvia
a expressão geral de an. De facto, para n , 0,
an =
$n+1 # $̄n+1/
5
onde $ = 1+
"
5
2 e $̄ =
1!
"
5
2 são as ráızes da equação x
2 # x # 1 = 0. $ é o número de
ouro.
Exerćıcio. Calcular f(n, 2).
2 o processo
Tomemos o produto dos seguintes n factores
(1 + x + x2 + · · · )(1 + x + x2 + · · · ) · · · (1 + x + x2 + · · · ) (2.1)
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 14
onde x é uma variável.
Qual é o coeficiente de 1 = x0 no produto (2.1)? É 1 pois a única forma de obter 1
no produto é escolher 1 em cada um dos factores. E o coeficiente de x? Para obter x
temos de escolher a parcela x num dos factores e a parcela 1 nos restantes n#1 factores.
Isto pode ser feito de 1 + 1 + · · · + 1 = n formas, logo ao multiplicar a expressão (2.1)
obtemos precisamente n parcelas da forma x. Ou seja, o coeficiente de x em (2.1) é n.
Para obter x2 em (2.1) temos duas possibilidades: escolher a parcela 1 em n # 1 dos
factores e a parcela x2 no factor restante, que pode ser feito de n formas distintas, ou
escolher a parcela x em dois dos factores e a parcela 1 nos restantes, que pode ser feito
de
!
n
2
"
formas distintas. Assim, o coeficiente de x2 em (2.1) é
n +
#
n
2
$
=
#
n
1
$
+
#
n
2
$
=
#
n + 1
2
$
.
Em geral, qual será o coeficiente de xk em (2.1)? Se escolhermos a parcela xa1
do primeiro factor, xa2 do segundo, . . . , xan do último factor, obtemos a parcela
xa1+···+an , logo o coeficiente de xk em (2.1) é o número de escolhas diferentes de intei-
ros a1, . . . , an , 0 que satisfazem a1 + · · · + an = k. Como vimos atrás, este valor é
precisamente f(n, k). Logo,
f(n, k) = coeficiente de xk em (2.1)
= coeficiente de xk em (1# x)!n,
já que
(1 + x + x2 + · · · )(1# x) = (1 + x + x2 + · · · )# (x + x2 + x3 + · · · ) = 1,
donde deduzimos que
1 + x + x2 + · · · = (1# x)!1.
Assim, obtivémos a seguinte fórmula:
(1# x)!n = f(n, 0) · 1 + f(n, 1)x + f(n, 2)x2 + · · · + f(n, k)xk + · · ·
=
%
k#0
f(n, k)xk.
No entanto, ainda não temos uma fórmula fechada para f(n, k).
3 o processo
O que distingue resultados diferentes é o número de ovos de cada cor, isto é, os va-
lores de x1, x2, . . . , xn. Imaginemos os ovos já pintados. Podemos alinhá-los colocando
primeiro os da cor 1, introduzir um separador, de seguida os de cor 2 e um separador,
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 15
etc., até chegar aos ovos de cor n. Podemos esquematizar o que fizémos numa figura
do tipo
0 · · · 0& '( )
x1
| 0 · · · 0& '( )
x2
| |&'()
x3=0
0 · · · | 0&'()
xn=1
onde “0” representa um ovo e “|” um separador. Usámos o śımbolo “0” k vezes e o
śımbolo “|” n # 1 vezes. Reciprocamente, a cada sequência deste género corresponde
uma única escolha para x1, x2, . . . , xn. Por exemplo, se n = 5 e k = 4, a sequência
0 | 00 | 0 | |
representa x1 = 1, x2 = 2, x3 = 1, x4 = 0, x5 = 0, ou seja, um ovo da cor 1, dois ovos
da cor 2, um ovo da cor 3 e nenhum ovo das cores 4 ou 5.
Reduzimos assim o nosso problema à enumeração de todas as sequências posśıveis
formadas pelos śımbolos “0” e “|”, de comprimento n + k# 1, usando o śımbolo “0” k
vezes e o śımbolo “|” n# 1 vezes. Quantas sequências há? Temos n + k # 1 posições,
e basta decidirmos em quais destas é que são inseridos os n # 1 śımbolos “|”. Logo,
f(n, k) =
!
n+k!1
n!1
"
=
!
n+k!1
k
"
.
Como já sab́ıamos, f(n, 1) =
!
n
1
"
= n, f(1, k) =
!
k
0
"
= 1, f(2, 2) =
!
3
2
"
= 3 e
f(n# 1, k) + f(n, k # 1) =
#
n + k # 2
k
$
+
#
n + k # 2
k # 1
$
=
#
n + k # 1
k
$
= f(n, k).
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 16
2.6 Exerćıcios
1. Resolva a relação de recorrência an = n2an!1, com a1 = 1.
2. Sabendo que an =
n!1
n an!1 e que a1 = 2, determine an.
3. Sabendo que an= an!1 + n, determine an se (a) a1 = 1, (b) a1 = 0.
4. São dadas n jaulas dispostas uma a seguir à outra e é necessário colocar nelas k
leões indistingúıveis de forma a que nenhuma jaula fique com mais de um leão e
que não haja jaulas consecutivas com leões. Seja g(n, k) o número de maneiras
de assim distribuir os leões pelas jaulas. Mostre que:
(a) g(2k # 1, k) = 1;
(b) g(n, k) = 0 se n < 2k # 1;
(c) g(n, 1) = n;
(d) g(n, k) = g(n # 2, k # 1) + g(n # 1, k) se k , 2 [Sugestão: considere as
possibilidades de a última jaula ter ou não um leão.];
(e) Deduza que: (i) g(6, 3) = 4; g(2k, k) = g(2k#2, k#1)+1; g(2k, k) = k+1.
5. Admita que t(n, n # 1) = 1 e que (n # k # 1)t(n, k) = k(n # 1)t(n, k + 1), para
k < n# 1. Deduza que
t(n, k) =
(n# 1)n!k!1(n# 2)!
(k # 1)!(n# k # 1)! .
6. Expanda (1# x)!3 em potências de x até ao termo em x5.
7. Seja h(n, k) o número de maneiras de colorir k objectos idênticos com n cores,
usando cada cor pelo menos uma vez. Conclua que:
(a) h(n, k) = 0 se n > k;
(b) h(n, k) é o coeficiente de xk em (x + x2 + x3 + · · · )n;
(c) h(n, k) é o coeficiente de xk!n em (1# x)!n;
(d) h(n, k) = f(n, k # n);
(e) h(n, k) =
!
k!1
n!1
"
se n " k;
(f) Calcule h(5, 10).
8. Expresse, em termos da função f(n, k) usada na secção 2.5:
(a) o número de sequências de 0’s e 1’s de comprimento 10 contendo exactamente
cinco 0’s;
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 17
(b) o número de soluções da equação x + y + z = 24: (i) nos números inteiros
não negativos; (ii) nos números inteiros positivos;
(c) o número de padrões distintos que é posśıvel obter ao lançar três dados
idênticos;
9. Mostre que o produto de r inteiros consecutivos é diviśıvel por r!.
10. De quantas formas distintas é que se podem pintar as faces de um cubo usando
cada uma de seis cores dispońıveis?
11. Sete amigos querem organizar sete jantares entre eles. A cada jantar vão três
pessoas de cada vez e, para evitar a monotonia, não se repetem pares de pessoas
em jantares diferentes. De quantas maneiras diferentes é que eles podem planear
os jantares?
12. Em 8 minutos, responda às seguintes 14 questões de forma concisa mas completa.
Em caso de dúvida, deverá indicar quais foram os pressupostos assumidos.
(a) De quantas maneiras é posśıvel escolher um livro de latim e um livro de grego
de um conjunto de 5 livros de latim distintos e 7 livros de grego distintos?
(b) De quantas maneiras é posśıvel formar uma palavra de 2 letras?
(c) De quantas maneiras é posśıvel formar uma palavra de 2 letras distintas?
(d) De quantas maneiras é posśıvel formar uma palavra de 2 letras consistindo
numa consoante seguida de uma vogal?
(e) De quantas maneiras é posśıvel escolher um rapaz e uma rapariga de um
grupo de 3 rapazes e 8 raparigas?
(f) De quantas maneiras diferentes é que duas pessoas se podem sentar numa
fila de 5 cadeiras livres?
(g) De quantas maneiras diferentes é que se podem escolher 2 cadeiras de 5
cadeiras dispostas em fila?
(h) De quantas maneiras é posśıvel formar uma palavra de 4 letras?
(i) De quantas maneiras é posśıvel escolher um elemento de uma matriz 5! 7?
(j) De quantas maneiras é posśıvel escolher um elemento de uma matriz m!n?
(k) Quantos resultados se podem obter atirando uma moeda ao ar e lançando
um dado?
(l) Quantos resultados se podem obter atirando uma moeda ao ar, lançando
um dado e escolhendo uma carta de um baralho?
(m) De quantas formas é que se podem ordenar os ás de um baralho de cartas?
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 18
(n) De quantas formas é que se podem ordenar as cartas de espadas de um
baralho de cartas?
13. Determine o número de soluções da inequação
x1 + x2 + x3 + x4 + x5 + x6 < 91
(a) nos números inteiros positivos.
[Sugestão: Considere a equação x1 + x2 + x3 + x4 + x5 + x6 + x7 = 91.]
(b) nos números inteiros não negativos.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 19
2.7 Permutações, arranjos, combinações
Temos n objectos dos quais queremos escolher k. De quantas formas distintas o pode-
mos fazer? Ao ńıvel mais simples, a resposta dependerá essencialmente de dois factores:
se a escolha é ordenada ou não e se são ou não permitidas repetições.
Começemos por ver de quantas formas diferentes podemos ordenar um conjunto
com n elementos. Para o primeiro elemento temos n possibilidades, restando n # 1
elementos no conjunto. Para o segundo elemento temos n # 1 possibilidades, e assim
sucessivamente. Ao fim de termos escolhido o (n # 1)-ésimo elemento, restará um
elemento, que é a única possibilidade para o último elemento da sequência. Logo, pelo
prinćıpio da multiplicação, existem
n(n# 1) · · · 2 · 1 = n!
formas distintas de ordenar os elementos de um conjunto com n elementos (distintos).
Uma ordenação diz-se uma permutação do conjunto. Nesta linguagem, existem n!
permutações de um conjunto com n elementos.
Exemplo. O jornal Público quer publicar nas suas próximas 18 edições de Domingo
um artigo sobre cada um dos clubes de futebol da 1 a divisão nacional. De quantas
formas diferentes o pode fazer? E se o 3 o artigo tiver de ser sobre o União de Leiria?
E se o Boavista e a Académica tiverem de aparecer em semanas consecutivas?
Exemplo. De quantas formas distintas se podem sentar n pessoas numa mesa redonda?
Exemplo. O professor da disciplina de Português pediu a cada um dos seus alunos
para expôr duas obras de literatura portuguesa de movimentos literários diferentes. Os
movimentos posśıveis são: romantismo, para o qual disponibilizou uma lista de sete
livros; realismo, tendo para este movimento disponibilizado uma lista de cinco livros;
modernismo, com uma lista de quatro livros posśıveis.
Quantas escolhas diferentes podem os alunos fazer? Qual é a probabilidade de uma
das obras ser do movimento realista?
Se tivermos um conjunto com n elementos e apenas quisermos escolher k deles de
forma ordenada temos, ainda pelo prinćıpio da multiplicação,
n(n# 1) · · · (n# (k # 1)) = n!
(n# k)!
formas de o fazer. Por exemplo, num inquérito sobre audiências os inquiridos têm de
seleccionar, por ordem de preferência, as quatro séries televisivas que mais vêem, de
entre uma lista de dez séries. Assim, há 10!6! respostas posśıveis.
Suponhamos que temos objectos que não são todos distintos. (Por exemplo, um
tubo cheio de smarties, em que apenas distinguimos smarties de cores diferentes.) Mais
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 20
precisamente, digamos que de n objectos de que dispomos, q1 são do tipo 1, q2 são do
tipo 2, . . . , e qk são do tipo k, onde, claro está, q1 + · · · + qk = n. De quantas formas
diferentes os podemos ordenar?
Começamos por imaginar que os objectos foram rotulados de forma a ser posśıvel
distinguir, temporariamente, objectos do mesmo tipo. Há neste caso n! formas de
os ordenar. Quando “apagamos” todos os rótulos aos objectos, verificamos que cada
sequência de objectos não rotulados dá origem a q1!! · · ·! qk! sequências de objectos
rotulados. Logo, há
n!
q1! · · · qk!
sequências distintas de q1 objectos de tipo 1, q2 objectos de tipo 2, etc. Este número
diz-se um coeficiente multinomial e denota-se por
#
n
q1, . . . , qk
$
.
Exemplo. Quantas “palavras” é posśıvel construir usando as letras de cada uma das
seguintes palavras?
(a) bola;
(b) bolo;
(c) matemática: (i) ignorando o acento; (ii) não ignorando o acento;
(d) combinatória: (idem).
Exemplo. Quantas sequências binárias de cinco algarismos é posśıvel escrever usando
o algarismo 0 no máximo quatro vezes e o algarismo 1 no máximo três vezes?
Suponhamos agora que não estamos limitados no número de objectos de cada tipo
a usar. Assim, queremos saber quantas sequências distintas de n objectos é posśıvel
construir, usando objectos de r tipos diferentes, com repetição ilimitada. Temos r pos-
sibilidades para o primeiro objecto, r para o segundo objecto, e assim sucessivamente,até escolhermos de que tipo é o n-ésimo objecto. Logo, o número de tais sequências é
rn.
Seja
!
n
k
"
o número de formas de escolher k objectos distintos de entre n objectos
distintos dispońıveis. Então, como não nos interessa a ordem por que foram escolhidos
esses k objectos, temos #
n
k
$
· k! = n!
(n# k)!
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 21
Isto porque cada escolha não ordenada de k objectos distintos de entre n dá origem a
k! escolhas ordenadas, e o número total de escolhas ordenadas é n!(n!k)! . Logo,
#
n
k
$
=
n!
k!(n# k)!
Outra forma de obter este resultado é a seguinte: A cada escolha não ordenada
de k objectos de entre n fazemos corresponder uma sequência ordenada de 0’s e 1’s,
em que ocorre um 1 na i-ésima posição se o i-ésimo objecto for escolhido e um 0 caso
contrário. Obtemos assim uma correspondência entre escolhas não ordenadas de k
objectos e sequências de 0’s e 1’s de comprimento n, com k 1’s e n# k 0’s. O número
de tais sequências já foi determinado e é o coeficiente multinomial
!
n
k,n!k
"
= n!k!(n!k)! .
Nota.
!
n
k
"
=
!
n
n!k
"
, uma vez que escolher k objectos de n é o mesmo que escolher os
n# k objectos que não são seleccionados.
Exemplo. De quantas formas é posśıvel escolher três números diferentes entre 1 e 300
de tal forma que a sua soma seja um múltiplo de 3?
Comecemos por dividir o conjunto dos números entre 1 e 300 em três subconjuntos
disjuntos: os que são diviśıveis por 3, os que dão resto 1 quando divididos por 3 e
os que dão resto 2 quando divididos por 3. Cada um destes subconjuntos tem cem
elementos. As únicas formas de escolher três números cuja soma é um múltiplo de 3 é
se os três números pertencerem ao mesmo subconjunto ou se cada um pertencer a um
subconjunto distinto. Logo, há
#
100
3
$
+
#
100
3
$
+
#
100
3
$
+ 1003
formas de escolher os números.
Resta-nos estudar o caso de escolhas não ordenadas com repetição ilimitada de k
objectos de entre objectos de n tipos distintos. Isto corresponde às soluções da equação
x1 + · · · + xn = k
no conjunto dos inteiros não negativos, onde xi indica o número de vezes que um
objecto de tipo i é escolhido. Como já vimos na secção 2.5, o número de tais soluções
é
f(n, k) =
#
n + k # 1
n# 1
$
=
#
n + k # 1
k
$
Exemplo. O João quer comprar sete berlindes. Na loja onde os vai comprar existem
berlindes de quatro tipos diferentes. Assim, o João tem
!
10
7
"
= 120 escolhas posśıveis.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 22
Temos portanto o seguinte quadro:
escolher k objectos número de escolhas número de escolhas
de n ordenadas (arranjos) não ordenadas (combinações)
sem repetição n!(n!k)!
!
n
k
"
com repetição nk
!
n+k!1
k
"
Quando temos objectos, em quantidades limitadas, de k tipos diferentes, o número
de escolhas posśıveis de objectos de entre eles é
(n1 + 1) · · · (nk + 1)
onde ni é o número de objectos dispońıveis de tipo i. Isto resulta do prinćıpio da
multiplicação, já que para objectos do tipo 1 temos n1 + 1 possibilidades de escolha,
entre 0 e n1 objectos, e analogamente para objectos de tipo 2, etc.
Exemplo. A Joana foi à padaria comprar pão. A padeira ainda tinha para vender 10
pães biju, 3 cacetes, 1 pão de forma e 2 pães da avó. Já não havia pão integral. Qual é
a probabilidade de a Joana sair da padaria com exactamente 2 pães biju e pelo menos
um pão da avó?
Exemplo. Quantos divisores tem o número 1400?
A factorização de 1400 em primos é 23527, logo os divisores de 1400 são os números
da forma 2a5b7c com 0 " a " 3, 0 " b " 2 e 0 " c " 1. Logo, 23527 tem (3 + 1)(2 +
1)(1 + 1) = 24 divisores.
Exemplo. Temos 10 bandeiras diferentes que devem ser hasteadas em 6 mastros, sendo
que nem todos os mastros têm de ser usados. De quantas formas é que podemos hastear
essas bandeiras?
Precisamos apenas de escolher um dos 6 mastros para a primeira bandeira, um dos
6 mastros para a segunda bandeira, etc., o que pode ser feito de 610 formas distintas.
No exemplo anterior, as escolhas de mastros para as bandeiras não reflectiu o facto
de que se 2 ou mais bandeiras forem hasteadas no mesmo mastro então terão de fi-
car a alturas diferentes no mastro. Tomando isto em consideração, cada atribuição
de bandeiras a mastros dá ainda origem a várias configurações diferentes. Quantas
configurações existem no total? Reformulemos o problema.
Temos n objectos distintos que queremos colocar em k caixas distintas, considerando
ordem dentro de cada caixa. Esta situação pode ser modelada por uma sequência
de comprimento n + k # 1 cujos elementos são os n objectos e k # 1 separadores
entre as caixas. Se os separadores fossem distintos, teŕıamos um total de (n + k # 1)!
sequências. Identificando, como deveŕıamos, os separadores, temos (n+k!1)!(k!1)! sequências
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 23
distintas, sendo esse o número de maneiras de colocar os n objectos distintos em k
caixas distintas, com ordem dentro de cada caixa.
Assim, para o exemplo anterior, assumindo que é necessário decidir a que altura
relativa nos mastros se dispõem as bandeiras, há 15!5! escolhas posśıveis.
Exemplo. Pretende-se enviar 5 letras diferentes (já escolhidas) através de um canal
de comunicação. Entre essas letras devem ser inseridos um total de 15 espaços em
branco, sendo cada par de letras separadas por um mı́nimo de 3 espaços em branco.
De quantas formas diferentes podem as letras e os espaços ser dispostos?
Se as letras não fossem distintas, existiriam
!
15!12+3
3
"
=
!
6
3
"
= 20 formas de o fazer.
Sendo as letras distintas, há um total de 5!20 formas de dispor as letras e os espaços.
Pensemos agora no seguinte problema: Dos subconjuntos de {1, . . . , n} com k ele-
mentos (0 " k " n) quantos é que não contêm números consecutivos?
Sem impor a restrição de não haver números consecutivos, a resposta seria
!
n
k
"
.
Uma das formas de chegar a esta conclusão é pensar num subconjunto de {1, . . . , n}
como uma sequência de 0’s e 1’s cujo i-ésimo algarismo é 1 se o inteiro i pertencer ao
subconjunto em questão e 0 caso contrário. Desta forma, estabelece-se uma bijecção
entre o conjunto dos subconjuntos de {1, . . . , n} com k elementos e o conjunto das
sequências binárias de comprimento n em que o śımbolo 1 ocorre k vezes e o śımbolo
0 ocorre n# k vezes. O número de tais sequências é
!
n
k
"
.
Ao restringir esta correspondência aos subconjuntos de k elementos sem inteiros
consecutivos obtemos exactamente as sequências binárias de comprimento n nas quais
1 ocorre k vezes, 0 ocorre n#k vezes e não há dois 1’s consecutivos. Quantas sequências
deste tipo haverá? Uma tal sequência é constrúıda inserindo os k śımbolos 1 nos espaços
entre os n# k śımbolos 0, incluindo os espaços que antecedem e sucedem a sequência
de 0’s:
0 0 · · · 0
Como há n#k+1 espaços e k śımbolos 1 a introduzir, no máximo um em cada espaço,
há
!
n!k+1
k
"
formas de o fazer. Temos então o seguinte resultado:
Lema 2.3 (Kaplansky). O número de subconjuntos de {1, . . . , n} com k elementos e
sem inteiros consecutivos é
!
n!k+1
k
"
.
Exemplo. Quantas palavras é que se podem formar usando todas as letras da palavra
INIMAGINÁVEIS sem que haja dois I’s adjacentes e ignorando o acento?
Escolhemos primeiro a localização dos quatro I’s de entre as 13 posições posśıveis.
Como não devem ocorrer I’s consecutivos, há
!
10
4
"
= 210 posições posśıveis. Resta
agora dispor as restantes letras, o que pode ser feito de 9!2!2! formas. Logo, há 210
9!
2!2!
palavras posśıveis, sem I’s adjacentes.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 24
Exemplo. Um relógio de cuco antigo está um pouco avariado e apenas assinala as
horas 4 vezes ao dia, nunca o fazendo, no entanto, em horas consecutivas. De quantas
formas distintas é que o relógio pode tocar (o relógio repeteo mesmo padrão todos os
dias)?
Este problema é análogo ao anterior no sentido em que estamos interessados em
saber quantos subconjuntos de {1, . . . , 24} com 4 elementos não consecutivos é que
existem. No entanto, há uma diferença significativa, uma vez que para este problema
devemos considerar os números 24 e 1 como sendo consecutivos, já que uma hora depois
da meia noite é uma hora da manhã. Somos portanto levados a considerar o seguinte
resultado, cuja prova é deixada como exerćıcio.
Lema 2.4 (Kaplansky). O número de subconjuntos de {1, . . . , n} com k elementos
e sem inteiros consecutivos, considerando n e 1 como sendo inteiros consecutivos, é
n
n!k
!
n!k
k
"
.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 25
2.8 Exerćıcios
1. Em 8 minutos, responda às seguintes 12 questões de forma concisa mas completa.
Em caso de dúvida, deverá indicar quais foram os pressupostos assumidos.
(a) De quantas formas é posśıvel ordenar as 6 letras da palavra ABCDEF?
(b) De quantas formas é posśıvel ordenar as 6 letras da palavra A1A2A3E4E5F?
(c) De quantas formas é posśıvel ordenar as 6 letras da palavra A1A2A3EEF?
(d) De quantas formas é posśıvel ordenar as 6 letras da palavra AAAE4E5F?
(e) De quantas formas é posśıvel ordenar as 6 letras da palavra AAAEEF?
(f) De quantas formas é posśıvel ordenar as letras da palavra BANANA?
(g) De quantas formas é posśıvel ordenar as letras da palavra AAABBCCCCD?
(h) De quantas formas é posśıvel ordenar as letras da palavra MISSISSIPPI?
(i) De quantas formas é que se podem ordenar 4 A’s, 3 G’s e as 6 letras S, T,
U, V, X, Z?
(j) De quantas formas é posśıvel dispor numa prateleira 4 exemplares de um
livro de álgebra, 3 exemplares de um livro de geometria e 6 romances de
cordel diferentes?
(k) De quantas formas é posśıvel dispor numa prateleira 4 livros de álgebra
distintos, 3 livros de geometria distintos e 6 livros de cálculo distintos de
forma a que livros sobre o mesmo assunto fiquem juntos?
(l) Quantas palavras de n letras é que têm r C’s e n# r R’s?
2. De quantas formas é que se podem ordenar as 23 letras do alfabeto de forma a
que: (i) as 5 vogais apareçam todas juntas; (ii) as letras A e B não apareçam
juntas.
3. Quantos colares distintos de n missangas é posśıvel formar usando uma missanga
de cada uma de n cores?
4. O António tem 75 livros mas apenas 20 destes cabem na sua prateleira. De
quantas forma é que pode encher a prateleira com os livros?
5. Quantos números entre 1000 e 3000 é que é posśıvel formar com os d́ıgitos
1, 2, 3, 4, 5: (i) com possibilidade de repetição de d́ıgitos; (ii) sem possibilidade
de repetição de d́ıgitos.
6. Em música serial dodecafónica, as 12 notas da escala cromática são dispostas em
linha e tocadas nessa ordem. Quantas linhas são posśıveis?
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 26
7. Uma comissão de 12 pessoas tem de designar de entre os seus membros um
Presidente, um Secretário e um Tesoureiro. De quantas formas é que isso pode
ser feito?
8. De quantas maneiras é posśıvel formar uma palavra de 5 letras (de entre as
23 letras do alfabeto): (i) com possibilidade de repetição de letras; (ii) sem
repetição de letras.
9. Mostre que:
(a)
!
n
k
"
=
!
k!1
k!1
"
+
!
k
k!1
"
+
!
k+1
k!1
"
+ · · · +
!
n!1
k!1
"
;
(b)
!
n+m+1
m
"
=
!
n
0
"
+
!
n+1
1
"
+
!
n+2
2
"
+ · · · +
!
n+m
m
"
.
10. Responda às seguintes questões de forma rápida, clara e concisa.
(a) De quantas formas é que 8 casais se podem sentar à volta de uma mesa
redonda de forma a que os membros de cada casal fiquem juntos?
(b) De quantas formas é que 4 Americanos, 7 Belgas e 10 Portugueses se podem
sentar à volta de uma mesa redonda?
(c) De quantas formas é que se podem ordenar 4 C’s e 8 R’s de forma a que
não haja C’s adjacentes?
(d) De quantas formas é posśıvel escolher 5 de 11 professores para uma comissão
de acompanhamento de alunos com necessidades especiais?
(e) Quantos full houses (três cartas do mesmo valor facial e um par do mesmo
valor facial, distinto do valor facial das três cartas anteriores) existem no
poker?
(f) De quantas formas é que o Armindo pode convidar alguns dos seus 10 amigos
para jantar, se convidar pelo menos 1 dos seus amigos?
(g) De quantas formas é que se podem arranjar as letras de DABBADABBA?
(h) Existem em casa do Duarte 5 livros de álgebra, 7 de geometria e 4 de cálculo.
Os livros são todos distintos. De quantas formas é posśıvel escolher destes
2 livros, não ambos da mesma área?
(i) Quantas das permutações das 23 letras do alfabeto é que não têm vogais
adjacentes?
(j) Quantas palavras de 10 letras é que não têm letras iguais adjacentes?
(k) Quantos conjuntos de 10 letras do alfabeto é que têm letras consecutivas?
(l) De quantas formas é que 5 homens e 7 mulheres se podem sentar em fila
sem que dois homens fiquem juntos?
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 27
(m) De quantas formas é que 5 homens e 7 mulheres se podem sentar à volta de
uma mesa redonda sem que dois homens fiquem juntos?
11. De quantas formas é que se podem hastear em 15 postes distintos, 5 bandeiras
vermelhas idênticas, 7 bandeiras azuis idênticas e 11 bandeiras distintas (entre si
e também distintas das anteriores)? Interessa a ordem das bandeiras nos postes
e nem todos os postes têm de ter bandeiras.
12. Determine o número de soluções, nos inteiros, da equação
x + y + z + w = 50
sujeitas às restrições adicionais x > 3, y > #4, z , 1 e w > #6.
13. De quantas formas diferentes é que 7 carros podem passar por 5 filas de portagem?
14. Prove o Lema 2.4.
15. Quantos triângulos é que se podem formar a partir de vértices não adjacentes de
um poĺıgono regular de n lados?
16. Quantas sequências é posśıvel formar usando a vezes o algarismo 0, b vezes o
algarismo 1 e c vezes o algarismo 2 de forma a que não haja nenhum par de 0’s
consecutivos?
17. Quantos subconjuntos de {1, . . . , n} com k elementos é que existem, de forma a
que entre dois quaisquer elementos do subconjunto haja pelo menos r elementos
que não lhe pertençam (isto é, tal que entre dois elementos haja uma diferença
de pelo menos r + 1 unidades)?
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 28
2.9 Os teoremas binomial e multinomial
Vejamos agora algumas aplicações simples do que fizémos até agora. Como alternativa
à mais habitual prova por indução do teorema binomial, apresentaremos de seguida
uma prova combinatória deste resultado, que se apresenta bastante mais simples e que
admite uma generalização natural – o teorema multinomial.
Teorema 2.5. Sejam n , 0 um inteiro e x, y números reais (ou complexos ou, mais
geralmente, elementos de um anel comutativo). Então:
(x + y)n =
n%
k=0
#
n
k
$
xkyn!k
Demonstração. Ao usar a distributividade do produto relativamente à adição na ex-
pressão
(x + y)(x + y) · · · (x + y)& '( )
n factores
(2.2)
e a comutatividade do produto, obtemos uma soma cujas parcelas são da forma xkyl.
Além disso, como há n factores em (2.2), k + l = n, isto é, l = n# k. Logo,
(x + y)n =
n%
k=0
c(k)xkyn!k,
onde c(k) é o número de vezes que é obtida a parcela xkyn!k ao efectuar a multiplicação
(2.2). Ora, para obter xkyn!k temos de escolher a parcela x em k dos factores de
(2.2). Isto pode ser feito precisamente de
!
n
k
"
formas, logo c(k) =
!
n
k
"
e (x + y)n =*n
k=0
!
n
k
"
xkyn!k.
Mais geralmente, podemos provar o teorema multinomial:
Teorema 2.6. Sejam n , 0 e k , 1 inteiros e x1, . . . , xk números reais (ou complexos
ou, mais geralmente, elementos de um anel comutativo). Então:
(x1 + · · · + xk)n =
%
a1, . . . , ak # 0
a1 + · · · + ak = n
#
n
a1, . . . , ak
$
xa11 · · ·x
ak
k
Demonstração. Ao expandir o produto
(x1 + · · · + xk) · · · (x1 + · · · + xk) (2.3)
as parcelas que obtemos são da forma xa11 · · ·x
ak
k , com a1, . . . , ak , 0 e a1+· · ·+ak = n,
o número de factores de (2.3). Resta-nos determinarde quantas formas diferentes pode
ser obtida a parcela xa11 · · ·x
ak
k . Para tal, temos de escolher os a1 factores em que
tomamos a parcela x1, os a2 factores em que tomamos a parcela x2, etc. Isto, como já
vimos, pode ser feito de n!a1!···ak! =
!
n
a1,...,ak
"
formas.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 29
Proposição 2.7. Sejam n um inteiro positivo e x um número real ou complexo tal que
|x| < 1. Então
(1# x)!n =
+$%
k=0
#
n + k # 1
k
$
xk
= 1 +
#
n
1
$
x +
#
n + 1
2
$
x2 +
#
n + 2
3
$
x3 + · · ·
Demonstração. Já vimos que o coeficiente de xk no produto dos n factores
(1 + x + x2 + · · · )(1 + x + x2 + · · · ) · · · (1 + x + x2 + · · · )
é
!
n+k!1
k
"
, o que prova o teorema, já que (1#x)!1 = 1+x+x2 + · · · , para |x| < 1.
Este resultado motiva a seguinte definição, que estende a definição dos coeficientes
binomiais
!
n
k
"
para valores arbitrários de n ' R e k ' N.
#
n
k
$
=
n(n# 1) · · · (n# k + 1)
k!
, se k , 1 e
#
n
0
$
= 1.
Temos assim, por exemplo,
#
1/2
3
$
=
1/2(1/2# 1)(1/2# 2)
3!
= 1/16,
#
4
6
$
=
4 · 3 · 2 · 1 · 0 · (#1)
6!
= 0,
#
#n
k
$
=
#n(#n# 1) · · · (#n# k + 1)
k!
= (#1)k n(n + 1) · · · (n + k # 1)
k!
= (#1)k
#
n + k # 1
k
$
. (2.4)
Teorema 2.8. Sejam n ' Z um inteiro qualquer e x um número real ou complexo tal
que |x| < 1. Então
(x + 1)n =
+$%
k=0
#
n
k
$
xk. (2.5)
Demonstração. Se n , 0 então
!
n
k
"
= 0 para k > n e assim a equação (2.5) resume-se ao
Teorema 2.5, com y = 1. Se n < 0 então podemos usar a Proposição 2.7, substituindo
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 30
x por #x e #n por n, juntamente com a igualdade (2.4), para concluir que de facto
(x + 1)n =
+$%
k=0
#
#n + k # 1
k
$
(#x)k
=
+$%
k=0
(#1)k
#
#n + k # 1
k
$
xk
=
+$%
k=0
#
n
k
$
xk.
Exemplo. Seja X um conjunto com n elementos. Então o número de subconjun-
tos de X com k elementos é
!
n
k
"
, por definição de
!
n
k
"
. Em particular, o número de
subconjuntos de X é
#
n
0
$
+
#
n
1
$
+ · · · +
#
n
n
$
=
n%
k=0
#
n
k
$
= (1 + 1)n = 2n.
Exemplo. Determinemos o número total de subconjuntos de {1, . . . , n}, onde n é um
inteiro positivo, que não contêm inteiros consecutivos (não consideramos os inteiros 1
e n como sendo consecutivos). Note-se que o conjunto vazio é um destes subconjuntos.
Então, pelo Lema 2.3, o número que procuramos é:
%
k#0
#
n# k + 1
k
$
.
Seja, para n , 0,
Fn =
%n/2&%
k=0
#
n# k
k
$
=
#
n
0
$
+
#
n# 1
1
$
+
#
n# 2
2
$
+ · · ·
A sucessão Fn consiste nas somas dos elementos das diagonais do triângulo de Pascal.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 31
Note-se que F0 =
!
0
0
"
= 1 =
!
1
0
"
= F1 e que
Fn + Fn+1 =
%
k#0
#
n# k
k
$
+
%
l#0
#
n + 1# l
l
$
=
%
k#0
+#
n# k
k
$
+
#
n# k
k + 1
$,
+
#
n + 1
0
$
=
%
k#0
#
n + 2# (k + 1)
k + 1
$
+ 1
=
%
k#0
#
n + 2# k
k
$
= Fn+2
Logo, (Fn)n#0 é a sucessão de Fibonacci.
Assim, o número total de subconjuntos de {1, . . . , n} que não contêm inteiros con-
secutivos é Fn+1, o (n + 1)-ésimo número de Fibonacci.
Exemplo. Considere-se a expansão binomial de (10 + 1)n:
11n =
#
n
0
$
10n +
#
n
1
$
10n!1 + · · · +
#
n
n# 1
$
10 +
#
n
n
$
.
Assim, as linhas do triângulo de Pascal permitem calcular a representação decimal das
potências de 11. Por exemplo, como a 6 a linha do triângulo de Pascal é
1 5 10 10 5 1
podemos concluir que 115 = 161051.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 32
2.10 Exerćıcios
1. Usando a identidade
(1 + x)2n = (1 + x)n(1 + x)n
e considerando em ambos os membros o coeficiente de xn, mostre que
#
2n
n
$
=
#
n
0
$2
+
#
n
1
$2
+
#
n
2
$2
+ · · · +
#
n
n
$2
.
Verifique esta igualdade para n = 5.
2. Apresente uma prova combinatória da identidade
n%
k=0
#
a
k
$#
b
n# k
$
=
#
a + b
n
$
.
Observe que se a = b = n obtemos a identidade do exerćıcio 1.
3. Mostre que
!
n+1
3
"
#
!
n!1
3
"
= (n# 1)2.
4. Mostre que, em cada uma das linhas do triângulo de Pascal, o número maior é o
(resp. são os) do meio, isto é, mostre que
!
n
r
"
>
!
n
r!1
"
se r " 12(n + 1).
5. Mostre que, para n > 2 e 1 < k < n# 1, se tem sempre
!
k
2
"
+
!
n!k
2
"
<
!
n!1
2
"
.
6. Mostre que
!
n
r
"2
>
!
n
r!1
"!
n
r+1
"
, para n > r.
7. Mostre que:
(a)
!
n
0
"
#
!
n
1
"
+
!
n
2
"
# · · · + (#1)n
!
n
n
"
= 0;
(b)
!
n
0
"
+
!
n
2
"
+
!
n
4
"
+ · · · =
!
n
1
"
+
!
n
3
"
+
!
n
5
"
+ · · · = 2n!1.
8. Calcule
n%
k=1
k
#
n
k
$
,
derivando ambos os membros da expansão binomial de (1 + x)n e fazendo a
substituição x = 1.
9. Calcule, de forma análoga ao que é sugerido no exerćıcio 8, as seguintes somas:
(a)
*n
k=0(#1)k!1k
!
n
k
"
;
(b)
*n
k=0
1
k+1
!
n
k
"
.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 33
10. Dados 0 " s " k " r " n, mostre que
#
n
r
$#
r
k
$#
k
s
$
=
#
n
s
$#
n# s
k # s
$#
n# k
r # k
$
.
11. Dado n , 3, calcule o valor de
1 · 2 · 3 + 2 · 3 · 4 + 3 · 4 · 5 + · · · + (n# 2) · (n# 1) · n.
12. Considere a seguinte rede de estradas:
No Ponto inicial O encontram-se 2a soldados. Metade destes segue na direcção SO
e a outra metade na direcção SE. Chegando a uma nova intersecção, cada grupo
de soldados divide-se novamente em dois, metade seguindo na direcção SO e a
outra metade na direcção SE. Quantos soldados chegam ao k-ésimo cruzamento
da linha n? [Sugestão: Considere a posição inicial de O como sendo o cruzamento
0 da linha 0.]
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 34
2.11 O prinćıpio do pombal
Temos N objectos que queremos distribuir de alguma forma por k caixas, podendo
eventualmente deixar algumas caixas vazias ou colocar todos os objectos na mesma
caixa. Se N > k então, independentemente da forma como o fizermos, alguma caixa
terá pelo menos dois objectos. Mais geralmente, se N > km para algum inteiro não
negativo m, então alguma das caixas terá pelo menos m + 1 objectos. Se assim não
fosse, então cada caixa conteria no máximo m objectos e o número total de objectos
não excederia mk, contrariando a hipótese sobre N .
O prinćıpio ilustrado acima chama-se usualmente prinćıpio do pombal, ou prinćıpio
das caixas de Dirichlet, por poder ser formulado em termos de pombas (respecti-
vamente, objectos) e pombais (respectivamente, caixas). Apesar de ser extrema-
mente simples, tem inúmeras aplicações nada óbvias, como iremos ver de seguida.
Começamos, no entanto, com algumas aplicações imediatas.
Exemplo. Num grupo de 13 pessoas há pelo menos duas pessoas com o mesmo signo
astrológico.
Exemplo. Numa festa com 6 pessoas, existe necessariamente um grupo de 3 pessoas
que se conhecem mutuamente ou um grupo de 3 pessoas que se desconhecem mutua-
mente (estamos a assumir que a relação de conhecer é simétrica).
Seja A uma das pessoa da festa. Dividimos as restantes 5 pessoas em dois grupos: o
grupo das que A conhece e o grupo das que A não conhece. Pelo prinćıpio do pombal,
algum destes grupos tem pelo menos 3 pessoas. Suponhamos, por exemplo, que o grupo
das pessoas que A não conhece tem pelo menos 3 pessoas, digamos B, C e D. Se B,
C e D se conhecem mutuamente, então já temos um trio que se conhece mutuamente.
Caso contrário, há pelo menos um par de entre B, C e D que não se conhece, digamos
B e C. Então A, B e C é um trio de desconhecidos. Fica assim provada a existência
de um trio de conhecidos ou de um trio de desconhecidos mútuos em qualquer grupo
de 6 pessoas.
Exemplo. Dados 5 pontos P1, . . . , P5 no interior de um quadrado de lado 1, algum
par deles está a uma distância inferior ou igual a
/
2/2.
Se decompusermos o quadrado em 4 quadrados de lado 1/2, pelo menos dois dos
pontos dados estarão no mesmo quadrado de lado 1/2. Como o diâmetro de qualquer
um destes quadrados é
/
2/2, dois pontos no mesmo quadrado pequeno distam no
máximo
/
2/2 um do outro.
Exemplo. Um jogador de xadrez quer treinar-separa um campeonato fazendo jogos
de prática nos próximos 77 dias. Ele quer jogar pelo menos um jogo por dia, mas não
mais de 132 jogos no total dos 77 dias. Vamos ver que, independentemente do seu
plano de treinos, haverá um peŕıodo de dias consecutivos em que jogará precisamente
21 jogos.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 35
Seja ai o número de jogos que ele faz desde o primeiro dia até ao final do dia i.
Então a sucessão a1, a2, . . . , a77 é estritamente crescente, a1 , 1 e a77 " 132. A sucessão
a1 + 21, a2 + 21, . . . , a77 + 21 é ainda estritamente crescente e a77 + 21 " 153. Ora,
os 77 ! 2 = 154 números a1, a2, . . . , a77, a1 + 21, a2 + 21, . . . , a77 + 21 não podem ser
todos distintos, já que estão todos compreendidos entre 1 e 153. Logo, há pelo menos
dois iguais. Pela monotonia das sucessões (ai)i e (ai + 21)i, os números iguais têm de
pertencer a sucessões distintas. Logo ai = aj + 21 para alguns 1 " i, j " 77. Isto
significa que do dia j + 1 ao dia i o jogador joga exactamente 21 partidas de xadrez.
Exemplo. Seja a1, . . . , an uma sequência de n números reais distintos e suponhamos
que n > pq, para alguns inteiros positivos p e q. Vamos ver que: ou existe uma
subsequência crescente desta com pelo menos p+1 termos, ou existe uma subsequência
decrescente desta com pelo menos q + 1 termos.
Suponhamos que não há nenhuma subsequência crescente com p + 1 termos. Para
cada i, seja xi o número máximo de termos numa subsucessão crescente da sucessão
dada começando em ai. Por hipótese, 1 " xi " p para todo o 1 " i " n. Logo, como
n > pq, há pelo menos q + 1 termos da sucessão com o mesmo valor de xj. Estes q + 1
termos formam necessariamente uma subsucessão decrescente de a1, . . . , an. De facto,
se i < j e xi = xj então não pode acontecer ai < aj, pois tal implicaria a contradição
xi , xj + 1.
Exemplo. Dois ćırculos concêntricos, um maior do que o outro, são divididos em 200
secções iguais. Das secções do disco exterior, 100 são coloridas de vermelho e as 100
restantes de azul. As secções do disco interior são pintadas arbitrariamente de vermelho
e azul. Será que é sempre posśıvel rodar o ćırculo interior de forma a que as cores dos
dois ćırculos coincidam em pelo menos 100 das secções? A figura abaixo ilustra a
situação descrita para 10 secções.
A resposta é afirmativa e passamos a prová-lo usando o prinćıpio do pombal. Fixe-
se o disco exterior e comece-se a rodar o disco interior pelas 200 posições posśıveis.
Para cada uma das posições registe-se o número de secções coincidentes. Se somarmos
todos estes números ao percorrer as 200 posições, obtemos o número 20000, pois cada
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 36
secção interna coincide com exactamente 100 das secções externas, ao longo das várias
posições que vai tomando. Assim, nalguma posição tem de haver pelo menos 100
secções coincidentes.
Exemplo. Dados n + 1 inteiros positivos entre 1 e 2n, há algum deles que é múltiplo
de outro.
Denotamos os n + 1 inteiros dados por x1, . . . , xn+1 e escrevemos, para cada i,
xi = 2!iyi, com !i , 0 e yi ı́mpar. Como os yi são n + 1 inteiros ı́mpares entre 1 e
2n, não podem ser todos diferentes. Logo existem ı́ndices i -= j tais que yi = yj. Se
!i " !j então xj é múltiplo de xi. Caso contrário, xi é múltiplo de xj.
Exemplo. Seja S um subconjunto de {1, 2, . . . , 99} com 10 elementos. Mostrar que
existem subconjuntos não vazios e disjuntos de S tais que a soma dos seus elementos
é igual.
O conjunto S tem 210#1 = 1023 subconjuntos não vazios. A soma dos elementos de
qualquer um desses subconjuntos é majorada por 90+91+ · · ·+99 < 10!100 = 1000.
Logo, pelo prinćıpio do pombal, existem dois subconjuntos não vazios e distintos de S
cujas somas dos seus elementos coincidem, digamos X e Y . Estes conjuntos podem,
no entanto, não ser disjuntos, mas
A = X \ (X % Y ) e B = Y \ (X % Y )
são disjuntos e a soma dos seus elementos é igual, já que retirámos a X e a Y os mesmos
elementos. Além disso, se um destes conjuntos fosse vazio então X 0 Y ou Y 0 X.
Como
*
x'X x =
*
y'Y y e estes inteiros são não nulos, tal implicaria que X = Y , o
que é absurdo. Logo A e B têm a propriedade pretendida.
CAPÍTULO 2. MÉTODOS ELEMENTARES DE CONTAGEM 37
2.12 Exerćıcios
1. Numa gaveta há 10 meias brancas idênticas e 10 meias pretas também idênticas.
Sem olhar para as meias, quantas meias é necessário retirar da gaveta para ga-
rantir que se consegue um par de meias da mesma cor?
2. Quantas cartas é necessário retirar de um baralho de cartas para garantir que se
retiram pelo menos duas cartas do mesmo naipe?
3. Quantas pessoas é necessário haver numa sala para garantir que pelo menos 3
delas têm o mesmo dia de aniversário?
4. Quantas bolas é necessário retirar de um saco que contém 12 bolas vermelhas,
20 bolas brancas, 7 bolas azuis e 8 bolas verdes para garantir que se tiram pelo
menos 10 bolas da mesma cor?
5. Quantas pessoas devem ser escolhidas de entre n casais de forma a garantir que
algum casal é escolhido?
6. Mostre que numa sala com 20 pessoas há pelo menos 2 pessoas com o mesmo
número de amigos na sala.
7. Considere todos os pontos do plano cujas coordenadas são inteiros. Mostre que
dados quaisquer 5 desses pontos, pelo menos 1 dos 10 segmentos que os unem
contém ainda algum ponto de coordenadas inteiras.
[Sugest~ao: Considere os pontos médios dos segmentos.]
8. Sejam x1, . . . , xn inteiros arbitrários. Mostre que existem i < j tais que xi +
xi+1 + · · · + xj!1 é múltiplo de n.
9. Usando o prinćıpio do pombal, mostre que a expansão decimal de um número
racional é finita ou periódica.
10. Mostre que para qualquer inteiro N , existe um múltiplo de N cuja representação
decimal contém apenas os d́ıgitos 0 e 7. Por exemplo, se N = 3 então 259! 3 =
777; se N = 4 então 1925! 4 = 7700.
[Sugest~ao: Considerar as classes residuais módulo N dos seguintes inteiros:
7, 77, . . . , 77 · · · 7& '( )
N algarismos
.]
11. Considere uma sequência de N inteiros positivos contendo precisamente n inteiros
distintos. Mostre que se N , 2n então existe um bloco de termos consecutivos
da sequência cujo produto é um quadrado perfeito.