Contagem, permutações e combinação

Prévia do material em texto

Contagem, permutac¸o˜es e combinac¸a˜o
Edna A. Hoshino
Facom - UFMS
junho de 2015
E. Hoshino (Facom-UFMS) Contagem junho de 2015 1 / 63
To´picos
1 Contagem
Princ´ıpios Ba´sicos de Contagem
Princ´ıpio da Inclusa˜o-Exclusa˜o
Princ´ıpio da Casa dos Pombos
2 Permutac¸a˜o e combinac¸a˜o
Permutac¸o˜es
Combinac¸a˜o
Permutac¸o˜es e Combinac¸o˜es Generalizadas
3 Coeficientes Binomiais
4 Relac¸o˜es de Recorreˆncia
E. Hoshino (Facom-UFMS) Contagem junho de 2015 2 / 63
Contagem Princ´ıpios Ba´sicos de Contagem
Regra do produto
E´ usada quando um procedimento pode ser quebrado em uma sequ¨eˆncia
de duas tarefas. Se existem n1 meios de realizar a primeira tarefa e, para
cada um destes meios, existirem n2 meios de realizar a segunda tarefa,
enta˜o existem n1n2 meios de realizar o procedimento.
Exemplo 1
Uma pequena empresa com apenas dois empregados, Joa˜o e Paulo, alugou
um andar de um pre´dio com 12 salas. De quantas formas diferentes
pode-se associar os empregados a salas diferentes?
O procedimento de associar os empregados a`s salas consiste em associar
uma sala a Joa˜o, que pode ser feito de 12 formas, e enta˜o associar Paulo a
uma das 11 salas diferentes que a de Joa˜o. Pela regra do produto, existem
12x11 = 132 meios de associar as salas aos dois empregados.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 3 / 63
Contagem Princ´ıpios Ba´sicos de Contagem
Exemplos
Exemplo 2
As cadeiras de um audito´rio sa˜o rotuladas com uma letra e um inteiro
positivo nao excedendo 100. Qual e´ o nu´mero ma´ximo de cadeiras que
podem ser rotuladas desta forma (na˜o se admite ro´tulos iguais)?
O procedimento de rotular as cadeiras consiste em associar uma das 26
letras e enta˜o associar um dos 100 inteiros poss´ıveis. Pela regra do
produto existem, no ma´ximo, 26x100 = 2600 ro´tulos diferentes.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 4 / 63
Contagem Princ´ıpios Ba´sicos de Contagem
Regra do Produto (cont.)
A regra do produto pode ser estendida para o caso em que o procedimento
consiste em n tarefas consecutivas T1,T2, . . . ,Tn. Pode-se provar por
induc¸a˜o matema´tica que se cada tarefa Ti pode ser realizada em mi meios
diferentes depois que as tarefas anteriores foram realizadas enta˜o existem
m1m2 . . .mn meios de realizar o procedimento.
Exemplo 3
Quantas cadeias diferentes de 7 bits existem?
Cada cadeia pode ser formada escolhendo-se cada um dos 7 bits por vez.
Cada um dos bits pode ser escolhido de duas formas diferentes, ou seja, 0
ou 1. Logo, pela regra do produto existem 27 = 128 diferentes cadeias de
bits de comprimento 7.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 5 / 63
Contagem Princ´ıpios Ba´sicos de Contagem
Exemplos
Exemplo 4
Quantas placas de ve´ıculos existem se cada placa conte´m uma sequ¨eˆncia
de 3 letras seguida por 4 d´ıgitos?
Existem 26 escolhas para cada letra e 10 escolhas para cada um dos
quatro d´ıgitos. Portanto, pela regra do produto existem
26x26x26x10x10x10x10 = 175.760.000 placas veiculares diferentes.
Exemplo 5
Quantas func¸o˜es f : A 7→ B existem se |A| = m e |B | = n?
Cada func¸a˜o f associa um elemento do dom´ınio a algum dos n elementos
do contra-dom´ınio. Logo, pela regra do produto, existem nm func¸o˜es
diferentes de A para B .
E. Hoshino (Facom-UFMS) Contagem junho de 2015 6 / 63
Contagem Princ´ıpios Ba´sicos de Contagem
Regra da soma
E´ usada quando um procedimento pode ser realizado ou de uma das n1
formas diferentes ou de um dos n2 meios alternativos, onde nenhuma das
n1 formas e´ igual a algum dos n2 meios. Neste caso, existem n1 + n2
meios de realizar o procedimento.
Exemplo 1
Suponha que ou um professor ou um estudante da Faculdade e´ escolhido
para ser representante da Faculdade em um comiteˆ da Universidade.
Quantas escolhas diferentes existem para o representante se existem 37
professores e 83 estudantes?
Existem 37 meios de escolher um professor e 83 para um estudante. Como
nenhum professor e´ estudante da faculdade, a regra da soma diz que
existem 37 + 83 meios diferentes para a escolha do representante.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 7 / 63
Contagem Princ´ıpios Ba´sicos de Contagem
Exemplos mais complexos
Exemplo 2
Em uma linguagem de programac¸a˜o, o nome de uma varia´vel e´ formada
por um ou dois caracteres alfanume´ricos. Ale´m disso, o nome deve
comec¸ar com uma letra e deve ser diferente de 5 palavras reservadas de 2
caracteres. Quantos nomes distintos de varia´veis podem existir nesta
linguagem?
O nome da varia´vel ou e´ formada por 1 letra ou por 2 caracteres sendo o
primeiro obrigatoriamente uma letra. Como os dois casos sa˜o exclusivos,
temos pela regra da soma que o total de nomes diferentes e´ n1 + n2, sendo
n1 o total de nomes com 1 letra e n2 o total de nomes formados por 2
caracteres. Temos um total de 26 poss´ıveis escolhas para a letra logo
n1 = 26. Pela regra do produto, existem 26x36 nomes diferentes formados
por 2 caracteres sendo o primeiro uma letra. Como 5 deles sa˜o reservados,
temos que n2 = 26x36 − 5. Logo, existem 26 + 26x36 − 5 nomes
diferentes.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 8 / 63
Contagem Princ´ıpios Ba´sicos de Contagem
Mais exemplos
Exemplo 3
Um enderec¸o IP consiste em uma cadeia de 32 bits. Ele comec¸a com um
netid, que identifica a rede, e e´ seguido por um hostid, que identifica um
computador particular da rede. Existem 3 formas de enderec¸amento.
Classe A e´ usada para redes grandes e consiste de um 0 seguido por um
netid de 7 bits e um hostid de 24 bits. Classe B e´ usada para redes de
tamanho moderado e consiste da cadeia 10 seguindo por um netid de 14
bits e um hostid de 16 bits. Classe C e´ usada para redes pequenas e
consiste da cadeia 110 seguindo por um netid de 21 bits e um hostid de 8
bits. Existem outras classes, mas estas sa˜o reservadas. O netid 1111111
na˜o e´ permitido na classe A e os hostids formados por apenas 0s ou 1s
tambe´m na˜o esta˜o dispon´ıveis em qualquer uma das classes. Quantos
enderec¸os de IPs sa˜o suportados?
Soluc¸a˜o: Exerc´ıcio!
E. Hoshino (Facom-UFMS) Contagem junho de 2015 9 / 63
Contagem Princ´ıpios Ba´sicos de Contagem
Mais Exemplos
Exemplo 4
Suponha um sistema que admite senhas de 6 a 8 caracteres, onde cada
caracter e´ uma letra ou um d´ıgito e senhas sem nenhum d´ıgito na˜o seja
permitido. Quantas senhas diferentes sa˜o admitidas neste sistema?
Seja P o total de senhas poss´ıveis e sejam P6, P7 e P8 o total de senhas
de 6, 7 e 8 caracteres, respectivamente. Pela regra da soma,
P = P6 + P7 + P8. Para calcular P6 e´ mais fa´cil encontrar o total de
senhas formadas por letras e d´ıgitos, incluindo aqueles com nenhum d´ıgito
e subtrair destes o total de senhas formadas com nenhum d´ıgito. Logo,
P6 = 36
6 − 266. Analogamente, P7 = 36
7 − 267 e P8 − 36
8 − 268.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 10 / 63
Contagem Princ´ıpio da Inclusa˜o-Exclusa˜o
Princ´ıpio da Inclusa˜o e Exclusa˜o
E´ usado nos casos em que uma tarefa pode ser feita em n1 ou em n2
meios, mas alguns de n1 tambe´m esta˜o em n2. Nesta situac¸a˜o, a regra da
soma na˜o pode ser usada!
Consiste em adicionar os meios de realizar n1 e n2 e enta˜o subtrair o total
de meios em comum entre n1 e n2.
Exemplo 1
Quantas cadeias de 8 bits que comec¸am com 1 ou que terminam com 00
existem?
Seja n1 as cadeias de 8 bits que comec¸am com 1 e n2 as que terminam
com 00. Note que n1 e n2 teˆm cadeias em comum. Pelo princ´ıpio da
inclusa˜o-exclusa˜o, pode-se somar o total de elementos em n1 e em n2 e
subtrair aqueles que esta˜o tanto em n1 quanto em n2. Logo, o total de
cadeias e´ 27 + 26 − 25.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 11 / 63
Contagem Princ´ıpio da Inclusa˜o-Exclusa˜o
Princ´ıpio da Inclusa˜o e Exclusa˜o (cont.)
Note que ja´ hav´ıamosusado o princ´ıpio da inclusa˜o-exclusa˜o em teoria dos
conjuntos! |A ∪ B | = |A|+ |B | − |A ∩ B |.
Exemplo 2
Uma empresa recebeu 350 curr´ıculos de candidatos para uma vaga de TI.
Destes, 220 teˆm formac¸a˜o em computac¸a˜o, 147 em administrac¸a˜o e 51 em
ambas as a´reas. Quantos dos inscritos na˜o teˆm formac¸a˜o em computac¸a˜o
nem administrac¸a˜o?
Seja A o conjunto dos candidatos com formac¸a˜o em computac¸a˜o, B o dos
com formac¸a˜o em administrac¸a˜o. Neste caso, A ∪ B conte´m aqueles com
formac¸a˜o em computac¸a˜o ou em administrac¸a˜o (ou ambos) e, A ∩ B
aqueles que tem formac¸a˜o em ambos. Pelo princ´ıpio da inclusa˜o-exclusa˜o,
|A ∪ B | = |A|+ |B | − |A ∩ B | = 220 + 147 − 51 = 316. Logo, o total de
candidatos de outras a´reas e´ 350 − 316 = 34.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 12 / 63
Contagem Princ´ıpio da Inclusa˜o-Exclusa˜o
Diagrama de A´rvore
Usada para resolver problemas de contagem. Cada ramo da a´rvore indica
uma escolha e as folhas indicam as sa´ıdas poss´ıveis.
Exemplo 1
Quantas cadeias de 4 bits com nenhum par de 1s consecutivos existem?
E. Hoshino (Facom-UFMS) Contagem junho de 2015 13 / 63
Contagem Princ´ıpio da Inclusa˜o-Exclusa˜o
Exerc´ıcios
1 Uma camiseta vem em 12 cores, tem a versa˜o masculina e feminina e
esta´ dispon´ıvel em 3 tamanhos diferentes para cada sexo. Quantos
tipos diferentes destas camisetas sa˜o produzidas?
2 Quantas cadeias de bits de comprimento menor ou igual a 6 existem?
3 Quantas cadeias de 3 digitos decimais existem se:
1 o mesmo d´ıgito na˜o ocorre treˆs vezes;
2 comec¸a com um d´ıgito ı´mpar;
3 tem exatamente dois d´ıgitos 4.
4 Uma pal´ındrome e´ uma palavra que e´ ideˆntica ao seu reverso.
Quantas cadeias de bits de comprimento n sa˜o pal´ındromes?
5 Quantas cadeias de 7 bits que comec¸am com dois 0s ou terminam
com treˆs 1s existem?
6 Use o diagrama de a´rvore para determinar o total de subconjuntos de
{3, 7, 9, 11, 24} com a propriedade que a soma dos elementos do
subconjuntos e´ menor que 28.
7 Use induc¸a˜o matema´tica para mostrar que a regra da soma vale para
m tarefas.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 14 / 63
Contagem Princ´ıpio da Casa dos Pombos
Princ´ıpio da Casa dos Pombos
Se k e´ um inteiro positivo e k + 1 ou mais objetos sa˜o colocados em k
caixas enta˜o existe pelo menos uma caixa contendo dois ou mais objetos.
Prova: Suponha, por contradic¸a˜o, que nenhuma das caixas conte´m mais
que um objeto. Logo, o total de objetos colocados em caixas sera´ no
ma´ximo k , que e´ um absurdo ja´ que existem pelo menos k + 1 objetos.
Corola´rio
Uma func¸a˜o f de um conjunto com k + 1 ou mais elementos para um
conjunto com k elementos na˜o e´ injetora.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 15 / 63
Contagem Princ´ıpio da Casa dos Pombos
Exemplos
Exemplo 1
Em qualquer grupo de 367 pessoas existem, pelo menos, duas pessoas no
grupo que fazem aniversa´rio no mesmo dia, porque existem somente 366
dias poss´ıveis de aniversa´rio.
Exemplo 2
Em um grupo de 27 palavras deve existir pelo menos duas que comec¸am
com a mesma letra.
Exemplo 3
Quantos estudantes na sala devem existir para garantir que pelo menos
dois deles receberam a mesma pontuac¸a˜o no exame final, se a pontuac¸a˜o
vai de 0 a 100?
E. Hoshino (Facom-UFMS) Contagem junho de 2015 16 / 63
Contagem Princ´ıpio da Casa dos Pombos
Princ´ıpio da casa dos pombos generalizado
Generalizac¸a˜o:
Se N objetos sa˜o colocados dentro de k caixas enta˜o existe pelo menos
uma caixa contendo pelo menos ⌈N/k⌉ objetos.
Prova:
Suponha, por contradic¸a˜o, que nenhuma das caixas conte´m mais que
⌈N/k⌉ − 1 objetos.
Uma vez que ⌈N/k⌉ < (N/k) + 1, segue que o total de objetos colocados
nas caixas e´ no ma´ximo
k(⌈N/k⌉ − 1) < k((N/k + 1)− 1) = N,
que e´ uma contradic¸a˜o.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 17 / 63
Contagem Princ´ıpio da Casa dos Pombos
Exemplos
Exemplo 1
Em um grupo de 100 pessoas existem pelo menos ⌈100/12⌉ = 9 que
nasceram no mesmo meˆs.
Exemplo 2
Qual e´ o menor nu´mero de alunos numa sala para garantir que pelo menos
8 deles recebam o mesmo conceito, se existem 5 poss´ıveis conceitos, A, B,
C, D e E?
O menor nu´mero de alunos para garantir que oito deles recebam o mesmo
conceito e´ o menor inteiro N tal que ⌈N/5⌉ = 8. Logo, N = 7x5 + 1 = 36.
Exemplo 3
Quantas cartas de um baralho com 52 cartas devem ser selecionadas para
garantir que pelo menos 3 delas sejam do mesmo naipe?
E. Hoshino (Facom-UFMS) Contagem junho de 2015 18 / 63
Contagem Princ´ıpio da Casa dos Pombos
Exerc´ıcios
1 Mostre que se existem 30 alunos em uma sala enta˜o pelo menos dois
deles teˆm a mesma inicial no sobrenome.
2 Mostre que em qualquer grupo de 5 inteiros existem dois com o
mesmo resto quando dividido por 4.
3 considere uma caixa com 10 bolas vermelhas e 10 bolas azuis, da qual
bolas sa˜o retiradas aleatoriamente. Quantas bolas devem ser retiradas
para obter:
1 pelo menos treˆs bolas da mesma cor?
2 pelo menos treˆs bolas azuis?
4 Mostre que em uma festa com pelo menos duas pessoas existem duas
pessoas que conhecem o mesmo nu´mero de pessoas na festa.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 19 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es
Permutac¸o˜es
Problema t´ıpico
De quantas formas diferentes podemos selecionar 3 estudantes de um
grupo de 5 estudantes para se posicionarem lado-a-lado para uma foto? E
se quise´ssemos arranjar todos eles?
Note que a ordem dos estudantes selecionados importa!
Existem 5 meios de selecionar o primeiro estudante. Uma vez que o
primeiro foi selecionado, existira´ 4 meios para selecionar o segundo
estudante e, por fim, apo´s os dois primeiros, restara´ 3 meios de selecionar
o u´ltimo estudante. Logo, pela regra do produto, existira´ 5.4.3 = 60
formas diferentes de selecionar 3 estudantes de um grupo de 5.
De forma ana´loga, para arranjar todos eles, ter´ıamos 5.4.3.2.1 = 120
possibilidades.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 20 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es
Permutac¸o˜es e r -permutac¸o˜es
Permutac¸a˜o
E´ um arranjo ordenado dos objetos de um conjunto.
r -permutac¸a˜o
E´ um arranjo ordenado de r objetos de um conjunto.
Exemplos
Seja S = {1, 2, 3}. O arranjo ordenado 3, 1, 2 e´ uma permutac¸a˜o de S . O
arranjo 3, 2 e´ uma 2-permutac¸a˜o de S .
O nu´mero de r -permutac¸o˜es de um conjunto com n elementos e´ denotado
por P(n, r) e pode ser encontrado pela regra do produto.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 21 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es
Propriedades
Teorema 1
Se n e´ um inteiro positivo e r um inteiro entre 1 e n enta˜o existem
P(n, r) = n(n − 1)(n − 2) . . . (n − r + 1) r -permutac¸o˜es de um conjunto
com n elementos distintos.
Prova:
Uma r -permutac¸a˜o pode ser formada escolhendo-se o primeiro elemento
da permutac¸a˜o, depois o segundo e assim por diante ate´ o r -e´simo
elemento. Logo, podemos usar a regra do produto para contar o total de
r -permutac¸o˜es. Para escolher o primeiro elemento temos n meios de
fazeˆ-lo ja´ que existem n elementos no conjunto. Para o segundo elemento,
existira˜o n − 1 elementos, uma vez que sobraram n − 1 elementos. Logo,
para o i -e´simo elemento existira˜o n − (i − 1) meios de seleciona´-lo.
Portanto, P(n, r) = n(n − 1)(n − 2) . . . (n − (r − 1)).
P(n, 0) = 1.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 22 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es
Propriedades
Corola´rio
Se n e r sa˜o inteiros com 0 ≤ r ≤ n enta˜o P(n, r) = n!(n−r)! .
Exemplo 1
Quantas formas diferentes de selecionar o primeiro, o segundo e o terceiro
colocado de uma lista de 100 candidatos?
Como a ordem importa, temos um caso de arranjo ordenado e portanto
existem P(100, 3) = 100x99x98 = 970200selec¸o˜es diferentes.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 23 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es
Exemplos
Exemplo 2
Um vendedor precisa visitar 8 cidades diferentes e deve comec¸ar a viagem
em uma cidade espec´ıfica, mas pode visitar as demais em qualquer ordem.
De quantas formas diferentes o vendedor pode fazer estas visitas?
Como a primeira cidade a ser visitada ja´ esta´ definida, resta ao vendedor
escolher a ordem para visitar as demais 7 cidades, logo, existem 7! formas
diferentes de fazeˆ-lo.
Exemplo 3
Quantas permutac¸o˜es das letras ABCDEFGH conte´m a palavra ABC?
Como a palavra ABC deve aparecer como um bloco na permutac¸a˜o,
podemos trata´-lo como uma u´nica letra, digamos X , e enta˜o resta fazer a
permutac¸a˜o das letras XDEFGH, que nos da´ um total de 6! permutac¸o˜es.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 24 / 63
Permutac¸a˜o e combinac¸a˜o Combinac¸a˜o
Combinac¸a˜o
Problema t´ıpico
Quantos comiteˆs diferentes de 3 estudantes podem ser formados de um
grupo de 4 estudantes?
Note que a ordem dos estudantes selecionados na˜o importa!
Basta calcular o total de subconjuntos de 3 elementos que pode ser
formado de um conjunto de 4 elementos. E´ fa´cil de ver que existem 4 de
tais subconjuntos, pois escolher um trio de quatro pessoas equivale a
escolher um dos estudantes para ficar fora do comiteˆ.
r -combinac¸a˜o
E´ uma selec¸a˜o na˜o ordenada de r elementos de um conjunto, ou seja, e´
um subconjunto de r elementos. O total de r -combinac¸o˜es de um
conjunto com n elementos e´ denotado por C (n, r).
E. Hoshino (Facom-UFMS) Contagem junho de 2015 25 / 63
Permutac¸a˜o e combinac¸a˜o Combinac¸a˜o
Combinac¸a˜o (cont.)
C (n, r) tambe´m e´ denotado por
(
n
r
)
e e´ chamado de coeficiente binomial.
Exemplo 1
C (4, 2) = 6 pois as 2-combinac¸o˜es de um conjunto {a, b, c , d} sa˜o os seis
subconjuntos {a, b}, {a, c}, {a, d}, {b, c}, {b, d} e {c , d}.
Teorema
O nu´mero de r -combinac¸o˜es de um conjunto com n elementos, onde n e´
um inteiro na˜o-negativo e r e´ um inteiro com 0 ≤ r ≤ n, e´ igual a
C (n, r) =
n!
r !(n − r)!
.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 26 / 63
Permutac¸a˜o e combinac¸a˜o Combinac¸a˜o
Propriedades
Prova:
A prova segue do fato de que pode-se obter todas as r -permutac¸o˜es de um
conjunto com n elementos a partir das C (n, r) r -combinac¸o˜es do conjunto
e ordenando os elementos em cada r -combinac¸a˜o, que pode ser feito em
P(r , r) meios. Logo,
P(n, r) = C (n, r)P(r , r),
do qual segue que
C (n, r) =
P(n, r)
P(r , r)
=
n!/(n − r)!
r !/(r − r)!
=
n!
r !(n − r)!
.
Note que C (n, r) = n!
r !(n−r)! =
n(n−1)...(n−r+1)
r ! .
E. Hoshino (Facom-UFMS) Contagem junho de 2015 27 / 63
Permutac¸a˜o e combinac¸a˜o Combinac¸a˜o
Exemplos
Exemplo 2
Quantas combinac¸o˜es de 5 cartas pode-se obter de um baralho de 52
cartas? E se pega´ssemos 47 cartas?
Uma vez que a ordem na˜o importa, temos um caso de r -combinac¸a˜o.
Logo, existem C (52, 5) = 52!5!47! =
52.51.50.49.48
5.4.3.2.1 = 2598960 combinac¸o˜es
diferentes com 5 cartas.
Para 47 cartas, temos C (52, 47) = 52!47!5! combinac¸o˜es, ou seja, o mesmo
que com 5 cartas!
Corola´rio
Seja n e r inteiros na˜o-negativos com r ≤ n. Enta˜o C (n, r) = C (n, n − r).
E. Hoshino (Facom-UFMS) Contagem junho de 2015 28 / 63
Permutac¸a˜o e combinac¸a˜o Combinac¸a˜o
Exemplos
Exemplo 3
Quantas cadeias de n bits contendo exatamente r 1s existem?
As posic¸o˜es dos r 1s na cadeia de bits de comprimento n formam uma
r -combinac¸a˜o do conjunto {1, 2, 3, . . . , n}. Logo, existem C (n, r) cadeias
de n bits contendo exatamente r 1s.
Exemplo 4
Suponha que existem 9 professores no depto de matema´tica e 11 no de
computac¸a˜o. Quantos meios diferentes existem de selecionar um comiteˆ
formado por 3 professores do depto de matema´tica e 4 do de computac¸a˜o?
Pela regra do produto, o total e´ obtido pelo produto do nu´mero de
3-combinac¸o˜es de um conjunto de 9 elementos e o de 4-combinac¸o˜es de
um de 11 elementos, ou seja, C (9, 3)C (11, 4) = 9!3!6!
11!
4!7! = 27720.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 29 / 63
Permutac¸a˜o e combinac¸a˜o Combinac¸a˜o
Exerc´ıcios
1 Quantas permutac¸o˜es de {a, b, c , d , e, f , g} terminadas com a
existem?
2 Se um clube tem 25 membros, quantos comiteˆs executivos diferentes
podem ser formados por 4 membros do clube? E se quise´ssemos
selecionar um presidente, um vice-presidente, um secreta´rio e um
tesoureiro, quantas escolhas ter´ıamos?
3 Quantas cadeias de 10 bits contendo:
1 exatamente quatro 1s existem?
2 no ma´ximo quatro 1s existem?
3 pelo menos quatro 1s existem?
4 uma quantidade igual de 0s e 1s existem?
4 Quantas cadeias de bits conte´m exatamente oito 0s e dez 1s se todo
0 deve ser imediatamente seguindo por um 1?
5 Quantas formas diferentes existem de dispor 6 pessoas em torno de
uma mesa circular, se uma disposic¸a˜o e´ considerada a mesma que
outra se pode ser obtida da outra rotacionando a mesa?
E. Hoshino (Facom-UFMS) Contagem junho de 2015 30 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Permutac¸o˜es com repetic¸a˜o
Problema T´ıpico
Quantas palavras de comprimento r podem ser formadas?
Pela regra do produto, como existem 26 letras e cada letra pode ser usada
repetidamente, existem 26r palavras de comprimento r .
Teorema
O nu´mero de r -permutac¸o˜es de um conjunto com n objetos, onde
repetic¸a˜o de objetos e´ permitida, e´ nr .
E. Hoshino (Facom-UFMS) Contagem junho de 2015 31 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Combinac¸o˜es com repetic¸a˜o
Problema T´ıpico
De quantas formas quatro pedac¸os de frutas podem ser selecionados de
uma tigela contendo pedac¸os de mac¸a, laranja e pera? Considere que
existem pelo menos quatro pedac¸os de cada tipo de fruta.
Existem 15 formas:
4 mac¸as 4 laranjas 4 peras
3 mac¸as e 1 laranja 3 mac¸as e 1 pera 3 laranjas e 1 mac¸a
3 mac¸as e 1 pera 3 peras e 1 mac¸a 3 peras e 1 laranja
2 mac¸as e 2 laranjas 2 mac¸as e 2 peras 2 laranjas e 2 peras
2 mac¸as, 1 laranja e 1 pera 2 laranjas, 1 mac¸a e 1 pera 2 peras, 1 mac¸a
e 1 laranja
E. Hoshino (Facom-UFMS) Contagem junho de 2015 32 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Combinac¸a˜o com repetic¸a˜o (cont.)
Teorema
Existem C (n + r − 1, r) = C (n + r − 1, n − 1) r -combinac¸o˜es de um
conjunto com n elementos quando repetic¸a˜o de elementos e´ permitida.
Prova:
Uma r -combinac¸a˜o de n elementos quando repetic¸a˜o e´ permitida pode ser
representada por uma lista de n − 1 barras e r estrelas, onde as n − 1 barras sa˜o
usadsa para separar n ce´lulas e a i-e´sima ce´lula conte´m uma estrela para cada
ocorreˆncia do i-e´simo elemento na combinac¸a˜o.
Por exemplo, uma 6-combinac¸a˜o de um conjunto com 4 elementos e´ representado
com 3 barras e 6 estrelas como ∗ ∗ | ∗ || ∗ ∗∗ que representa uma combinac¸a˜o
contendo duas vezes o primeiro elemento, uma vez o segundo, nenhuma vez o
terceiro e 3 vezes o quarto elemento.
Note que existem C (n − 1 + r , r) destas listas, uma vez que cada lista
corresponde a uma escolha das n− 1 + r posic¸o˜es para colocar as r estrelas. Esta
quantidade e´ igual a C (n − 1 + r , n − 1) pois cada lista tambe´m corresponde a
uma escolha das n − 1 + r posic¸o˜es para colocar as n − 1 barras.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 33 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Exemplos
Exemplo 1
Suponha que sa˜o vendidos 4 tipos diferentes de cookies. Quantas
maneiras diferentes existem de escolher 6 cookies?
Usando o teorema anterior, segue que existem
C (4 + 6− 1, 6) = C (9, 6) = C (9, 3) = 9x8x71x2x3 = 84.
E. Hoshino(Facom-UFMS) Contagem junho de 2015 34 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Exemplos
Exemplo 2
Quantas soluc¸o˜es a equac¸a˜o
x1 + x2 + x3 = 11
tem, onde x1, x2 e x3 sa˜o inteiros na˜o-negativos?
Este problema e´ equivalente a escolher 11 itens de 3 tipos diferentes.
Logo, existem C (11 + 3− 1, 11) = C (13, 11) = C (13, 2) = 13x121x2 = 78
soluc¸o˜es para a equac¸a˜o.
E se as restric¸o˜es x1 ≥ 1, x2 ≥ 2 e x3 ≥ 3 fossem adicionadas?
E. Hoshino (Facom-UFMS) Contagem junho de 2015 35 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Permutac¸o˜es com objetos indistingu¨´ıveis
Problema t´ıpico
Quantas palavras diferentes podem ser feitas reordenando as letras da
palavra “SUCCESS”?
Note que a resposta na˜o e´ 7!. Embora existam 7 letras na palavra, existem
3 S’s e 2 C’s que sa˜o indistingu¨´ıveis entre si. Note que os 3 S’s podem ser
colocados em 7 posic¸o˜es em C (7, 3) meios diferentes, deixando 4 posic¸o˜es
livres. Os 2 C’s podem ser colocados nas 4 posic¸o˜es em C (4, 2) meios
deixando 2 posic¸o˜es livres. Assim, o U pode ser colocado em 2 posic¸o˜es
em C (2, 1) meios e, por fim, o E pode ser colocado em C (1, 1) meios.
Logo, existem
C (7, 3)C (4, 2)C (2, 1)C (1, 1) =
7!
3!4!
4!
2!2!
2!
1!1!
1!
1!0!
=
7!
3!2!1!1!
= 420.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 36 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Permutac¸o˜es com objetos indistingu¨´ıveis (cont.)
Teorema
O nu´mero de permutac¸o˜es de n objetos, onde existem ni objetos
indistingu¨´ıveis do tipo i , para i = 1, . . . , k , e´
n!
n1!n2! . . . nk !
.
Prova:
Note que os n1 objetos do tipo 1 podem ser colocados nas n posic¸o˜es em
C (n, n1) meios, deixando n − n1 posic¸o˜es livres. Enta˜o, os objetos do tipo
2 podem ser colocados em C (n − n1, n2) meios deixando n − n1 − n2
posic¸o˜es livres e, assim por diante. Portanto, pela regra do produto, o
total de permutac¸o˜es diferentes e´
C (n, n1)C (n − n1, n2) . . .C (n − n1 − . . . nk−1, nk)
= n!
n1!(n−n1)
(n−n1)!
n2!(n−n1−n2)!
. . .
(n−n1−...−nk−1)!
nk !0!
= n!
n1!n2!...nk !
.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 37 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Distribuic¸a˜o de objetos em caixas
Muitos problemas de contagem podem ser resolvidos enumerando os meios
de colocar objetos em caixa, onde a ordem dos objetos colocados dentro
de cada caixa na˜o importa.
Os objetos e as caixas podem ser distingu¨´ıveis ou na˜o. O caso de caixas
indinstingu¨´ıveis e´ mais complicado e na˜o se conhece uma fo´rmula fechada
para este caso.
Objetos e caixas distingu¨´ıveis
Quantas formas existem de distribuir 5 cartas a quatro jogadores de um
baralho de 52 cartas?
O primeiro jogador pode receber 5 cartas em C (52, 5) meios diferentes
deixando 47 cartas no baralho. O segundo jogador tera´ C (47, 5) meios
diferentes de receber 5 cartas e, assim sucessivamente. Logo, existira´ um
total de C (52, 5)C (47, 5)C (42, 5)C (37, 5) = 52!5!5!5!5!32! .
E. Hoshino (Facom-UFMS) Contagem junho de 2015 38 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Distribuic¸a˜o de objetos em caixas (cont.)
Teorema
O nu´mero de meios de distribuir n objetos distingu¨´ıveis em k caixas
distingu¨´ıveis de modo que n1 objetos sa˜o colocados na caixa i ,
i = 1, . . . , k e´
n!
n1!n2! . . . nk !(n − nk)!
.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 39 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Distribuic¸a˜o de objetos em caixas (cont.)
Objetos indistingu¨´ıveis e caixas distingu¨´ıveis
Quantas formas existem de distribuir 10 bolas indistingu¨´ıveis em 8 caixas
distingu¨´ıveis?
Equivale ao problema de contar o nu´mero de 10-combinac¸o˜es de um
conjunto com 8 elementos quando repetic¸a˜o e´ permitida. Logo, existem
C (8 + 10− 1, 10) = C (17, 10) = 17!10!7! = 19448 meios.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 40 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Distribuic¸a˜o de objetos em caixas (cont.)
Objetos distingu¨´ıveis e caixas indistingu¨´ıveis
Quantas formas existem de alocar 4 funciona´rios em 3 salas indistingu¨´ıveis,
quando cada sala pode ter qualquer quantidade de funciona´rios?
Sejam A,B,C e D os quatro funciona´rios. A distribuic¸a˜o deles nas salas pode ser
representada pela partic¸a˜o de A,B,C e D em subconjuntos disjuntos. Por
exemplo, existe um u´nico meio de distribuir os quatros funciona´rios em uma
mesma sala, representado por {{A,B,C ,D}} enquanto que colocar treˆs deles em
uma sala e o outro em uma sala separada equivale a {{A,B,C}, {D}},
{{A,B,D}, {C}}, {{A,C ,D}, {B}} e {{B,C ,D}, {A}}.
Colocando dois deles em uma sala e os outros dois em outra equivale a
{{A,B}, {C ,D}}, {{A,C}, {B,D}} e {{A,D}, {B,C}}.
Finalmente, como u´ltima opc¸a˜o podemos colocar dois deles em uma sala e cada
um dos outros em salas diferentes: {{A,B}, {C}, {D}}, {{A,C}, {B}, {D}},
{{A,D}, {B}, {C}}, {{B,C}, {A}, {D}}, {{B,D}, {A}, {C}} e
{{C ,D}, {A}, {B}}.
Logo, existem 14 meios diferentes.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 41 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Distribuic¸a˜o de objetos em caixas (cont.)
Teorema
Denote por S(n, j) o nu´mero de meios de distribuir n objetos distingu¨´ıveis
em j caixas indistingu¨´ıveis de modo que nenhuma caixa fique vazia. Logo,
o nu´mero de meios de distribuir n objetos distingu¨´ıveis em k caixas
indistingu¨´ıveis e´
∑k
j=1 S(n, j).
No exemplo anterior, temos S(4, 1) + S(4, 2) + S(4, 3) = 1 + 7 + 6 = 14
meios diferentes.
Pode-se mostrar que S(n, j) = 1
j!
∑j−1
i=0(−1)
i
(
j
i
)
(j − i)n.
Mas, na˜o existe uma fo´rmula fechada para S(n, j).
E. Hoshino (Facom-UFMS) Contagem junho de 2015 42 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Distribuic¸a˜o de objetos em caixas (cont.)
Objetos indistingu¨´ıveis e caixas indistingu¨´ıveis
Quantas formas existem de distribuir 6 co´pias de um mesmo livro em 4
caixas ideˆnticas, onde na˜o ha´ limite no nu´mero de livros que uma caixa
pode comportar?
Vamos representar um meio de distribuir os livros por uma sequ¨eˆncia de nu´meros
ordenados, onde cada nu´mero indica o total de livros colocados em uma caixa.
Enumerando todos eles, vemos que existe um total de 9 meios diferentes:
6 2, 2, 2
5, 1 2, 2, 1, 1
4, 2
4, 1, 1
3, 3
3, 2, 1
3, 1, 1, 1
E. Hoshino (Facom-UFMS) Contagem junho de 2015 43 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Distribuic¸a˜o de objetos em caixas (cont.)
Observac¸a˜o
Distribuir n objetos indistingu¨´ıveis em k caixas indistingu¨´ıveis equivale a
escrever n como a soma de no ma´ximo k inteiros positivos em ordem na˜o
crescente. Se a1 + a2 + . . .+ aj = n com j ≤ k e ai inteiros positivos,
dizemos que a1, a2, . . . , aj e´ uma partic¸a˜o de n em j inteiros positivos.
Denote por pk(n) o nu´mero de partic¸o˜es de n em no ma´ximo k inteiros
positivos enta˜o existem pk(n) meios de distribuir n objetos indistingu¨´ıveis
em k caixas indistingu¨´ıveis.
Na˜o existe uma fo´rmula fechada e simples para pk(n).
E. Hoshino (Facom-UFMS) Contagem junho de 2015 44 / 63
Permutac¸a˜o e combinac¸a˜o Permutac¸o˜es e Combinac¸o˜es Generalizadas
Exerc´ıcios
1 Quantas formas existem de alocar 3 trabalhos a 5 funciona´rios se a
um funciona´rio pode ser alocado mais de um trabalho?
2 Quantas soluc¸o˜es existem para a equac¸a˜o x1+ x2+ x3+ x4+ x5 = 21,
onde xi , i = 1, . . . , 5, e´ um inteiro na˜o negativo tal que x1 ≥ 1?
3 Quantas cadeias de 10 d´ıgitos terna´rios (0,1 e 2) existem que conte´mexatamente dois 0s, treˆs 1s e cinco 2s?
4 Quantas palavras diferentes podem ser constru´ıdas das letras em
“ABRACADABRA” usando-se todas as letras?
5 Se existem 10 questo˜es em uma prova, de quantas formas diferentes
pode-se associar pontos a`s questo˜es de modo que a soma dos pontos
seja 100 e cada questa˜o tenha pelo menos 5 pontos?
6 De quantos modos n livros podem ser colocados em k estantes
dintingu¨´ıveis se:
1 os livros sa˜o co´pias indistingu¨´ıveis de um mesmo livro?
2 os livros sa˜o distintos e as posic¸o˜es deles nas estantes importa?
7 De quantos modos podemos colocar 8 DVDs ideˆnticos em 5 caixas
indistingu¨´ıveis de modo que cada caixa contenha pelo menos um
DVD?E. Hoshino (Facom-UFMS) Contagem junho de 2015 45 / 63
Coeficientes Binomiais
Coeficientes binomiais
Poteˆncia de expressa˜o binomial
Uma expressa˜o binominal e´ a soma de dois termos tal como x + y . Uma
poteˆncia de uma expressa˜o binomial e´ da forma (x + y)n.
Coeficiente binomial
O nu´mero
(
n
r
)
e´ chamado coeficiente binomial pois aparece como
coeficiente na expansa˜o de uma poteˆncia de uma expressa˜o binomial.
Teorema Binomial
Considere x e y varia´veis e n um inteiro na˜o-negativo. Enta˜o
(x + y)n =
∑n
j=0
(
n
j
)
xn−jy j
=
(
n
0
)
xn +
(
n
1
)
xn−1y +
(
n
2
)
xn−2y2 + . . .+
(
n
n−1
)
xyn−1 +
(
n
n
)
yn.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 46 / 63
Coeficientes Binomiais
Corola´rio 1
Seja n um inteiro na˜o-negativo. Enta˜o
n∑
k=0
(
n
k
)
= 2n.
Prova:
Usando o Teorema Binomial com x = 1 e y = 1 temos que
2n = (1 + 1)n =
n∑
k=0
(
n
k
)
1k1n−k =
n∑
k=0
(
n
k
)
.
Prova combinatorial:
Um conjunto com n elementos tem um total de 2n subconjuntos diferentes. Cada
subconjunto tem 0, 1, 2, . . . , ou n elementos. Como existem
(
n
0
)
subconjuntos
com zero elementos,
(
n
1
)
subconjuntos com um elemento, . . . e
(
n
n
)
com n
elementos, segue que existem
∑n
k=0
(
n
k
)
subconjuntos de um conjunto com n
elementos.E. Hoshino (Facom-UFMS) Contagem junho de 2015 47 / 63
Coeficientes Binomiais
Corola´rio 2
Seja n um inteiro na˜o-negativo, enta˜o
n∑
k=0
(−1)k
(
n
k
)
= 0.
Prova:
Usando o Teorema Binomial com x = −1 e y = 1 temos
0 = 0n = ((−1) + 1)n =
n∑
k=0
(
n
k
)
(−1)k1n−k =
n∑
k=0
(
n
k
)
(−1)k .
O corola´rio 2 implica que
(
n
0
)
+
(
n
2
)
+
(
n
4
)
+ . . . =
(
n
1
)
+
(
n
3
)
+
(
n
5
)
+ . . . .
E. Hoshino (Facom-UFMS) Contagem junho de 2015 48 / 63
Coeficientes Binomiais
Identidade de Pascal
Teorema da Identidade de Pascal
Sejam n e k inteiros positivos com n ≥ k . Enta˜o
(
n + 1
k
)
=
(
n
k − 1
)
+
(
n
k
)
.
Prova:
Seja T um conjunto com n+ 1 elementos. Considere a um elemento de T
e S = T − {a}. Note que existem
(
n+1
k
)
subconjuntos de T contendo k
elementos. Cada um destes subconjuntos conte´m ou na˜o o elemento a.
Como existem
(
n
k−1
)
subconjuntos de S contendo k − 1 elementos,
existem
(
n
k−1
)
subconjuntos de k elementos de T que conte´m a. Como
existem
(
n
k
)
subconjuntos de k elementos de S , existem
(
n
k
)
subconjuntos
de k elementos de T que na˜o conte´m a.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 49 / 63
Coeficientes Binomiais
Triaˆngulo de Pascal
Triaˆngulo de Pascal
E´ um arranjo dos coeficientes binomiais em um triaˆngulo em que a n-e´sima
linha do triaˆngulo consiste dos coeficientes de
(
n
k
)
, k = 0, 1, 2, 3, . . . , n.
Propriedade
A disposic¸a˜o dos coeficientes no triaˆngulo permite, usando a identidade de
Pascal, obter facilmente o coeficiente de cada elemento como soma de
dois elementos da linha anterior, como ilustrado abaixo.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 50 / 63
Coeficientes Binomiais
Exerc´ıcios
1 Desenvolva o binoˆmio (x + 2)5.
2 Seja n um inteiro na˜o-negativo. Use o Teorema Binomial para provar
que
n∑
k=0
2k
(
n
k
)
= 3n.
3 Prove a Identidade de Pascal usando a fo´rmula para
(
n
k
)
.
4 Prove o Teorema binomial usando induc¸a˜o matema´tica.
5 Mostre que um conjunto na˜o vazio tem o mesmo nu´mero de
subconjuntos com nu´mero ı´mpar de elementos que aqueles com
nu´mero par de elementos.
6 Determine uma fo´rmula envolvendo coeficientes binomiais para o
n-e´simo termo de uma sequ¨eˆncia se os termos iniciais dela sa˜o
listados abaixo. Dica: use o triaˆngulo de Pascal.
1 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, . . . .
2 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, . . . .
E. Hoshino (Facom-UFMS) Contagem junho de 2015 51 / 63
Relac¸o˜es de Recorreˆncia
Relac¸a˜o de recorreˆncia
Uma relac¸a˜o de recorreˆncia para uma sequ¨eˆncia {an} e´ uma equac¸a˜o que
expressa um termo an em func¸a˜o dos termos anteriores a ele na sequ¨eˆncia,
para todo n ≥ n0, sendo n0 um inteiro na˜o-negativo.
Exemplo 1
an = 2an−1 + 1, para todo n ≥ 1.
Soluc¸a˜o de uma relac¸a˜o de recorreˆncia
Uma sequ¨eˆncia e´ chamada soluc¸a˜o de uma relac¸a˜o de recorreˆncia se seus
termos satisfazem a relac¸a˜o de recorreˆncia.
A sequeˆncia {an} com an = 2
n − 1 e n ≥ 0 e´ uma soluc¸a˜o para a relac¸a˜o
de recorreˆncia do Exemplo 1.
Vejamos: a0 = 0, a1 = 1 = 2 ∗ a0 − 1, a2 = 3 = 2 ∗ a1 − 1,
a3 = 7 = 2 ∗ a2 − 1, . . ..
E. Hoshino (Facom-UFMS) Contagem junho de 2015 52 / 63
Relac¸o˜es de Recorreˆncia
Exemplo 2
Determine quais das sequeˆncias {an} abaixo sa˜o soluc¸o˜es para a relac¸a˜o de
recorreˆncia an = 2an−1 − an−2, para n ≥ 2:
1 an = 3n, n ≥ 0;
2 an = 2
n, n ≥ 0;
3 an = 5, n ≥ 0.
Resposta:
1 Como an−1 = 3n − 3 e an−2 = 3n − 6, segue que
2an−1 − an−2 = 2(3n − 3)− (3n − 6) = 3n. Portanto, a sequeˆncia
an = 3n e´ uma soluc¸a˜o para a relac¸a˜o de recorreˆncia dada.
2 Note que a0 = 1, a1 = 2 e a2 = 4. Logo,
2a1 − a0 = 2(2) − 1 = 3 6= a2, logo, an = 2
n na˜o e´ soluc¸a˜o.
3 Como an = 5, para todo n, temos que
2an−1 − an−2= 2(5) − 5 = 5 = an, logo, an = 5 tambe´m e´ uma
soluc¸a˜o.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 53 / 63
Relac¸o˜es de Recorreˆncia
Podem existir va´rias soluc¸o˜es para uma mesma relac¸a˜o de recorreˆncia!
Condic¸a˜o inicial
Especifica os termos anteriores ao n0−e´simo termo, onde a relac¸a˜o de
recorreˆncia toma efeito.
A relac¸a˜o de recorreˆncia do exemplo 2 esta´ definida para n ≥ 2:
an = 2an−1 − an−2
Neste caso, n0 = 2. Logo, as condic¸o˜es iniciais devem especificar a0 e a1.
Se a0 = 3 e a1 = 5, a soluc¸a˜o para relac¸a˜o de recorreˆncia e´
{3, 5, 7, 9, 11, 13, 15, . . .}, ou seja, an = 2n + 1, n ≥ 0.
Por outro lado, se a0 = 5 e a1 = 5, teremos que a soluc¸a˜o e´ an = 5, n ≥ 0.
A relac¸a˜o de recorreˆncia junto com a condic¸a˜o inicial determinam
unicamente uma sequ¨eˆncia.
Qualquer termo da sequ¨eˆncia pode ser determinada da condic¸a˜o inicial eE. Hoshino (Facom-UFMS) Contagem junho de 2015 54 / 63
Relac¸o˜es de Recorreˆncia
Exemplo 3
Suponha que uma pessoa deposita R$10.000, 00 em um banco e ganha
11% ao ano com investimentos. Qual sera´ o montante apo´s 30 anos?
Considere Pn o montante na conta depois de n anos. Logo,
Pn = Pn−1 + 0.11 ∗ Pn−1. Ou seja, a relac¸a˜o de recorreˆncia que representa
o montante apo´s n anos e´ Pn = (1.11) ∗ Pn−1. A condic¸a˜o inicial e´ que
P0 = 10.000, 00.
Como calcular P30? P30 = (1.11) ∗ P29, por sua vez, P29 = (1.11) ∗ P28,
assim sucessivamente.
No entanto, note que P1 = (1.11) ∗ P0, P2 = (1, 11) ∗ P1 = (1, 11)
2P0,
assim por diante. Logo, Pn = (1, 11)
n ∗ P0.
Podemos usar induc¸a˜o matema´tica para provar isso!
Logo, como P0 = 10.000, 00 segue que
P30 = (1, 11)
3010.000,00 = R$228.922, 97.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 55 / 63
Relac¸o˜es de Recorreˆncia
Exemplo 4
Leonardo Pisano (Fibonacci) postou o seguinte problema: Um par de
coelhos (um de cada sexo) e´ colocado em uma ilha. Sabendo que coelhos
na˜o se acasalam ate´ 2 meses de vida e que depois deste per´ıodo, cada par
reproduz um par de coelhos a cada meˆs, encontre uma relac¸a˜o de
recorreˆncia para o nu´mero de pares de coelhos na ilha apo´s n meses
(assumindo que coelhos na˜o morrem).
Considere fn o nu´mero de pares de coelhos depois de n meses. Note que
f1 = 1 e f2 = 1, uma vez que coelhos jovens na˜o se acasalam. Ja´ f3 = 2.
Para determinar fn basta verificar que o nu´mero de pares de coelhos em
um meˆs e´ igual ao nu´mero de pares de coelhos no meˆs anterior (fn−1) mais
o nu´mero de novos pares de coelhos jovens, que e´ igual a fn−2, uma vez
que cada novo coelho e´ filho de um par de coelhos adultos (que teˆm mais
de dois meses de vida).
Portanto, fn = fn−1 + fn−2.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 56 / 63
Relac¸o˜es de Recorreˆncia
Exemplo 5
Quantas palavras bina´rias de comprimento n que na˜o conteˆm dois 0’s
consecutivos?
A ideia e´ encontrar uma relac¸a˜o de recorreˆncia e as condic¸o˜es iniciais para
o nu´mero de palavras bina´rias de comprimento n que na˜o teˆm dois 0’s
consecutivos e, posteriormente, encontrar uma soluc¸a˜o para a relac¸a˜o de
recorreˆncia.
Observe que as palavras bina´rias que na˜o teˆm dois 0’s consecutivos podem
ser divididas em dois grupos: (a) as que terminam com 1 e (b) as que
terminam com 0, como apresentado na Figura 1.
Figura 1: Palavras bina´rias de n bits que na˜o conteˆm dois 0’s consecutivos.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 57 / 63
Relac¸o˜es de Recorreˆncia
Exemplo 5
Quantas palavras bina´rias de comprimento n que na˜o conteˆm dois 0’s
consecutivos? (cont.)
Seja an o nu´mero de cadeias de bits de comprimento n que na˜o teˆm dois
0’s consecutivos.
Portanto, pela regra da soma, an = total de palavras do caso (a) + total
de palavras do caso (b).
As palavras do caso (a) sa˜o obtidas das palavras de n− 1 bits que na˜o teˆm
dois 0s consecutivos seguidas por um 1. Logo, temos que existem
exatamente an−1 destas palavras.
Por outro lado, as palavras do caso (b) so´ podem ser obtidas das cadeias
de n− 2 bits seguidas por um 10. Logo, existem an−2 delas.
Portanto, an = an−1 + an−2.
Condic¸o˜es iniciais sa˜o a1 = 2 e a2 = 3.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 58 / 63
Relac¸o˜es de Recorreˆncia
Exemplo 6
O problema da Torre de Hanoi consiste de treˆs pinos montados sobre um
tabuleiro junto com va´rios discos de tamanhos diferentes. Inicialmente os
discos esta˜o colocados no pino 1 em ordem de tamanho (com o maior na
base). A regra do jogo permite transferir discos um por vez de um pino a
outro desde que um disco na˜o seja colocado em cima de um disco menor.
O objetivo do jogo e´ transferir todos os discos do pino 1 para o pino 2.
Seja Hn o nu´mero de movimentos necessa´rios para resolver o problema da
Torre de Hanoi com n discos. Encontre uma relac¸a˜o de recorreˆncia para a
sequ¨eˆncia {Hn}.
Uma soluc¸a˜o pode ser obtida transferindo-se os n − 1 discos menores do
pino 1 para o pino 3 usando as regras do jogo e, portanto, fazendo Hn−1
movimentos. Posteriormente, o disco maior e´ transferido do pino 1 para o
pino 2 e, enta˜o, os n− 1 discos do pino 3 sa˜o transferidos para o pino 2
usando Hn−1 movimentos.
Logo, Hn = 2Hn−1 + 1.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 59 / 63
Relac¸o˜es de Recorreˆncia
Exemplo 6 (cont.)
Encontre a soluc¸a˜o para a relac¸a˜o de recorreˆncia da Torre de Hanoi se a
condic¸a˜o inicial e´ H1 = 1.
Hn = 2Hn−1 + 1
= 2(2Hn−2 + 1) + 1 = 2
2Hn−2 + 2 + 1
= 22(2Hn−3 + 1) + 2 + 1 = 2
3Hn−3 + 2
2 + 21 + 20
...
= 2n−1Hn−n−1 + 2
n−2 + 2n−3 + . . . + 20 = 2n−1 + 2n−2 + . . . + 20
= 2n − 1.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 60 / 63
Relac¸o˜es de Recorreˆncia
Exemplo 7
Em um sistema de computador uma palavra de d´ıgitos decimais e´ va´lida se
conter um nu´mero par de d´ıgitos 0. Seja an o nu´mero de palavras de n
d´ıgitos que e´ va´lida. Encontre uma relac¸a˜o de recorreˆncia para an.
Primeiro, note que a1 = 9.
Uma palavra de n d´ıgitos pode ser obtida de duas maneiras diferentes.
Na primeira maneira, podemos acrescentar um d´ıgito diferente de 0 em
uma palavra de n − 1 d´ıgitos que e´ va´lida, o que da´ um total de 9an−1
palavras.
Na segunda forma, podemos acrescentar um d´ıgito 0 em uma palavra de
n − 1 d´ıgitos que na˜o e´ va´lida. Como existem 10n−1 palavras de n− 1
d´ıgitos e an−1 deles sa˜o va´lidos, existem 10
n−1 − an−1 destas palavras.
Logo, an = 9an−1 + 10
n−1 − an−1 = 8an−1 + 10
n−1.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 61 / 63
Relac¸o˜es de Recorreˆncia
Exerc´ıcios
1 Verifique se cada sequ¨eˆncia {an}, definida para todo natural n, e´
soluc¸a˜o para a relac¸a˜o de recorreˆncia an = −3an−1 + 4an−2 definida
para n ≥ 2:
1 an = 0;
2 an = 1;
3 an = (−4)
n;
4 an = 2(−4)
n + 3.
2 Encontre a soluc¸a˜o para cada relac¸a˜o de recorreˆncia com a condic¸a˜o
inicial dada. Use o me´todo iterativo usado no problema da Torre de
Hanoi.
1 an = −an−1, a0 = 5;
2 an = an−1 + 3, a0 = 1;
3 an = an−1 − n, a0 = 4;
4 an = 2an−1 − 3, a0 = −1;
5 an = (n + 1)an−1, a0 = 2;
6 an = 2nan−1, a0 = 3;
7 an = −an−1 + n − 1, a0 = 7.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 62 / 63
Relac¸o˜es de Recorreˆncia
Exerc´ıcios
1 Suponha que o nu´mero de bacte´rias em uma coloˆnia triplica a cada
hora. Encontre a relac¸a˜o de recorreˆncia para o nu´mero de bacte´rias
depois de n horas se inicialmente havia apenas 100 delas?
2 Encontre a relac¸a˜o de recorreˆncia para o nu´mero de permutac¸o˜es de
um conjunto com n elementos.
3 Encontre uma relac¸a˜o de recorreˆncia para o nu´mero de cadeias de n
bits contendo treˆs 1’s consecutivos.
4 Mostre que os nu´meros de Fibonacci satisfaz a relac¸a˜o de recorreˆncia
fn = 5fn−4 + 3fn−5, para n = 5, 6, 7, . . . junto com a condic¸a˜o inicial
f0 = 0, f1 = 1, f2 = 1, f3 = 2 e f4 = 3.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 63 / 63
	Contagem
	Princípios Básicos de Contagem
	Princípio da Inclusão-Exclusão
	Princípio da Casa dos Pombos
	Permutação e combinação
	Permutações
	Combinação
	Permutações e Combinações Generalizadas
	Coeficientes Binomiais
	Relações de Recorrência