aula_5_edmilson_papmem_janeiro_2025

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Contagem: Bijeções, Paradigmas e Estratégias 
Edmilson Motta 
 
Vamos começar com o seguinte problema: 
De quantas maneiras é possível escolher seis números inteiros positivos 𝑎1, 𝑎2, 𝑎3, 𝑎4, 𝑎5 e 𝑎6 de 
tal modo que 
1 ≤ 𝑎1
𝑥5, 𝑥6} do conjunto {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, o que já sabemos 
facilmente como calcular. 
Portanto, o número de inteiros positivos 𝑎1, 𝑎2, 𝑎3, 𝑎4, 𝑎5 e 𝑎6 que satisfazem o problema 
original é 
(
15
6
) =
15!
6! 9!
=
15 ∙ 14 ∙ 13 ∙ 12 ∙ 11 ∙ 10
6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1
= 5005 
Apenas conferindo com o auxílio de um computador para contar todas as maneiras: 
 
e realmente obtemos o mesmo resultado (ainda bem). 
 
Paradigmas da Contagem 
Como já vimos nos exercícios anteriores, utilizamos a bijeção para transformar problemas 
originalmente difíceis de se ter uma solução direta em problemas cuja solução é conhecida. 
As ideias mais comuns em problemas de contagem aprendidas na escola são permutação, 
arranjo, combinação e anagramas e usualmente os usos mais intuitivos são os seguintes: 
 Permutação: Maneiras de reordenar uma sequência com elementos diferentes; 
 Arranjo: Escolher uma certa quantidade de elementos de um conjunto, em que a ordem 
da escolha importa; 
 Combinação: Escolher uma certa quantidade de elementos de um conjunto, em que a 
ordem da escolha não importa 
 
 
 Anagramas / permutação com repetição: Para o caso em que a palavra não tem 
nenhuma letra repetida, a ideia é equivalente à permutação; já para o caso em que a 
palavra tem letras repetidas, deve-se considerar primeiramente que a palavra não tem 
repetição, e depois dividir o resultado pela quantidade que foi contada a mais, gerada 
pelas letras repetidas. 
Essas ideias, embora úteis em vários problemas, podem atrapalhar na hora de resolver 
exercícios mais complexos por evidenciarem um caso específico de sua utilidade. Para isso, os 
paradigmas da contagem, que serão explicados abaixo visam dar um outro ponto de vista para 
cada uma dessas ideias, baseando-se na teoria dos conjuntos. 
 
 Permutação ↔ funções bijetoras 
Um clássico exemplo de permutação é encontrado no seguinte problema: 
Cinco pessoas: 𝐴, 𝐵, 𝐶, 𝐷, 𝐸 vão fazer uma fila. De quantas maneiras diferentes essa fila pode ser 
feita? 
Muitos já devem ter se deparado com esse tipo de exercício e rapidamente classificado esse 
exercício como sendo de permutação, cuja resposta é 5! = 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 120 maneiras. 
Entretanto, vamos ver com mais detalhes o que estamos fazendo. 
Vamos ordenar as pessoas da seguinte forma: cada uma delas receberá um número de 1 a 5 
representando o seu número na fila. Cada uma delas receberá exatamente um número e esses 
números não podem se repetir. Podemos definir essa ordenação (distribuição dos números) 
através de uma função 𝑓 que mostre para cada pessoa em qual posição ela deva ir. Por exemplo, 
abaixo temos dois exemplos de funções 𝑓 diferentes 
 
Na função da esquerda, por exemplo, temos 𝑓(1) = 𝐶, indicando que quem estará na primeira 
posição será a pessoa 𝐶. Já na função da direita, 𝑓(2) = 𝐵 indicando que quem estará na 
segunda posição será a pessoa 𝐵. 
Observe que essa função nunca poderá levar duas pessoas diferentes em um mesmo lugar e que 
nenhuma vaga estará vazia após a reordenação. Em outras palavras, há uma bijeção entre o 
domínio (conjunto das posições {1, 2, 3, 4, 5}) e o contradomínio (o conjunto das pessoas 
{𝐴, 𝐵, 𝐶, 𝐷, 𝐸}), e essa relação de bijeção é mostrada pela função 𝑓. E, por causa dessas 
propriedades, temos que a função 𝑓 é bijetora. 
Portanto, o número de funções bijetoras diferentes que existe entre dois conjuntos com a 
mesma quantidade de elementos é igual ao número de maneiras em que podemos formar essa 
fila. 
 
 
E sabemos que o número 𝑃𝑛 de funções bijetoras diferentes que existem entre dois conjuntos 
de 𝑛 elementos é dado por 
𝑃𝑛 = 𝑛! = 𝑛 ∙ (𝑛 − 1) ∙ (𝑛 − 2)… ∙ 3 ∙ 2 ∙ 1 
Em outras palavras, se conseguirmos fazer uma bijeção utilizando uma função bijetora, 
obteremos que o número de maneiras de fazer realizar tal coisa é 𝑛!. 
 
 Arranjo ↔ funções injetoras 
Vamos começar com outro exemplo que demonstra a utilização do arranjo: 
Oito pessoas estão participando de uma competição de xadrez. De quantas formas o pódio, que 
consiste de uma medalha de ouro, uma de prata e uma de bronze, pode ser ocupado pelos 
participantes (admita que não há empates)? 
Esse também é um exercício frequente quando se trata de arranjo. Muitos já devem saber como 
responder esse exercício, já que é um arranjo de 8 elementos tomados 3 a 3, cuja fórmula é 
𝐴8,3 =
8!
(8−3)!
= 8 ∙ 7 ∙ 6 = 336 maneiras. Agora, vamos analisar isso com mais detalhes. 
De um modo similar ao exercício anterior, queremos selecionar os ganhadores das medalhas de 
ouro (1º lugar), prata (2º lugar) e bronze (3º lugar), e podemos fazê-lo entregando para um dos 
participantes o número 1, para outro participante o 2 e para um terceiro participante o 3. Aqui, 
é importante que ninguém receba mais de um número, podendo haver participantes que não 
recebam nenhum número (não ficaram no pódio) e, novamente, podemos representar isso 
através de uma função 𝑓. Abaixo, temos dois exemplos de funções 𝑓 diferentes. 
 
Na função da esquerda, por exemplo, temos 𝑓(1) = 𝐹 indicando que o participante 𝐹 recebeu 
a medalha de ouro (1º lugar), enquanto o participante 𝐵 não ficou no pódio. Já na função da 
direita, temos 𝑓(2) = 𝐴 indicando que o participante 𝐴 ganhou medalha de prata. 
Observe que essa função também não poderá dar uma mesma premiação para pessoas 
diferentes nem fazer uma mesma pessoa ganhar dois prêmios ou mais, indicando que essa é 
uma função injetora. Perceba também que uma maneira de entregar as medalhas representa 
unicamente uma dessas funções, e cada uma dessas funções representa unicamente um jeito 
de entregar as medalhas. Portanto, há uma bijeção entre o número de funções injetoras cujo 
domínio tem três elementos ({1, 2, 3}) e o contradomínio possui 8 elementos 
({𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻}). 
Por causa disso, podemos afirmar que o número de funções injetoras cujo domínio tem 𝑚 
elementos e o contradomínio tem 𝑛 ≥ 𝑚 elementos (ambos finitos) é igual ao número de 
 
 
maneiras de realizarmos um arranjo em um conjunto de 𝑛 elementos tomados 𝑚 a 𝑚, e essa 
quantidade é expressa por 
𝐴𝑛,𝑚 =
𝑛!
(𝑛 − 𝑚)!
= 𝑛 ∙ (𝑛 − 1) ∙ (𝑛 − 2)… ∙ (𝑛 − 𝑚 + 1) 
Em outras palavras, se conseguirmos fazer uma bijeção utilizando uma função injetora, 
obteremos que o número de maneiras de fazer tal coisa é 
𝑛!
(𝑛−𝑚)!
. 
 
 Combinação ↔ número de subconjuntos 
Já vimos anteriormente que contar a quantidade do número de subconjuntos com 𝑚 elementos 
a partir de um conjunto com 𝑛 ≥ 𝑚 elementos é dado pela combinação (𝑛
𝑚
), mas vamos analisar 
essa relação mais a fundo. Veja o seguinte problema: 
Oito pessoas estão participando de um sorteio, das quais duas pessoas serão selecionadas para 
ganhar dois prêmios idênticos. De quantas maneiras essas duas pessoas podem ser 
selecionadas? 
Esse é um exercício típico de combinação, cuja fórmula para resolvê-lo é (8
2
) =
8!
2!(8−2)!
=
8∙7
2
=
28 maneiras. 
Há uma bijeção entre o número de pessoas diferentes que podem ser selecionadas pelo sorteio 
e o número de subconjuntos de dois elementos que podem ser formados a partir de um 
conjunto com oito elementos distintos a partir da própria definição de como um conjunto é 
feito: 
Um conjunto com elementos distintos, assim como a ideia de combinação, não considera a 
ordem da escolha dos elementos. Portanto, cada uma das escolhas possíveis pode ser 
representada por um conjunto contido no conjunto original – e isso é por definição um 
subconjunto. 
 
Obs: Outra bijeção bem conhecida é associar a combinação (𝑛−1
𝑘−1
) ao número de soluções da 
equação 𝑥1 + 𝑥2 +⋯+ 𝑥𝑘 = 𝑛, com incógnitas 𝑥1, 𝑥2, … , 𝑥𝑘 e parâmetros 𝑘, 𝑛, todos inteiros 
positivos. 
 
 Anagramas ↔ permutação de multiset 
O caso de anagramas sem repetição pode claramente ser coberto a partir da permutação 
simples. Entretanto, a permutação por si só não
consegue cobrir os casos em que há letras 
repetidas, e para isso precisamos utilizar multiset. 
Antes de explicar essa relação, devemos explicar primeiramente o que é multiset. 
 
 
Até essa parte do material, foi usada várias vezes a expressão “conjunto com elementos 
distintos”. Entretanto, isso é uma redundância, já que um conjunto não considera a quantidade 
de cada um de seus elementos, mas sim se o elemento pertence ao conjunto ao não. Em outras 
palavras, os conjuntos {1, 2} e {1, 1, 2} são equivalentes e ambos possuem dois elementos: o 1 
e o 2. O multiset (ou multiconjunto) se comporta exatamente igual a um conjunto, mas dessa 
vez consideramos multiplicidades. A notação de um multiset será apresentada pelo exemplo 
abaixo: 
𝑀 = {1 ∙ 𝐴, 4 ∙ 𝐵, 2 ∙ 𝐷} é um multiset que contém um elemento 𝐴, quatro elementos 𝐵 e dois 
elementos 𝐷. 
Essa definição de multiset é utilizada para o cálculo de anagramas com letras repetidas, visto 
que agora temos como expressar repetições. 
E, também pela definição de anagramas, fica claro que permutação de multiset e anagramas 
com letras repetidas são análogos. Vamos mostrar isso no exemplo a seguir: 
Quantos são os anagramas da palavra BANANA? 
Pela fórmula de anagramas com repetição, há 
6!
3!∙2!
=
6∙5∙4
2
= 60 anagramas 
Vemos que é análogo a ver as reordenações que podem ocorrer a partir do seguinte multiset: 
𝑀 = {3 ⋅ 𝐴, 1 ⋅ 𝐵, 2 ⋅ 𝑁} 
De modo geral, se há uma palavra que pode ser representada pelo multiset 
𝑀 = {𝑚1 ⋅ 𝑥1,𝑚2 ⋅ 𝑥2,𝑚3,⋅ 𝑥3, … ,𝑚𝑛 ⋅ 𝑥𝑛} 
O número de anagramas que podem ser formados a partir desse multiset é 
𝑃𝑚1+𝑚2+⋯+𝑚𝑛
𝑚1,𝑚2,…,𝑚𝑛 =
(𝑚1 +𝑚2 +𝑚3 +⋯+𝑚𝑛)!
𝑚1! ⋅ 𝑚2! ⋅ 𝑚3! ⋅ … ⋅ 𝑚𝑛!
 
Obs: também é possível construir uma função sobrejetora que siga algumas condições para 
representar permutações de multiset. São elas: 
 O domínio dessa função 𝑓 será o conjunto {1, 2, 3, … , 𝑛}, em que 𝑛 é a soma de todas 
as multiplicidades do multiset (pode ser entendido como a quantidade de elementos 
que há no multiset) 
 O contradomínio dessa função 𝑓 será o conjunto formado pelos elementos do multiset 
(é considerado que nenhum elemento do multiset tenha multiplicaidade zero). 
 A quantidade de valores do domínio que são levados ao elemento 𝑎 no contradomínio 
é igual à multiplicidade de 𝑎 no multiset. 
Se quisermos criar a função 𝑓 para os anagramas da palavra BANANA, o domínio seria 
{1, 2, 3, 4, 5, 6}, em que cada número representaria a posição da letra no anagrama. O 
contradomínio seria {𝐴, 𝐵. 𝑁} e, por exemplo, temos que exatamente três elementos do 
domínio terão que ser direcionados para o elemento 𝐴 no contradomínio, pois há três 𝐴’s na 
palavra BANANA. 
 
 
Alguns exemplos de funções sobrejetoras 𝑓 que satisfazem essas condições e representam 
alguns anagramas da palavra BANANA estão mostradas abaixo 
 
A função da esquerda é referente ao anagrama NAAABN e a função da esquerda é referente à 
função NBNAAA. Perceba que construindo a função desse jeito, cada função corresponde a 
exatamente um anagrama e cada anagrama corresponde a exatamente uma dessas funções. 
Portanto, há uma bijeção. 
Ressaltando novamente que não estamos contando TODAS as funções sobrejetoras, mas só as 
que satisfazem as três condições dadas acima. 
Obs: essa função é bijetora pensando em multisets. 
 
Estratégias e Operações em Contagem 
Esta seção trata de outras duas ideias mais fundamentais de contagem do que as vistas no 
capítulo anterior: a regra do E e a regra do OU. Assim como os paradigmas da contagem citados 
acima, essas duas ideias também podem ser expressas a partir da teoria dos conjuntos. 
 Regra do E ou princípio multiplicativo ↔ produto cartesiano 
A regra do E (também conhecida como Princípio Fundamental da Contagem – PFC ou princípio 
multiplicativo) é associada a tomadas sucessivas de decisão, como pode ser visto no exemplo 
abaixo: 
Uma pessoa possui seis camisetas e três calças, todas distintas. De quantos modos diferentes ela 
pode se vestir utilizando uma camiseta e uma calça? 
Observe que podemos supor que a primeira escolha é a da camiseta, das quais temos seis 
opções (digamos, as opções do conjunto {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹}) e que a segunda escolha será da calça, 
das quais temos três opções (digamos, as opções do conjunto {𝐼, 𝐼𝐼, 𝐼𝐼𝐼}). 
E, o total de maneiras que ela pode se vestir serão todas as duplas ordenadas (___, ___) onde o 
primeiro elemento deve pertencer ao grupo das camisetas e o segundo ao grupo das calças. Ou 
seja, uma maneira de listar todas as possibilidades é fazendo o produto cartesiano: 
{𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹} × {𝐼, 𝐼𝐼, 𝐼𝐼𝐼} =
{(𝐴, 𝐼), (𝐵, 𝐼), (𝐶, 𝐼), (𝐷, 𝐼), (𝐸, 𝐼), (𝐹, 𝐼),
(𝐴, 𝐼𝐼), (𝐵, 𝐼𝐼), (𝐶, 𝐼𝐼), (𝐷, 𝐼𝐼), (𝐸, 𝐼𝐼), (𝐹, 𝐼𝐼),
(𝐴, 𝐼𝐼𝐼), (𝐵, 𝐼𝐼𝐼), (𝐶, 𝐼𝐼𝐼), (𝐷, 𝐼𝐼𝐼), (𝐸, 𝐼𝐼𝐼), (𝐹, 𝐼𝐼𝐼)}
 
E o total de possibilidades será o número de elementos do produto cartesiano, que obtemos 
multiplicando a quantidade de elemento dos conjuntos que representam cada uma das 
escolhas. 
 
 
Obs: há também o princípio da divisão em contagem, que nos permite achar o número de 
elementos a partir de uma contagem que conta um múltiplo dos conjuntos em A. Por exemplo, 
ao contar a quantidade de subconjuntos de dois elementos que existem em {1, 2, 3, 4, 5, 6}, 
podemos contar a quantidade de pares ordenados (𝑎, 𝑏), com 𝑎 ≠ 𝑏 que podemos formar a 
partir desse conjunto, que, pela regra do E será 6 ∙ 5 = 30, e depois perceber que cada 
subconjunto {𝑎, 𝑏} corresponde a exatamente dois pares ordenados: (𝑎, 𝑏) e (𝑏, 𝑎). Portanto, a 
quantidade de subconjuntos em de 2 elementos é 
30
2
= 15. A mesma ideia pode ser usada para 
provar a fórmula de combinação a partir do arranjo ou a fórmula da permutação com elementos 
repetidos a partir da permutação simples. 
 Regra do OU ou princípio aditivo ↔ união de conjuntos 
A regra do OU (também conhecida como divisão em casos ou princípio aditivo) é utilizada para 
divisão em casos. É comum focar essa divisão em casos a partir de uma decisão, especialmente 
quando essa decisão influencia na quantidade de escolhas das outras decisões, como no 
exercício abaixo. 
Uma pessoa possui seis camisetas (A, B, C, D, E e F) e três calças (branca, preta e cinza), todas 
distintas. Quando ela veste a calça branca, ela só usa as camisetas A, B ou C, enquanto que se 
ela usa qualquer uma das outras calças, ela não tem restrição para camisetas. De quantas 
formas ela consegue se vestir utilizando exatamente uma camiseta e uma calça? 
Utilizando a regra do OU, juntamente com a regra do E, separando em casos a partir da escolha 
da pessoa vestir a calça branca ou não é 1 ⋅ 3 + 2 ⋅ 6 = 15 maneiras. Observe que essa operação 
é equivalente a analisar o conjunto dos pares (camiseta, calça) em que a calça é branca, analisar 
o conjunto dos pares (camiseta, calça) em que a calça não é branca e depois realizar a união 
deles e, então, contar a quantidade de elementos no conjunto final, após a união. 
 
Obs: Também há o princípio da subtração, que é usado a partir do cálculo de elementos do 
conjunto complementar. Voltando na questão acima, poderíamos considerar o universo de 
todas as possibilidades da pessoa se vestir, sem nenhuma restrição (já calculamos 
anteriormente que é 18), e destes, podemos calcular quantos casos não satisfazem a condição 
(vemos que são os casos (𝐷, branca), (𝐸, branca) e (𝐹, branca), ou seja, 3 casos). Portanto, 
pelo princípio da subtração, concluímos que há 18 − 3 = 15 maneiras. Essa técnica também é 
conhecida como “total – não pode” ou “tudo – não interessa”. 
 
O exemplo a seguir mostra um caso em que os conjuntos não são disjuntos: 
Quantos números positivos menores ou iguais a 30 são múltiplos de 3 ou de 5? 
Vemos que isso é equivalente a perguntar a união dos conjuntos 
{3, 6, 9, 12, 15, 18, 21, 24, 27, 30} e {5, 10, 15, 20, 25, 30} que contêm
10 e 6 elementos 
respectivamente. A união é {3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30}, apenas 14 
elementos, uma vez que 15 e 30 eram comuns nos conjuntos dos múltiplos de 3 e de 5. 
 
 
Uma forma para se calcular a quantidade de elementos da união de conjuntos não disjuntos é 
utilizando o princípio da inclusão-exclusão. No caso de apenas dois conjuntos, esse princípio diz 
que a quantidade de elementos de 𝐴 ∪ 𝐵 é igual à soma da quantidade de elementos de 𝐴 e 𝐵, 
subtraída da quantidade de elementos comuns a 𝐴 e 𝐵, representada por 𝐴 ∩ 𝐵. 
Bolas e caixas: outra abordagem 
Também é comum utilizar uma bijeção em problemas de contagem com problemas similares 
envolvendo bolas e caixas, com suas características (se as bolas / caixas são distintas ou não, se 
é permitido haver caixas vazias, se há um número máximo de bolas por caixa, etc) variando 
dependendo do problema. Abaixo mostramos um exercício em que essa relação com problemas 
de caixas e bolas fica mais claro: 
Cinco pessoas entraram em um elevador. De quantas maneiras elas podem sair do elevador 
assumindo que o prédio só tem oito andares? E se caso cada uma das pessoas sair em um andar 
diferente? 
Nesse problema, podemos considerar as pessoas como sendo bolas distintas, das quais 
precisamos distribuir em oito caixas também distintas, representando os andares. 
No primeiro caso, não há restrição para nenhuma das caixas. Ou seja, pela regra do E, cada uma 
das pessoas tem 8 possibilidades de escolha, em um total de 85 = 32768 possibilidades. É 
possível mostrar que para 𝑚 bolas distintas e 𝑛 caixas distintas, quando não há uma restrição 
para como as bolas devem ser colocadas, a resposta sempre será igual a 𝑛𝑚. 
Agora, para o segundo caso, há uma restrição para as caixas: cada caixa pode ter no máximo 
uma bolinha. Portanto, pela regra do E, a primeira pessoa tem 8 possibilidades de escolham, a 
segunda 7 (não pode ser o andar que a primeira pessoa escolheu) e assim por diante, em um 
total de 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 = 6720 possibilidades. Observe que esse tipo de pensamento é 
equivalente ao arranjo. Ou seja, a situação em que temos 𝑚 bolas distintas para distribuir em 𝑛 
caixas distintas, de modo que cada caixa tenha no máximo 1 bola apresenta 𝐴𝑚,𝑛 =
𝑚!
(𝑚−𝑛)!
 
possibilidades. Em outras palavras, cada situação de arranjo pode ser interpretada por bolas e 
caixas que seguem essas condições. 
Sequências Notáveis 
Além das ideias apresentadas nas seções anteriores, existem alguns problemas de contagem em 
que se é possível mostrar uma bijeção com sequências conhecidas, como Fibonacci ou Catalan. 
Vamos começar com a sequência de Fibonacci. Essa sequência é definida da seguinte forma: 
{
𝐹0 = 0; 𝐹1 = 1
𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 para 𝑛 ≥ 2
 
Portanto, os primeiros termos da sequência de Fibonacci são os seguintes: 
𝐹0 𝐹1 𝐹2 𝐹3 𝐹4 𝐹5 𝐹6 𝐹7 𝐹8 𝐹9 
0 1 1 2 3 5 8 13 21 34 
 
 
 
E aqui está um problema onde ela aparece: 
De quantas formas é possível cobrir totalmente o tabuleiro 1 × 𝑛 abaixo com pecinhas 1 × 1 e 
1 × 2? 
 
Seja 𝑥𝑛 o número de possibilidades de preencher o tabuleiro 1 × 𝑛. 
Fazendo casos iniciais, percebemos que 𝑥1 =
1, 𝑥2 = 2 e 𝑥3 = 3, como mostrado ao lado. 
Agora, para fazer os casos seguintes, vamos 
utilizar a regra do OU: observe que para a 
primeira casa, sempre temos duas opções – 
preenchê-la com uma pecinha 1 × 1 ou com uma 
pecinha 1 × 2. Veja também que essas duas escolhas necessariamente vão gerar 
preenchimentos diferentes, já que não é possível que a casa 1 esteja preenchida pelos dois tipos 
de pecinhas ao mesmo tempo. 
Analisando o caso em que a primeira casa é preenchida com uma pecinha 1 × 1, ainda restam 
𝑛 − 1 casinhas a serem preenchidas e, pela nossa definição, podem ser preenchidas de 𝑥𝑛−1 
maneiras. Analogamente, no caso em que a primeira casa é preenchida com uma pecinha 1 × 2 
ainda restam 𝑛 − 2 casinhas para serem preenchidas, o que pode ser feito de 𝑥𝑛−2 maneiras, 
como mostrado pelo esquema abaixo: 
 
Portanto, pela regra do OU temos a seguinte relação: 
𝑥𝑛 = 𝑥𝑛−1 + 𝑥𝑛−2 para 𝑛 ≥ 3 
O que é a mesma regra para a sequência de Fibonacci, com a diferença de que os termos iniciais 
são 1 e 2, e não 1 e 1. Ou seja, essa é a sequência de Fibonacci, só que deslocada. Com isso, 
chegamos à conclusão que 
𝑥𝑛 = 𝐹𝑛+1 
Obs: é possível demonstrar que o n-ésimo termo da sequência de Fibonacci consegue ser 
calculado pela fórmula 
 
 
𝐹𝑛 =
(
1 + √5
2 )
𝑛
− (
1 − √5
2 )
𝑛
√5
 
A demonstração disso foge do escopo da aula, e essa relação está aqui a título de curiosidade. 
O importante é perceber que nem sempre precisamos de uma fórmula fechada para calcular 
algo; no exemplo acima, se fosse pedido a quantidade de maneiras de se cobrir um tabuleiro 
1 × 20, seria muito mais fácil descobrir todos os termos da sequência de Fibonacci até 𝐹21 a 
partir de 𝐹1 e 𝐹2 do que calcular 
(
1+√5
2
)
21
−(
1−√5
2
)
21
√5
. 
Outro exemplo em que Fibonacci aparece é no seguinte problema: 
Qual é o número de subconjuntos de {1, 2, 3, 4, … , 𝑛} sem elementos consecutivos? (o conjunto 
vazio é considerado como não tendo elementos consecutivos por não ter nenhum elemento) 
 Seja xn o número de subconjuntos de {1, 2, 3, … , 𝑛} que satisfaz tal propriedade. Vamos analisar 
casos iniciais: 
𝑥0 = 1; 𝑥1 = 2; 𝑥2 = 3; 𝑥3 = 5 
∅ {𝟏} {𝟏, 𝟐} {𝟏, 𝟐, 𝟑} 
∅ ∅ ∅ ∅ 
 {1} {1} {1} 
 {2} {2} 
 {3} 
 {1, 3} 
 
Agora, vamos calcular 𝑥𝑛 em função os valores anteriores. Pela regra do OU, podemos separar 
em dois casos: o que escolhemos o 1 e o que não escolhemos o 1. 
 Caso o número 1 não seja escolhido, temos as possibilidades de escolher os números 
do conjunto {2, 3, 4, … , 𝑛}, que é 𝑥𝑛−1 por definição; 
 Caso o número 1 seja escolhido, o 2 automaticamente não poderá ser. Ou seja, temos 
as possibilidades de escolha do conjunto {3, 4, … , 𝑛}, que é 𝑥𝑛−2 por definição. 
Como escolher ou não o 1 formam subconjuntos diferentes, o número total de subconjuntos 𝑥𝑛 
será definido pela recursão 
𝑥𝑛 = 𝑥𝑛−1 + 𝑥𝑛−2 
E, como os casos iniciais se alinham com a sequência de Fibonacci deslocada, chegamos à 
conclusão que 
𝑥𝑛 = 𝐹𝑛+2 
 
Portanto, deve haver uma bijeção entre a maneira de se preencher um tabuleiro 1 × 𝑛 com 
peças 1 × 1 e 1 × 2 e a quantidade de subconjuntos de {1, 2, 3, 4, … , 𝑛 − 1} de elementos não 
 
 
consecutivos. Ela de fato existe: cada configuração de preencher o tabuleiro corresponde à 
escolha dos números que estão na casa da esquerda dos retângulos 1 × 2. A figura a seguir 
mostra alguns exemplos dessa bijeção para 𝑛 = 7: 
 
Observe também que isso explica porque o tabuleiro 1 × 𝑛 determina apenas para o conjunto 
de 1 até 𝑛 − 1, uma vez que a casa 𝑛 nunca conseguirá ser escolhida. 
 
Outra sequência que vale a pena citar é a dos números de Catalan. O número de Catalan é 
definido como 
𝐶𝑛 =
1
𝑛 + 1
(
2𝑛
𝑛
) para 𝑛 ∈ ℤ+ 
e os primeiros termos dessa sequência são 
𝐶0 𝐶1 𝐶2 𝐶3 𝐶4 𝐶5 𝐶6 𝐶7 𝐶8 𝐶9 
1 1 2 5 14 42 132 429 1430 4862 
 
Eles também satisfazem a recorrência: 
𝐶𝑛 = 𝐶0𝐶𝑛−1 + 𝐶1𝐶𝑛−2 + 𝐶2𝐶𝑛−3 +⋯+ 𝐶𝑛−1𝐶0 
Observe que essa propriedade nos permite calcular 𝐶𝑛 se soubermos o valor de todos os termos 
anteriores da sequência, e isso será bem importante! Agora, vamos à questão: 
De quantas maneiras diferentes é possível dividir um polígono convexo de 𝑛 lados em regiões 
triangulares traçando apenas diagonais que não se intersectam? 
 (aqui, consideramos o polígono 𝑃1𝑃2𝑃3𝑃4…𝑃𝑛, nomeando os pontos em sentido horário para 
que mesmo configurações que possam vir a ser idênticas por simetrias de rotação / reflexão 
sejam tidas como diferentes pois os pontos são diferentes) 
 
 
Vamos novamente analisar casos iniciais primeiro: seja 𝑥𝑛 o número de maneiras de dividir um 
polígono convexo de 𝑛 lados seguindo as condições do enunciado.
Temos que 𝑥3 = 1, 𝑥4 = 2 e 
𝑥5 = 5, a partir das figuras abaixo. 
 
Agora, vamos analisar com calma o caso para 6 lados, a partir do lado 𝑃1𝑃2̅̅ ̅̅ ̅̅ . Como temos que 
dividir toda a região em triângulos, então 𝑃1𝑃2̅̅ ̅̅ ̅̅ deve ser o lado de um triângulo. Pela regra do 
OU, vamos separar em casos com base nos diferentes triângulos que podemos fazer: o terceiro 
vértice deve ser algum entre 𝑃3, 𝑃4, 𝑃5, 𝑃6, e cada uma dessas escolhas nos leva a uma 
configuração diferente, visto que o lado 𝑃1𝑃2̅̅ ̅̅ ̅̅ só pode pertencer a um triângulo, devido à 
condição das diagonais não se intersectarem. 
 
Observe que esse triângulo destacado reparte o hexágono em duas outras regiões: uma à 
esquerda do triângulo e outra à direita (para os casos I e IV considere uma das regiões formadas 
apenas por um segmento de reta). Além disso, definir 𝑥2 = 1, mesmo que não faça sentido 
dividir um segmento de reta em regiões triangulares, auxiliará na resolução do exercício. 
 No caso I a região foi dividida em uma com 2 vértices e outra com 5. Portanto, pela 
regra do E, o total de maneiras de terminar de dividir o hexágono em triângulos é 𝑥5 =
1 ⋅ 𝑥5 = 𝑥2 ⋅ 𝑥5. 
 No caso II, temos a divisão entre um triângulo e um quadrilátero, obtendo 𝑥3 ⋅ 𝑥4. 
 Analogamente, para o caso III obtemos 𝑥4 ⋅ 𝑥3 
 E para o caso IV obtemos 𝑥5 ⋅ 𝑥2. 
Ou seja, temos 𝑥6 = 𝑥2 ⋅ 𝑥5 + 𝑥3 ⋅ 𝑥4 + 𝑥4 ⋅ 𝑥3 + 𝑥5 ⋅ 𝑥2 = 5 + 2 + 2 + 5 = 14. 
De forma análoga, para um polígono de 𝑛 lados obtemos a equação 
𝑥𝑛 = 𝑥2 ⋅ 𝑥𝑛−1 + 𝑥3 ⋅ 𝑥𝑛−2 + 𝑥4 ⋅ 𝑥𝑛−3 +⋯+ 𝑥𝑛−2 ⋅ 𝑥3 + 𝑥𝑛−1 ⋅ 𝑥2 
 
 
O que é exatamente igual à propriedade dos números de Catalan. Além disso, os valores iniciais 
𝑥2 = 1, 𝑥3 = 1, 𝑥4 = 2, 𝑥5 = 5 é exatamente a mesma dos termos iniciais de Catalan. Portanto, 
chegamos à conclusão que 
𝑥𝑛 = 𝐶𝑛−2 
A seguir, mostramos mais um exemplo relacionado ao número de Catalan – a quantidade de 
maneiras de se colocar parênteses em uma expressão: 
Considere que ∗ represente uma operação não associativa entre dois números – ou seja, dados 
três números 𝑎, 𝑏, 𝑐 as expressões ((𝑎 ∗ 𝑏) ∗ 𝑐) e (𝑎 ∗ (𝑏 ∗ 𝑐)) não necessariamente levam ao 
mesmo resultado. Um exemplo seria 𝑎 ∗ 𝑏 = 𝑎𝑏, pois (𝑎𝑏)
𝑐
 e 𝑎(𝑏
𝑐) não são necessariamente 
iguais. 
Agora, suponha uma sequência de 𝑛 números inteiros positivos em que queremos realizar as 
operações 
𝑥1 ∗ 𝑥2 ∗ 𝑥3 ∗ 𝑥4 ∗ …∗ 𝑥𝑛 
em alguma ordem (não é possível altear a posição dos 𝑥’s, só decidir a ordem em que as 
operações são efetuadas). 
De quantas maneiras diferentes essa sequência de operações pode ser realizada? 
 
Seja 𝑆𝑛 o número de maneiras diferentes em que essa operação com 𝑛 números pode ser 
efetuada. Vamos começar a calcular os casos iniciais: 
𝑆1 = 1 𝑆2 = 1 𝑆3 = 2 𝑆4 = 3 
Abaixo temos listados todos os casos para 𝑛 = 1, 2, 3, 4. 
𝑥1 (𝑥1 ∗ 𝑥2) ((𝑥1 ∗ 𝑥2) ∗ 𝑥3) (((𝑥1 ∗ 𝑥2) ∗ 𝑥3) ∗ 𝑥4) 
 (𝑥1 ∗ (𝑥2 ∗ 𝑥3)) ((𝑥1 ∗ (𝑥2 ∗ 𝑥3)) ∗ 𝑥4) 
 ((𝑥1 ∗ 𝑥2) ∗ (𝑥3 ∗ 𝑥4)) 
 (𝑥1 ∗ (𝑥2 ∗ (𝑥3 ∗ 𝑥4))) 
 (𝑥1 ∗ 𝑥2 ∗ 𝑥3 ∗ 𝑥4) 
 
Agora, a partir dos valores iniciais obtidos, vamos tentar calcular 𝑆𝑛 sem explicitamente escrever 
todos os casos. Repare que a cada operação efetuada, reduzimos a quantidade de números na 
nossa sequência em 1 (isto é, depois de efetuar 𝑎 ∗ 𝑏 = 𝑐, os números 𝑎 e 𝑏 serão substituídos 
por 𝑐 na sequência). Perceba também que a última operação a ser efetuada terá apenas dois 
números restantes: (𝑝 ∗ 𝑞). O primeiro número, 𝑝, será formado por alguma combinação de 
𝑥1, 𝑥2, 𝑥3, … , 𝑥𝑘, enquanto o segundo número, 𝑞, será formado por alguma combinação de 
𝑥𝑘+1, 𝑥𝑘+2, … , 𝑥𝑛. 
Ou seja, pela regra do OU podemos dividir nos casos 𝑘 = 1, 2, 3, 4, … , (𝑛 − 1), com todos esses 
casos gerando maneiras diferentes de se realizar as operações. 
 
 
 Caso 𝑘 = 1, há 𝑆1 maneiras de se obter 𝑝 e 𝑆𝑛−1 maneiras de se obter 𝑞. Portanto, pela 
regra do E, há 𝑆1 ∙ 𝑆𝑛−1 maneiras para esse caso; 
 Caso 𝑘 = 2, há 𝑆2 maneiras de se obter 𝑝 e 𝑆𝑛−2 maneiras de se obter 𝑞, levando a um 
total de 𝑆2 ∙ 𝑆𝑛−2 maneiras. 
 ... 
Em geral, conseguimos ver que para um certo 𝑘, há 𝑆𝑘 ∙ 𝑆𝑛−𝑘 maneiras, e, portanto, o total de 
maneiras 𝑆𝑛 pode ser calculado por: 
𝑆𝑛 = 𝑆1 ∙ 𝑆𝑛−1 + 𝑆2 ∙ 𝑆𝑛−2 +⋯+ 𝑆𝑘 ∙ 𝑆𝑛−𝑘 +⋯+ 𝑆𝑛−1𝑆1 
Que é exatamente a recorrência da sequência de Catalan. Como os termos iniciais são 
exatamente iguais aos primeiros termos da sequência de Catalan, concluímos que 
𝑆𝑛 = 𝐶𝑛−1 
Mas não é só isso. Observe que a resposta dos dois exercícios anteriores eram a sequência de 
Catalan (deslocada, mas ainda assim sendo a sequência de Catalan). Portanto, podemos 
procurar uma bijeção entre as maneiras de dividir um polígono regular de 𝑛 lados em triângulos 
e as maneiras de efetuar as operações em 𝑥1 ∗ 𝑥2 ∗ 𝑥3 ∗ … ∗ 𝑥𝑛−1. E ela é a seguinte: 
 Defina a base do seu polígono (no exercício de Catalan, ela é o segmento 𝑃1𝑃2̅̅ ̅̅ ̅̅ ); 
 A partir da base, no sentido horário, coloque os números 𝑥1, 𝑥2, 𝑥3, … , 𝑥𝑛−1 em ordem, 
um sobre cada lado do polígono; 
 Os triângulos formados indicarão a ordem das operações: caso haja um triângulo com 
dois lados representando os valores 𝑎 e 𝑏, o terceiro lado deverá representar o valor 
𝑎 ∗ 𝑏, sempre tomando cuidado para seguir a ordem dos índices de 𝑥1, 𝑥2, … , 𝑥𝑛−1; 
 Fazendo esse esquema para achar o valor de todos os lados e das diagonais usadas na 
triangularização, o valor obtido na base do polígono corresponderá a exatamente uma 
maneira de efetuar a operação. 
Abaixo, mostramos um exemplo para 𝑛 = 7 obtendo a expressão a partir da triangularização: 
 
E também um exemplo de obter a triangularização a partir de uma expressão, fazendo o 
processo inverso dos passos acima. 
 
 
 
De um modo similar para um polígono de 𝑛 lados, conseguimos mostrar que cada expressão 
remete a exatamente uma triangularização e vice-versa, demonstrando que realmente há uma 
bijeção entre esses dois conjuntos. 
 
Obs: Existe também um problema similar sobre o número de maneiras de se construir uma 
expressão apenas com “(” e “)”, de modo que todo parêntese aberto seja fechado e vice-versa. 
Por exemplo, as expressões válidas com ((( e ))) são ()()(), (())(), ()(()), ((())), (()()), enquanto que 
)((()) não e válido, pois começamos fechando um parêntese que não havíamos aberto. O número 
de expressões válidas é exatamente igual a 𝐶4, e é possível mostrar que isso também gera a 
sequência de Catalan ao se aplicar com uma quantidade maior de parênteses. 
 
Por fim, vamos a último exercício, que não remete a nenhuma sequência notável, mas que é 
resolvido a partir de uma recorrência. 
 
Uma formiga está no ponto A indicado na malha triangular abaixo, e quer ir para o ponto B. Ela 
pode realizar apenas os seguintes movimentos: 
De quantas maneiras ela pode fazer isso? 
 
 
 
Vamos colocar uma variável 𝑥𝑖,𝑗 sobre cada vértice 
do triângulo, como na figura ao lado. Nela, 𝑖 
representa o número a linha e 𝑗 representa o 
número da reta que é paralela ao lado 𝐴𝐵̅̅ ̅̅ . A 
variável 𝑥𝑖,𝑗 representa o número de maneiras de se 
chegar do ponto em que a variável está até o ponto 
B utilizando apenas os movimentos permitidos. 
Observe que, dessa maneira, 𝑥0,0 = 1 (só existe uma 
maneira de chegar a B se ela já está em B, que é 
fazendo 0 movimentos). Também conseguimos ver 
facilmente que 𝑥1,1 = 𝑥2,2 = 𝑥3,3 = 𝑥4,4 = 1 (só há 
uma maneira dela chegar em B a partir de cada um desses pontos). Além disso, para 
descobrirmos o valor das outras variáveis, temos a seguinte relação 
𝑥𝑖,𝑗 = 𝑥(𝑖−1),(𝑗−1) + 𝑥(𝑖−1),𝑗 + 𝑥𝑖,(𝑗+1) 
Evidentemente, válido apenas para 𝑖′𝑠 e 𝑗′𝑠 em que 𝑥𝑖,𝑗 está escrito no triângulo. Além disso, 
se algum 𝑥(𝑖−1),(𝑗−1), 𝑥(𝑖−1),𝑗, 𝑥𝑖,(𝑗+1) não estiver definido no triângulo, ele será tratado como 
zero (a formiga
não pode sair do triângulo). Com isso, 
conseguimos calcular todos os 𝑥′𝑠 da figura, obtendo a 
figura ao lado 
E, portanto, há 90 maneiras da formiga ir de A para B.