Análise Combinatória
Rodrigo [email protected]
Instituto de InformáticaUniversidade Federal do Rio Grande do SulPorto Alegre, Brasilhttp://www.inf.ufrgs.br
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
2/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
3/168
Problemas de contagem
Contagem: determinar o número de elementos de uma determinada coleçãosem precisar necessariamente enumerá-la.
Exemplos de problemas que envolvem contagem:• Quantos números inteiros pares existem entre 0 e 100? Considere os limites
na contagem.• Você precisa construir todas as funções totais f : A → A, onde
A = {1, 2, . . . , 8}. Quanto de memória você precisa alocar?
A seguir, veremos alguns princípios de contagem a partir dos quais as fórmulaspara contagem de diversos tipos de objetos matemáticos serão derivadas.
4/168
Princípio aditivo
Sejam A e B conjuntos finitos.
Princípio aditivo: Se A ∩ B = ∅, então |A ∪ B| = |A| + |B|.
Aplicável quando escolhemos elementos do conjunto A OU do conjunto B,exclusivamente.
Exemplo: Suponha que tenham entrado em cartaz 3 filmes e 2 peças de teatroe que Carlos tenha dinheiro para assistir a apenas 1 evento. Quantos são osprogramas que Carlos pode fazer no sábado?
5/168
Princípio multiplicativo
Sejam A e B conjuntos finitos.
Princípio multiplicativo: |A × B| = |A| × |B|.
Aplicável quando escolhemos elementos do conjunto A E do conjunto B,simultaneamente.
Exemplo: Suponha que tenham entrado em cartaz 3 filmes e 2 peças deteatro. Se Carlos tem dinheiro para assistir a um filme e a uma peça de teatro,quantos programas ele pode fazer no sábado?
6/168
Princípio aditivo e multiplicativo: exercícios
Exercício:
1. Dados 5 livros diferentes de matemática, 7 livros diferentes de física, 10livros diferentes de química, de quantas maneiras podemos escolher 2 livrosde forma que eles não sejam da mesma matéria?
2. De quantas maneiras 2 pessoas podem estacionar seus carros numagaragem com 6 vagas?
3. Quantos números naturais de três algarismos distintos (na base 10)existem?
4. De quantas maneiras podemos escolher 1 consoante e 1 vogal de umalfabeto formado por 18 consoantes e 5 vogais?
5. De quantas maneiras podemos escolher 2 consoantes diferentes dentre umconjunto de 8 consoantes?
6. Quantas diagonais possui um polígono regular de n lados?
7/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
8/168
Permutações
Sejam a1, a2, . . . , an elementos distintos de uma coleção A.
Definição: uma permutação de elementos de A é uma n-tupla
(b1, b2, . . . , bn)
tal que exista uma bijeção f : {1, . . . , n} → {1, . . . , n} onde ai = bf(i)
Uma permutação representa um ordenamento de todos os elementos dacoleção A.
Nota: é importante para contagem de permutações que todos os elementos dacoleção A sejam distintos.
9/168
Permutações: contagem
Exemplo: todas as permutações do conjunto {a,b,c}:
(a,b,c) (a,c,b) (b,a,c) (b,c,a) (c,a,b) (c,b,a)
Pergunta: quantas permutações distintas existem para sequências com nelementos?
Resposta: n × (n – 1) × (n – 2) × . . . × 1 = n!
Definição: Pn representa o número de permutações de um conjunto com nelementos.
Pn = n!
10/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
11/168
Arranjos
Definição: um arranjo é uma tupla de k elementos distintos retirados de umacoleção com n elementos.
Exemplo: todos os arranjos de tamanho 2 do conjunto {1, 2, 3}.
(1,2) (2,3)(1,3) (3,1)(2,1) (3,2)
Nota: note que ordem é importante: (1,2) 6= (2,1)
12/168
Arranjos: contagem
Definição: Akn representa o número de arranjos de tamanho k
cujos elementos são extraídos de uma coleção de tamanho n.
Akn =
k︷ ︸︸ ︷n × (n – 1) × · · · × (n – k + 1)
= n!(n – k)!
Nota: perceba que Ann = Pn = n!
13/168
Arranjos: exercícios
Exercício:
1. Quantas são as palavras de 4 letras que não repetem letras, considerando oalfabeto convencional (de A a Z, 26 letras)?
2. Uma empresa precisa preencher 8 vagas de trabalho distintas. Houve 5pessoas interessadas em ocupar um cargo qualquer dentre os 8. De quantasformas distintas podemos alocar as pessoas interessadas para vagas nessaempresa?
3. Quantas funções injetoras existem do conjunto {a, b, c} para o conjunto{1, 2, 3, 4, 5, 6, 7, 8}?
14/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
15/168
Combinações
Definição: uma combinação é um subconjunto de k elementos tomados deuma coleção de n elementos distintos.
Exemplo: seja A = {1, 2, 3, 4, 5}.
Todas as combinações de 3 elementos tirados de A:
{3,4,5} {2,4,5}{2,3,5} {2,3,4}{1,4,5} {1,3,5}{1,3,4} {1,2,5}{1,2,4} {1,2,3}
Nota: combinações não são ordenadas! {1,4,2} = {2,4,1}
16/168
Combinações: contagem
Considere k, n ∈ {0, 1, 2, . . .}.
Definição: Ckn representa o número de combinações de tamanho k extraídas de
uma coleção de n elementos distintos.
Ckn = 0 quando k > n
Ckn = n!
(n – k)! k! quando k ≤ n
Outra notação para contagem de combinações :
Ckn =
(nk
)(lê-se “n escolhe k”)
Nota: atenção com a ordem dos índices!
17/168
Combinações: exercícios
Exercício:
1. De quantas maneiras podemos arrumar em fila 5 sinais ‘-’ e 7 sinais ‘|’ ?2. Considere uma grade de 5 linhas e 7 colunas. Considere que estamos no
cantos superior esquerdo da grade. De quantas formas distintas podemosalcançar o canto inferior direito, supondo que somente movimentos parabaixo e para a direita são possíveis?
3. Em um jogo do tipo loteria, existem 25 números ao total, dos quais 5 sãosorteados semanalmente. Uma aposta consiste da escolha de 5 números, eo jogador ganha somente se acertar exatamente os números sorteados.Qual a chance de alguém ser sorteado se fizer quatro apostas distintas?
18/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
19/168
Coeficientes de potências de binômios
Observe os coeficientes das seguintes potências de um binômio (a + b):
(a + b)0 = 1 × a0b0
(a + b)1 = 1 × a0b1 + 1 × a1b0
(a + b)2 = 1 × a0b2 + 2 × a1b1 + 1 × a2b0
(a + b)3 = 1 × a0b3 + 3 × a1b2 + 3 × a2b1 + 1 × a3b0
......
...
Notamos que o coeficiente de um termo aibj, na expansão de umamultiplicação (a + b)n corresponde à
(ni).
Intuição: o coeficiente na frente de aibj conta o número de formas distintasde enumerar i letras a e j letras b, pois é obtido do agrupamento de todas astuplas de tamanho (i + j) com exatos i a’s e j b’s.
20/168
Teorema binomial
Teorema: para n ∈ N temos:
(a + b)n =n∑
i=0
(ni
)aibn–i
Nota: esse teorema relaciona potências de polinômios com contagem decombinações. Tal relação será melhor explorada quando estudarmos funçõesgeradoras.
Demonstração: por indução sobre n ∈ N.
21/168
Teorema binomial: comentário sobre 00
Nota: a fim de garantir que o teorema binomial seja válido para todos os valores reaisde a e b, vamos assumir que
00 = 1Contudo, essa identidade é controversa: em outras áreas da matemática (comocálculo) 00 é considerada uma forma indefinida.
Para quem se interessar, há boas explicações e referências sobre esse tópico nos linksabaixo (em inglês)
• http:
//www.askamathematician.com/2010/12/q-what-does-00-zero-raised-to-the-zeroth-power-equal-why-do-mathematicians-and-high-school-teachers-disagree/
• http://mathforum.org/dr.math/faq/faq.0.to.0.power.html
• http://math.stackexchange.com/questions/11150/zero-to-the-zero-power-is-00-1
22/168
Teorema binomial: consequências
Corolário: podemos obter o resultado de(n
i)
“lendo” o coeficiente de xi naexpansão de (x + 1)n
(x + 1)n =n∑
i=0
(ni
)xi
23/168
Teorema binomial: consequências (2)
Corolário: o resultado da expressão(n0
)–(
n1
)+(
n2
)– · · · + (–1)n
(nn
)é sempre 0 (para n ≥ 1):
n∑i=0
(ni
)(–1)i = 0
24/168
Teorema binomial: exercícios
Exercício:
1. Calcular o quarto termo da expansão de (1 + x)8
2. Calcular o sexto termo da expansão de (x – 5y)10
25/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
26/168
Triângulo de Pascal
O triângulo de Pascal é uma matriz infinita onde cada elemento an,k corresponde aCk
n =(n
k)
n\k 0 1 2 3 4 5 6 7 · · ·0 11 1 12 1 2 13 1 3 3 14 1 4 6 4 15 1 5 10 10 5 16 1 6 15 20 15 6 17 1 7 21 35 35 21 7 1...
......
......
......
......
. . .
Obs: espaços em branco contêm o valor 0.
27/168
Propriedades de combinações
Os números construídos pela expressão(n
k)
possuem diversas identidades, quepodem ser visualizadas sobre o triângulo de Pascal.
1. Combinaçãocomplementar:
(nk
)=(
nn – k
)
n\k 0 1 2 3 4 5 · · ·0 11 1 12 1 2 13 1 3 3 14 1 4 6 4 15 1 5 10 10 5 1...
......
......
......
. . .
28/168
Propriedades de combinações (2)
2. Relação de Stifel: (n + 1k + 1
)=(
nk + 1
)+(
nk
)
n\k 0 1 2 3 4 5 · · ·0 11 1 12 1 2 13 1 3 3 14 1 4 6 4 15 1 5 10 10 5 1...
......
......
......
. . .
29/168
Propriedades de combinações (3)
3. Soma horizontal:
n∑k=0
(nk
)= 2n
n\k 0 1 2 3 4 5 · · ·0 11 1 12 1 2 13 1 3 3 14 1 4 6 4 15 1 5 10 10 5 1...
......
......
......
. . .
30/168
Propriedades de combinações (4)
4. Soma vertical:
k+x∑n=k
(nk
)=(
k + x + 1k + 1
)
n\k 0 1 2 3 4 5 · · ·0 11 1 12 1 2 13 1 3 3 14 1 4 6 4 15 1 5 10 10 5 1...
......
......
......
. . .
31/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
32/168
Regra da subtração
Lembre que A \ B = {x | x ∈ A ∧ x /∈ B}.
Regra da subtração: Sejam A e B conjuntos finitos tal que B ⊆ A. Então
|A \ B| = |A| – |B|
Demonstração:
1. (A \ B) ∩ B = ∅
2. |(A \ B) ∩ B| = |∅|
3. |A \ B| + |B| – |(A \ B) ∪ B| = 0
4. |A \ B| + |B| – |A ∪ B| = 0
5. |A \ B| + |B| – |A| = 0 (pois B ⊆ A)
6. |A \ B| = |A| – |B|
33/168
Regra da subtração: exemplo
A regra da subtração é útil quando é mais fácil contar o complemento de umconjunto do que o conjunto em si.
Exemplo: Considere um baralho normal• quatro naipes: ♠, ♦, ♣, ♥• valores: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
Pergunta: Quantas mãos (conjuntos) de 5 cartas contém alguma figura (cartasde valor J, Q ou K)?
Resposta: A contagem direta é difícil, porém podemos calcular o número de mãossem figuras e subtrair do total de mãos existentes:(
525
)–(52 – 12
5
)= 2598960 – 658008 = 1940952
34/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
35/168
Regra do quociente
Seja A um conjunto finito e seja R uma relação de equivalência sobre A ondecada classe de equivalência contém exatamente r elementos.
Denotemos A/R o conjunto de todas as classes de equivalência de R em A(subconjuntos maximais de elementos R-equivalentes em A).
Regra do quociente:|A/R| = |A|
r
36/168
Regra do quociente: exemplo
A regra do quociente é útil quando é possível caracterizar o objeto de interesseda contagem como uma classe de equivalência sobre elementos de outroconjunto (mais fácil de ser contado).
Exemplo: Considere A sendo o conjunto de todos os arranjos de tamanho kcontendo elementos do conjunto N, onde |N| = n.
Defina que dois arranjos (a1, a2, . . . , ak) e (b1, b2, . . . bk) são R-equivalentessss um for uma permutação do outro.
Note que cada classe de equivalência corresponde a uma k-combinação. Como|A| = n!
(n–k)! e cada classe de equivalência possui k! elementos,
|A/R| = |A|k! ⇔
(nk
)=
n!(n–k)!
k! = n!(n – k)!k!
37/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
38/168
Distribuição de elementos idênticos
Problema: contar de quantas formas podemos distribuir m elementos idênticos em rcaixas enumeradas x1, . . . , xr.
Variações:• cada caixa deve conter 1 ou mais elementos
• cada caixa deve conter 0 ou mais elementos
• quantidades mínimas distintas para as caixas
Equivale a contar soluções (em números naturais) da equação
x1 + . . . + xr = m
sujeito às restrições de cada caso.
39/168
Distribuição: solução em inteiros positivos
Variação 1: conte soluções em naturais para
x1 + . . . + xr = m
que não deixem nenhuma caixa vazia (xi > 0 para todo 1 ≤ i ≤ r)
Para realizar essa contagem, podemos considerar a inserção de r – 1 separadoresidênticos | entre pontos da representação unitária de m.
Exemplo: m = 5, r = 3.
•␣ • ␣ • ␣ • ␣• =⇒x1︷︸︸︷
•␣• |x2︷︸︸︷
•␣• |x3︷︸︸︷•
Solução:
Cr–1m–1 =
(m – 1r – 1
)
40/168
Distribuição: solução em inteiros positivos
Exercício:
Encontre o número de soluções em inteiros positivos da seguinte equação:
x1 + x2 + x3 + x4 = 11
41/168
Distribuição: solução em inteiros não-negativos
Variação 2: conte soluções em naturais para
x1 + . . . + xr = m
permitindo caixas vazias (xi ≥ 0 para todo 1 ≤ i ≤ r)
Para realizar essa contagem, podemos escolher posições para r – 1 símbolos | nastring composta de m+ (r – 1) símbolos | ou •.
Exemplo: m = 5, r = 4.
posição: 1 2 3 4 5 6 7 8símbolo • • | | • • | • ⇐⇒
{x1 = 2 x2 = 0x3 = 2 x4 = 1
Solução:
Cr–1m+r–1 =
(m+ r – 1
r – 1
)=(m+ r – 1
m
)
42/168
Distribuição: solução em inteiros não-negativos
Exercício:
Encontre o número de soluções em inteiros não-negativos da equação
x1 + x2 + x3 = 10
43/168
Distribuição: caixas com conteúdo mínimo
Variação 3: conte soluções em naturais para
x1 + . . . + xr = m
mantendo um número mínimo de elementos em certas caixas (xi ≥ ni para todo1 ≤ i ≤ r e ni fixos)
Exemplo: de quantas formas podemos distribuir 10 elementos idênticos em 3 caixasenumeradas, cada uma contendo no mínimo 2 elementos? (n1, n2, n3 = 2)
Equivale a remover do total de elementos a quantidade obrigatória em cada caixa, edistribuir os demais (verificando soluções em inteiros não-negativos).
Solução: particionamento em inteiros não-negativos da equação
x1 + . . . + xr = m –r∑
i=1ni
44/168
Distribuição: caixas com conteúdo mínimo
Exercício:
Encontrar o número de soluções em inteiros positivos maiores que 3 da equação
x1 + x2 + x3 = 17
Em outras palavras: determinar o número de soluções inteiras dex1 + x2 + x3 = 17, onde xi > 3 para i ∈ {1, 2, 3}.
45/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
46/168
Combinações com repetição
Seja A um conjunto finito, onde |A| = n.
Definição: uma k-combinação com (possível) repetição de A é um multiconjuntode tamanho k onde todos os elementos pertencem a A.
A contagem de k-combinações com repetição é equivalente a contar as soluçõesnão-negativas para a seguinte equação:
x1 + x2 + · · · + xn = k
Notação: denotamos por CRkn o número de k-combinações com repetição sobre um
conjunto A de tamanho n.
CRkn = Cn–1
k+n–1 =(k + n – 1n – 1
)=(k + n – 1
k
)
47/168
Combinações com repetição: exercícios
1. De quantos modos podemos comprar 4 refrigerantes em um bar que vende2 tipos de refrigerante?
2. De quantos modos diferentes podemos distribuir 10 bombons idênticos em4 caixas diferentes?
3. Dispondo de 4 cores diferentes, de quantas maneiras distintas podemospintar 5 objetos idênticos? (Cada objeto deve ser pintado com uma únicacor)
48/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
49/168
Arranjos com repetição
Seja A um conjunto finito, onde |A| = n.
Definição: um k-arranjo com (possível) repetição é uma k-tupla formadacom elementos de A.
Como temos n possibilidades para cada posição, certamente teremos nk tuplasdistintas.
k︷ ︸︸ ︷n × n × · · · × n = nk
Notação: denotamos ARkn o número de k-arranjos com repetição sobre um
conjunto A de tamanho n.ARk
n = nk
50/168
Arranjos com repetição: exercícios
1. Qual o total de placas de carro que podem ser construídas constando de 7símbolos, sendo os 3 primeiros contituídos por letras e os 4 últimos pordígitos?
2. Quantas funções totais existem entre os conjuntos A = {1, 2, 3} eB = {α, β, γ, δ}?
51/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
52/168
Permutações circulares
Pergunta: de quantas maneiras 4 crianças podem dar as mãos para brincar deroda?
A seguinte fórmula conta o número de permutações circulares a partir de umconjunto de tamanho n.
(PC)n = n!n = (n – 1)!
Resposta: no caso de 4 crianças, temos 3! = 6 formas distintas de formar umaroda.
53/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
54/168
Permutações com repetição
Pergunta: quantos anagramas existem para a palavra ABACATE ?
Note que há menos de 7! anagramas, pois algumas trocas de letras não gerampalavras distintas (primeira letra com a quinta, por exemplo).
Uma estratégia é distinguir as letras repetidas com índices:
A1 B A2 C A3 T E
Após, podemos definir uma relação de equivalência determinando que duas palavrassão equivalentes sss uma for obtida a partir da outra por uma permutação das letrasrepetidas.
No caso de ABACATE, há 3! formas de enumerar os A’s, o que leva a 6 palavras porclasse de equivalência. Pela regra do quociente o número de anagramas de abacate éigual a 7!
3! .
55/168
Permutações com repetição
Note que cada permutação com repetição consiste de uma forma de enumerar ummulticonjunto de tamanho n.
A seguinte fórmula conta o número de permutações com repetição de ummulticonjunto de tamanho n,
PR(n; r1, r2, . . . , rk) =(
nr1, r2, . . . , rk
)= n!
r1! × r2! × · · · × rk!
onde r1, r2, . . . , rk correspondem às repetições de cada uma das letras da palavra.
Nota: se k1 + k2 = n, então (n
k1, k2
)=(
nk1
)=(
nk2
)
56/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
57/168
Teorema multinomial
Considere a expansão de potências de trinômios.
Exemplo:
(a + b + c)n = ???
58/168
Teorema multinomial (2)
O que vimos para trinômios pode ser generalizado para multinômios.
Teorema:
(x1 + · · · + xm)n =∑
r1+···+rm=n
(n
r1, . . . , rm
)xr1
1 · · · xrmm
59/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
60/168
Princípio da inclusão e exclusão
Considere as seguintes contagens da união de conjuntos:
2 conjuntos:
|A ∪ B| = |A| + |B| – |A ∩ B|
3 conjuntos:
|A ∪ B ∪ C| = + |A| + |B| + |C|– |A ∩ B| – |A ∩ C| – |B ∩ C|+ |A ∩ B ∩ C|
61/168
Princípio da inclusão e exclusão (cont.)Princípio da inclusão e exclusão: O número de elementos da união de n conjuntosfinitos A1, . . . , An é dado por:
|A1 ∪ A2 ∪ . . . ∪ An| =
+∑
1≤i≤n
|Ai|
–∑
1≤i<j≤n
|Ai ∩ Aj|
+∑
1≤i<j<k≤n
|Ai ∩ Aj ∩ Ak|
–∑
1≤i<j<k<l≤n
|Ai ∩ Aj ∩ Ak ∩ Al|
...
(–1)n–1 |A1 ∩ A2 ∩ . . . ∩ An|
62/168
Princípio da inclusão e exclusão: exemplo
Pergunta: Quantas são as permutações das letras da palavras BRASIL em que o Bocupa o primeiro lugar, ou o R o segundo lugar, ou o A o terceiro lugar?
Podemos começar contando os seguintes conjuntos separadamente:
• PB = conjunto de permutações que mantém B na 1ł posição
• PR = conjunto de permutações que mantém R na 2ł posição
• PA = conjunto de permutações que mantém A na 3ł posição
A solução consiste de |PB ∪ PR ∪ PA|. Contudo, nesse cálculo não podemos aplicar oprincípio aditivo, pois PB, PR e PA não são disjuntos. Exemplo:
BLARSI ∈ PB e BLARSI ∈ PA
63/168
Princípio da inclusão e exclusão: exemplo (cont.)
Portanto, necessitamos do princípio da inclusão e exclusão, que diz:
|PB ∪ PR ∪ PA| = + |PB| + |PR| + |PA|– |PB ∩ PR| – |PB ∩ PA| – |PR ∩ PA|+ |PB ∩ PR ∩ PA|
Note que:• |PB| = |PR| = |PA| = 5!
• |PB ∩ PR| = |PB ∩ PA| = |PR ∩ PA| = 4!
• |PB ∩ PR ∩ PA| = 3!
Resposta: O número de permutações de BRASIL que mantém ou B, ou R ou A naposição original é
|PB ∪ PR ∪ PA| = 3 × 5! – 3 × 4! + 3! = 294
64/168
Princípio da inclusão e exclusão: exercícios
Exercício:
1. Quantos inteiros entre 1 e 3600, inclusive, são divisíveis por 3, 5 ou 7?2. Considere um baralho normal (quatro naipes, treze valores de Ás a K).
Quantas mãos (conjuntos) de 9 cartas contém 4 cartas do mesmo valor?
65/168
Contagem de funções sobrejetoras
Pergunta: Quantas funções sobrejetoras existem entre dois conjuntos finitos A e B?
Consideramos dois casos:• se |A| < |B|: 0 funções sobrejetoras
• se |A| ≥ |B|: vamos contar todas as funções cuja imagem é igual aocontradomínio.
Suponha |B| = n e B = {b1, b2, . . . , bn}.
Notação: Denotamos E1 o conjunto de todas as funções do tipo A → B que nãomapeiam nenhum elemento de A para b1 (ou seja, funções que “erram” b1).Definimos da mesma forma Ei para 1 ≤ i ≤ n.
66/168
Contagem de funções sobrejetoras (2)
As funções sobrejetoras são aquelas que não “erram” nenhum elemento docontradomínio. Portanto, pela regra da subtração:
|funções sobrejetoras| = |funções| - |funções que “erram” algum b ∈ B|
Ou seja:n|A| – |E1 ∪ E2 ∪ . . . ∪ En|
Por inclusão e exclusão:
= n|A| –(+ |E1| + |E2| + . . . + |En|– |E1 ∩ E2| – |E1 ∩ E3| – · · · – |En–1 ∩ En|+ |E1 ∩ E2 ∩ E3| + · · · + |En–2 ∩ En–1 ∩ En|...
(–1)n–1 |E1 ∩ E2 ∩ · · · ∩ En|)
67/168
Contagem de funções sobrejetoras (3)
Absorvendo a negação:
= n|A|
– |E1| – |E2| – . . . – |En|+ |E1 ∩ E2| + |E1 ∩ E3| + · · · + |En–1 ∩ En|– |E1 ∩ E2 ∩ E3| – · · · – |En–2 ∩ En–1 ∩ En|...
(–1)n |E1 ∩ E2 ∩ · · · ∩ En|
Cardinalidade das interseções:• |E1| = (n – 1)|A| (nro de funções do tipo A → (B – {b1}))
• |E1 ∩ E2| = (n – 2)|A| (nro de funções do tipo A → (B – {b1, b2}))
• e assim sucessivamente . . .Note também que |Eb1 | = |Eb2 | = · · · |Ebn |. O mesmo vale para as demaisinterseções, isto é os tamanhos dos conjuntos na mesma linha são iguais.
68/168
Contagem de funções sobrejetoras (4)
Número de termos por linha:• Interseções de 1 conjunto:
(n1)
• Interseções de 2 conjuntos:(n
2)
...
• Interseções de n conjuntos:(n
n)
Logo (lembrando que n = |B|):
= + (–1)0(n
0)(n – 0)|A|
+ (–1)1(n
1)(n – 1)|A|
+ (–1)2(n
2)(n – 2)|A|
...+ (–1)n
(nn)(n – n)|A|
Resposta: O número de funções sobrejetoras entre A e B é:
|B|∑i=0
(–1)i(|B|i
)(|B| – i)|A|
69/168
Função φ de Euler
Definição: A função φ de Euler associa o inteiro positivo n ao número de inteirospositivos menores que n e que são primos em relação a n.
Em outras palavras, φ(n) é a cardinalidade do conjunto{x | 1 ≤ x < n ∧ MDC(x, n) = 1}.
Teorema: (fórmula fechada para φ)
φ(m) = m(1 – 1
p1
)(1 – 1
p2
)· · ·(1 – 1
pr
)onde m = pα1
1 × pα22 × · · · × pαr
r é a decomposição de m em fatores primos.
Exercício:
1. Calcular φ(m) para m = 2100
70/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
71/168
Permutações caóticas
Definição: Permutações caóticas (ou desarranjos) são as permutações que nãodeixam nenhuma letra na sua posição original.
Teorema: o número de permutações caóticas de uma palavra sem letras repetidas detamanho n (denotado Dn) é dado pela seguinte fórmula:
Dn = n!(1 – 1
1! +12! –
13! + . . . + (–1)n 1
n!
)=
n∑i=0
(–1)i n!i!
Teorema: para todo inteiro n > 2, temos∣∣∣Dn – n!e
∣∣∣ < 12
Exercício:
1. De quantas formas distintas podemos realizar um sorteio de amigo secreto entre10 pessoas de forma que ninguém tire o próprio nome no sorteio?
72/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
73/168
Princípio dos escaninhos
Princípio dos escaninhos: Sejam n e k inteiros positivos onde n > k.Suponha a distribuição de n envelopes idênticos em k escaninhos.
Logo, haverá no mínimo um escaninho contendo dois ou mais envelopes.
Nota: também é conhecido como• princípio das gavetas de Dirichlet• princípio da casa dos pombos (pidgeonhole principle)
74/168
Princípio dos escaninhos: exemplos
Exemplo:
1. Dado um conjunto de 13 pessoas (ou mais), pelo menos duas aniversariamno mesmo mês.
2. Dado um conjunto de 32 pessoas (ou mais), pelo menos duas aniversariamno mesmo dia do mês.
3. Dado um conjunto de 367 pessoas (ou mais), pelo menos duasaniversariam no mesmo dia do ano.
75/168
Princípio dos escaninhos: caráter existencial
Pode-se notar que o princípio dos escaninhos é de natureza distinta dos demaisprincípios de contagem.
Ele essencialmente não conta elementos, nem especifica qual gavetaapresenta repetição. Ele simplemente garante a existência de tal gaveta.
Essa garantia de existência é tipicamente utilizada como fato auxiliar emprovas de propriedades mais interessantes.
Além disso, o princípio dos escaninhos ajuda a determinar quantidadesmínimas em certos parâmetros para a garantia de ocorrência de certos eventos.
76/168
Princípio dos escaninhos: exercícios
Exercício:
1. Em uma gaveta há 12 meias brancas e 12 meias pretas. Quantas meiasdevemos retirar ao acaso para termos certeza de obter um par de meias decores diferentes? E de mesma cor?
2. Mostre que em um conjunto de n pessoas há sempre duas pessoas queconhecem exatamente o mesmo número de outras pessoas do conjunto.Suponha que a relação “conhecer” é simétrica (se a conhece b então bconhece a) e irreflexiva (a não conhece a).
77/168
Princípio dos escaninhos: exemplo
Exemplo: Mostrar que na sequência infinita de números
a = 7, 77, 777, 7777, 77777, 777777, . . .
há ao menos um número que é múltiplo de 2003.
Demonstração: Vamos provar algo mais forte: que existe um múltiplo de 2003dentre os primeiros 2004 números de a.
Vamos chamar a1, a2, . . . , a2004 os 2004 primeiros elementos de a.
Para cada ai (1 ≤ i ≤ 2004), calculamos o resto da divisão inteirari = ai % 2003.
Note que o valor de cada ri varia de 0 a 2002, e existem 2004 restos.
78/168
Princípio dos escaninhos: exemplo (2)
Logo, pelo princípio dos escaninhos, há dois índices distintos i e j entre 1 e2004 tal que ri = rj.
Portanto, há valores na sequência a com o mesmo resto na divisão por 2003.Vamos chamá-los ai e aj, considerando i < j.
ai = ki ∗ 2003 + riaj = kj ∗ 2003 + rj
Considere agora a subtração aj – ai:
aj – ai = (kj ∗ 2003 + rj) – (ki ∗ 2003 + ri) = (kj – ki) ∗ 2003
O que garante que aj – ai é múltiplo de 2003.
79/168
Princípio dos escaninhos: exemplo (3)
Note que, se observarmos a forma de aj – ai, temos o seguinte:
aj =j︷ ︸︸ ︷
77 · · · 777777 · · · 7
–ai = –i︷ ︸︸ ︷
77777 · · · 7
aj – ai =aj–i︷ ︸︸ ︷
77 · · · 7 ×10i︷ ︸︸ ︷
100000 · · · 0
Portanto, sabemos que aj–i × 10i é múltiplo de 2003.
Também sabemos que 2003 é primo em relação a 10i.
Portanto, só resta que aj–i é múltiplo de 2003. Note também que1 ≤ (j – i) ≤ 2004.
80/168
Princípio dos escaninhos generalizado
Princípio dos escaninhos generalizado: Se k escaninhos são ocupados porx × k + 1 envelopes, então ao menos um escaninho deverá conter pelo menosx + 1 envelopes.
Reformulando:
Teorema: Se colocarmos n envelopes em k escaninhos , então pelo menos umescaninho deverá conter no mínimo⌊
n – 1k
⌋+ 1
envelopes.
81/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
82/168
Princípios de contagem: revisão
Princípio aditivo:
se A ∩ B = ∅ então|A ∪ B| = |A| + |B|
Princípio multiplicativo:
|A × B| = |A| × |B|
Regra da subtração: (derivada doprincípio aditivo)
se B ⊆ A então |A – B| = |A| – |B|
Regra do quociente: (derivada doprincípio multiplicativo)
se R é uma relação de equivalência sobreA onde toda classe de equivalência temtamanho r, então |A/R| = |A|
r
83/168
Princípios de contagem: revisão (cont)
Princípio da inclusão/exclusão:
|A1 ∪ A2 ∪ . . . ∪ An| =
+∑
1≤i≤n
|Ai|
–∑
1≤i<j≤n
|Ai ∩ Aj|
+∑
1≤i<j<k≤n
|Ai ∩ Aj ∩ Ak|
...
(–1)n–1 |A1 ∩ A2 ∩ . . . ∩ An|
Princípio dos escaninhos:se n objetos são colocados em k escaninhos e n > k, há ao menos um escaninhocontendo mais de um envelope.
84/168
Resumo de arranjos e combinações
Contagem de estruturas construídas a partir de um conjunto com n elementos.
sem reposição com reposição
k-tuplas Akn = n!
(n–k)! ARkn = nk
k-conjuntos Ckn =
(nk)
Ckn =
(nk)
k-multiconjuntos Ckn =
(nk)
CRkn =
(k+n–1k)
onde (nk
)= n!
(n – k)!k!
85/168
Resumo de permutações
Permutações simples: formas distintas de enumerar um conjunto detamanho n.
Pn = n!
Permutações com repetição: formas distintas de enumerar ummulticonjunto de tamanho n, sendo r1, . . . , rn as repetições de símbolo.
PR(n; r1, r2, . . . , rn) =(
nr1, r2, . . . , rn
)= n!
r1!r2! · · · rn!
86/168
Resumo de permutações (2)
Permutações circulares: formas de dispor circularmente os elementos de umconjunto de tamanho n.
(PC)n = (n – 1)!
Permutações caóticas: formas de embaralhar uma sequência de valoresdistintos sem que nenhum valor acabe na sua posição original.
Dn = n!(
1 – 11! + 1
2! – 13! + . . . + (–1)n 1
n!
)≈ n!
e
87/168
Resumo de contagem de funções
Sejam A e B conjuntos finitos, onde |A| = a e |B| = b.
Número de funções f : A → B: ba
Número de funções bijetoras f : A → B (considerando a = b): b!
Número de funções injetoras f : A → B (considerando a ≤ b): b!(b–a)!
Número de funções sobrejetoras f : A → B (considerando a ≥ b):
b∑i=0
(–1)i(bi
)(b – i)a
88/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
89/168
Sequências
Definição: uma sequência (an) é uma lista infinita de números reais.
(an) = (a0, a1, a2, . . .)
Exemplo:
(an) = (0, 1, 2, 3, 4, 5, 6, . . .)(bn) = (1, 1, 1, 1, 1, 1, . . .)(cn) = (0, 1, 0, –1, 0, 1, 0, –1, 0, 1, . . .)
Notação: sempre consideraremos que sequências começam no índice zero(primeiro elemento é a0).
90/168
Sequências (cont.)
Notação: usamos (an) = expressão para descrever uma sequência de númeroscom base em sua estrutura:
Exemplo:
(an) = n2 (an) = (0, 1, 4, 9, 16, 25, . . .)(bn) = 1 (bn) = (1, 1, 1, 1, 1, . . .)
(cn) ={
0 se n par(–1)bn/2c se n ímpar
(cn) = (0, 1, 0, –1, 0, 1, 0, –1, . . .)
91/168
Séries de potências
Definição: uma série de potências é uma série infinita da forma
a0 + a1x + a2x2 + a3x3 + . . .
onde todos ai (para i ∈ N) são números reais e x é uma variável.
Nota: qualquer polinômio finito pode ser visto como uma série de potênciastendo sempre 0 como coeficiente a partir de um certo índice.
92/168
Séries de potências: soma
Definição: a soma de duas séries de potências é realizada por componentes:
a0 + a1x + a2x2 + · · ·+ b0 + b1x + b2x2 + · · ·
(a0 + b0) + (a1 + b1)x + (a2 + b2)x2 + · · ·
93/168
Séries de potências: multiplicação
Definição: a multiplicação de duas séries A e B é dada pela soma de todasas possíveis multiplicações de termos de A e termos de B.
a0 + a1x + a2x2 + · · ·× b0 + b1x + b2x2 + · · ·
a0b0 + (a1b0 + a0b1)x + (a0b2 + a1b1 + a2b0)x2 + · · ·
Nota: note que, para calcular o coeficiente xn de A × B precisamos calcular asoma todos os termos com potência xn.
94/168
Funções geradoras ordinárias
Definição: dizemos que a série de potências
A = a0 + a1x + a2x2 + a3x3 + . . .
é a função geradora ordinária da sequência
(a0, a1, a2, a3, . . .)
Intuição: representar uma sequência de números através de uma única expressão.
Nota: as potências da variável x ( no caso, x0, x1, x2, . . .) servem essencialmente paraseparar os valores da sequência.
Importante: podemos recuperar o n-ésimo elementos da sequência (an) através docoeficiente da potência xn em A.
Notação: Vamos usar A ⇔ (an) para indicar que A é a função geradora da sequência(an).
95/168
Funções geradoras ordinárias (motivação)
A principal motivação de representarmos sequências através de funçõesgeradoras ordinárias é que essa transformação permite a manipulaçãoalgébrica da informação contida na sequência.
Veremos dois usos fundamentais para funções geradoras nesta disciplina• obter fórmulas fechadas para resoluções de problemas combinatórios• resolver relações de recorrência
Contudo, antes de partirmos para as aplicações, será necessário aprender comomanipular adequadamente as funções geradoras.
A seguir, construiremos um repertório de resultados que serão essenciais naresolução de problemas usando f.g.o.
96/168
Identidades básicas (1)
Teorema:
1 + x + x2 + x3 + · · · = 11 – x
Demonstração: assuma
1 + x + x2 + · · · = f(x)
e multiplique ambos os lados da equação por (1 – x).
Nota: normalmente no estudo de séries nos preocupamos com questões deconvergência, isto é, a faixa de valores para as quais o limite das somas parciaisé um número real. No caso acima, se x > 1 a série não converge. Nestadisciplina, contudo, não estaremos avaliando x, portanto conscientemente nãonos preocuparemos em calcular intervalos de convergência.
97/168
Identidades básicas (2)
Teorema:
1 + cx + c2x2 + c3x3 + · · · = 11 – cx
98/168
Identidades básicas (3)
Teorema:
c + cx + cx2 + cx3 + · · · = c(
11 – x
)
99/168
Identidades básicas (4)
Teorema:
1 + x + x2
2! + x3
3! + x4
4! + · · · = ex
100/168
Identidades básicas (5)
Teorema:
1 + 0x + 1x2 + 0x3 + 1x4 + 0x5 + 1x6 + · · · = 11 – x2
101/168
Identidades básicas (6)
Teorema:
1 + 0x + 0x2 + 1x3 + 0x4 + 0x5 + 1x6 + · · · = 11 – x3
102/168
Identidades básicas (7)
Teorema:
1 + xc + x2c + x3c + · · · = 11 – xc
103/168
Identidades básicas (8)
Considere
A(x) = a0 + a1x + a2x2 + a3x3 + · · · ⇔ (a0, a1, a2, a3, . . .)
Teorema:
xA(x) ⇔ (0, a0, a1, a2, a3, a4, . . .)x2A(x) ⇔ (0, 0, a0, a1, a2, a3, a4, . . .)x3A(x) ⇔ (0, 0, 0, a0, a1, a2, a3, a4 . . .)
...
Intuição: multiplicar a f.g.o por xk tem o efeito de um deslocamento à direitana sequência codificada, preenchendo as primeiras k posições com 0.
104/168
Identidades básicas (9)
Considere A(x) = a0 + a1x + a2x2 + · · · ⇔ (a0, a1, a2, . . .)
Teorema: (derivação)
ddx A(x) = 0a0 + 1a1 + 2a2x + 3a3x2 + · · · =
∞∑i=1
i · aixi–1
⇔ (1a1, 2a2, 3a3, . . . )
Intuição: multiplica pelo índice, depois executa um deslocamento à esquerda.
105/168
Identidades básicas (10)
Considere A(x) = a0 + a1x + a2x2 + · · · ⇔ (a0, a1, a2, . . .)
Teorema:
x(
ddx A(x)
)= 0a0x + 1a1x + 2a2x2 + 3a3x3 + · · ·
⇔ (0a0, 1a1, 2a2, 3a3, 4a4, . . .)
Intuição: multiplica pelo índice, apaga o termo a0.
106/168
Identidades básicas (11)
Considere A(x) = a0 + a1x + a2x2 + · · · ⇔ (a0, a1, a2, . . .)
Teorema: (integração) ∫A(x)dx = c +
∞∑i=0
aixi+1
i + 1
Intuição: deslocamento à direita (preenchendo com c a primeira posição) edivide pelo índice novo (para índice maior que 0).
107/168
Identidades básicas (12)
ConsidereA(x) = a0 + a1x + a2x2 + · · · ⇔ (a0, a1, a2, . . .)eB(x) = b0 + b1x + b2x2 + · · · ⇔ (b0, b1, b2, . . .)
Teorema:
A(x)B(x) =∞∑
j=0
j∑i=0
aibj–i
xj
⇔ ( a0b0,a0b1 + a1b0,a0b2 + a1b1 + a2b0,. . .)
108/168
Identidades básicas (13)
Considere A(x) = a0 + a1x + a2x2 + · · · ⇔ (a0, a1, a2, . . .)
Teorema: (1
1 – x
)A(x) = a0 + (a0 + a1)x + (a0 + a1 + a2)x2 + · · ·
⇔ ( a0,a0 + a1,a0 + a1 + a2,. . .)
Intuição: soma dos valores até o índice em questão.
109/168
Funções geradoras: exercícios I
5.1 Encontrar a função geradora ordinária f(x) na qual o coeficiente ar de xr éo número de soluções inteiras positivas de x1 + x2 + x3 = r, onde{9, 10, 11, 12, 13, 14, 15}, 2 ≤ xi ≤ 4 para i = 1, 2, 5 ≤ x3 ≤ 7.
5.2 Achar a função geradora ordinária f(x) na qual o coeficiente ar de xr é onúmero de soluções inteiras não-negativas da equação 2x + 3y + 7z = r.
5.3 Encontrar a função geradora para a sequência (ar) = (0, 0, 1, 1, 1, 1, . . .).5.4 Encontrar a sequência cuja função geradora é dada por
g(x) = 11 – x2
5.5 Encontrar a função geradora para a sequência
(ar) =(
1, 11! , 1
2! , 13! , 1
4! , . . .
)
110/168
Funções geradoras: exercícios II
5.6 Encontrar a sequência cuja função geradora ordinária é x2 + x3 + ex.
5.7 Encontrar a função geradora ordinária para a sequência
(ar) =(
2r
r!
)
5.8 Qual o coeficiente de x23 na expansão de (1 + x5 + x9)6?
111/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
112/168
Potências de séries: exemplo 1
Expressão original:
(1 + ax)(1 + bx)(1 + cx)
Expansão:
1 + (a + b + c)x + (ab + bc + ac)x2 + abcx3
Significado:Cálculo de todos os subconjuntos de {a, b, c}, separados por tamanho de conjunto i(coeficiente de xi).
Substituindo a, b e c por 1:
(1 + x)3 = 1 + (1 + 1 + 1)x + (1 + 1 + 1)x2 + 1x3
= 1 + 3x + 3x2 + x3
113/168
Potências de séries: exemplo 2
Expressão original:
(1 + ax + a2x2)(1 + bx)(1 + cx)
Expansão:
1 + (a + b + c)x + (a2 + ab + bc + ac)x2 + (abc + a2c + a2b)x3 + (a2bc)x4
Significado:Cálculo de todos os sub-multiconjuntos de Ha, a, b, cI, separados por tamanho demulticonjunto i (coeficiente de xi).
Note que a pode ocorrer até duas vezes, enquanto que b e c somente uma única vez.Substituindo a, b e c por 1:
(1 + x + x2)(1 + x)2 = 1 + 3x + 4x2 + 3x3 + x4
114/168
Potências de séries: exemplo 3
Expressão original: (infinita)
(1 + ax + a2x2 + · · · )(1 + bx + b2x2 + · · · )(1 + cx + c2x2 + · · · )
Expansão: (infinita)
1 + (a + b + c)x + (a2 + b2 + c2 + ab + bc + ac)x2+
(abc + a2b + a2c + b2a + b2c + c2a + c2b + a3 + b3 + c3)x3 + · · ·
Significado:Cálculo de todas as combinações com reposição sobre o alfabeto {a, b, c}, separadospor tamanho de multiconjunto i (coeficiente de xi).
Substituindo a, b e c por 1:
(1 + x + x2 + x3 + · · · )3 = 1 + 3x + 6x2 + 10x3 + · · ·
115/168
Potências de séries e contagem
Lembre que 11–x = 1 + x + x2 + x3 + · · ·
Podemos representar a contagem de combinações de tamanho k sobre um alfabetode tamanho n descobrindo o coeficiente de xk na expansão de• (1 + x)n (sem reposição)
•( 1
1–x)n (com reposição)
Note que casos intermediários entre reposição irrestrita e inexistência de reposiçãopodem ser uniformemente modelados.
Notação: escrevemos [xi]f(x) para denotar o coeficiente de xi na expansão emsérie de potências de f(x).
116/168
Potências de séries e contagem: exemplo
Contagem de combinações simples de tamanho k sobre alfabeto de tamanho n:
[xk](1 + x)n =(nk
)(teorema binomial)
Contagem de combinações com reposição de tamanho k sobre alfabeto de tamanho n:
[xk]( 11 – x
)n=(k + n – 1
k
)(demonstração a seguir . . . )
Contagem de multiconjuntos de tamanho k sobre alfabeto {a, b, c, d} (comreposição) onde 2 ≤ a ≤ 5, 0 ≤ b ≤ 3, e qualquer número de repetições de cs e ds:
[xk]((x2 + x3 + x4 + x5)(1 + x + x2 + x3)
( 11 – x
)2)
117/168
Funções geradoras: cálculo de coeficientes
Normalmente quando usamos funções geradoras, a parte de modelagem dasrestrições do problema é fácil.
Exemplo: obter uma expressão no formato [xk]f(x)
Contudo, efetivamente calcular uma fórmula para o coeficiente de xk na expansão def(x) pode ser um processo trabalhoso. Existem duas estratégias principais:
• Calcular a expansão de f(x) em séries de MacLaurin (envolve calcular derivadas).
• Descrever f(x) como uma combinação de funções cuja expansão em séries depotência é conhecida.
118/168
Série de MacLaurin
A seguinte identidade permite extrair os coeficientes da sequência codificadapor uma função f(x) infinitamente diferenciável:
Definição: (Série de MacLaurin)
f(x) = f(0) + f ′(0)x + f ′′(0)x2
2! + f ′′′(0)x3
3! + f ′′′′(0)x4
4! + · · ·
Este resultado não será provado nesta disciplina. Contudo, podemos nosconvencer da sua validade derivando os dois lados da igualdade e comparandoas expressões resultantes.
119/168
Notação binomial generalizada
Vamos utilizar a expansão em série de MacLaurin para generalizar o teoremabinomial.
Inicialmente redefinimos(u
k)para u ∈ R e k ∈ N.
Definição: (uk
)=
{u(u–1)(u–2)···(u–k+1)
k! se k > 01 se k = 0
Esta definição permite determinar(u
k)para qualquer valor real u, inclusive frações e
números negativos.
Exemplo: (–5, 53
)= –5, 5 × –6, 5 × –7, 5
3! = –268, 125
120/168
Notação binomial generalizada (2)
A seguinte identidade é útil quando temos “alfabeto de tamanho negativo”.
Teorema: (–uk
)=(k + u – 1
k
)(–1)k
Demonstração:
(–uk
)=
k︷ ︸︸ ︷(–u)(–u – 1) . . . (–u – k + 1)
k! (definição)
=
k︷ ︸︸ ︷(u)(u + 1) . . . (u + k – 1) ·(–1)k
k! (fatorando (-1)’s)
=(u + k – 1
k
)(–1)k (definição)
121/168
Teorema binomial generalizado
Considere u ∈ R.
Teorema:
(1 + x)u =∞∑i=0
(ui
)xi
Demonstração: calculamos a série de MacLaurin de (1 + x)u.
(1 + x)u
=
(1 + x)u∣∣∣x=0
+( ddx (1 + x)u
∣∣∣x=0
)x +
(d2
dx2 (1 + x)u∣∣∣x=0
)x2
2! + · · ·
122/168
Teorema binomial generalizado (2)
Calculando os coeficientes da série:• (1 + x)u
∣∣∣x=0
= (1 + 0)u = 1
• ddx (1 + x)u
∣∣∣x=0
= u(1 + x)u–1|x=0 = u
• d2
dx2 (1 + x)u∣∣∣x=0
= u(u – 1)(1 + x)u–2|x=0 = u(u – 1) . . .
Portanto:
(1 + x)u
= 1 + ux + u(u – 1)x2
2! + u(u – 1)(u – 2)x3
3! + · · ·
=(u0
)+(u1
)x +(u2
)x2 + · · · =
∞∑i=0
(ui
)xi
123/168
Exemplo de cálculo de coeficientes
Exemplo: Vamos mostrar a derivação de
[xk]( 1
1 – x
)n=(k + n – 1
k)
utilizando o teorema binomial generalizado.
Rescrevendo a expressão: ( 11 – x
)n= (1 – x)–n
Utilizando a substituição y = –x= (1 + y)–n
124/168
Exemplo de cálculo de coeficientes (2)
(1 + y)–n
=∞∑i=0
(–ni)
yi (teorema binomial generalizado)
=∞∑i=0
(i + n – 1i)
(–1)iyi · · · (alfabeto negativo)
=∞∑i=0
(i + n – 1i)
(–1)i(–1)ixi (substituição y = –x)
=∞∑i=0
(i + n – 1i)
xi (simplificando (–1)2i = 1)
125/168
Exemplo de cálculo de coeficientes (3)
Portanto:
[xk]( 11 – x
)n
= [xk]
( ∞∑i=0
(i + n – 1
i
)xi
)
=(k + n – 1
k
)
126/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
127/168
Potências de séries e contagem de tuplas
Vimos que problemas envolvendo combinações podem ser representadosatravés da descoberta de coeficientes em potências de séries (consequência doteorema binomial):
(x + 1)n =n∑
i=0
(ni
)xi
Nesses problemas, assumimos que a ordem dos elementos não é relevante,isto é, contamos multiconjuntos.
Contudo, não há a mesma equivalência para problemas de contagemenvolvendo tuplas ou arranjos (tuplas sem repetição):
??? =n∑
i=0
n!(n – i)!xi
128/168
Potências de séries e contagem de tuplas (cont.)
Considerando que a relação entre o número de combinações e o número dearranjos de tamanho k é conhecida, isto é,
k!(
nk
)= k! n!
(n – k)!k! = n!(n – k)!
poderíamos estabelecer uma correlação entre potências de séries e contagemde arranjos se mudarmos a codificação de séries.
(x + 1)n =n∑
i=0
n!(n – i)!
xi
i!
129/168
Funções geradoras exponenciais
Definição: dada uma sequência de números
(a0, a1, a2, . . .)
a sua respectiva função geradora exponencial (f.g.e) é a série
a0x0
0! + a1x1
1! + a2x2
2! + a3x3
3! + · · ·
Nota: a designação exponencial vem do fato que
ex = (1 + x + x2
2! + x3
3! + · · · ) ⇔ (1, 1, 1, 1, . . .)
Importante: os fatos anteriormente provados valem somente para f.g.o! Épreciso desenvolver novos resultados para trabalhar com f.g.e.
130/168
Funções geradoras exponenciais: identidades
Teorema:
ex =(
1 + x + x2
2! + x3
3! + · · ·)
⇔ (1, 1, 1, . . .)
Teorema:
eax =(
1 + ax + a2x2
2! + a3x3
3! + · · ·)
⇔ (1, a, a2, a3, . . .)
Teorema:
1ex =
(1 – x + x2
2! – x3
3! + · · ·)
⇔ (1, –1, 1, –1, . . .)
131/168
Funções geradoras exponenciais: identidades (2)
Teorema:
ex + e–x
2 =(
1 + x2
2! + x4
4! + x6
6! + · · ·)
⇔ (1, 0, 1, 0, . . .)
Intuição: seleciona as posições pares da sequência.
Teorema:
ex – e–x
2 =(
x + x3
3! + x4
5! + · · ·)
⇔ (0, 1, 0, 1, 0, . . .)
Intuição: seleciona as posições ímpares da sequência.
132/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
133/168
Funções geradoras exponenciais e contagem
Apesar de ser uma codificação de sequências diferente de f.g.o, a forma deresolver problemas de contagem usando f.g.e é a mesma. O que muda écodificação do problema (em f.g.e) e a leitura do resultado:• f.g.o ⇒ contagem de multiconjuntos• f.g.e ⇒ contagem de tuplas
Nota: nunca esqueça que o fatorial no denominador faz parte da construção daf.g.e, e não deve ser lido como parte do coeficiente.
Exemplo: como 2x3 = 3!3!2x3, temos[
x3
3!
](1 + 4x + 2x3 + 5x5) = 3! × 2 = 12
134/168
Funções geradoras exponenciais: exemplo 1
Expressão original:
(1 + ax)(1 + bx)(1 + cx) = 1 + (a + b + c)x + (ab + bc + ac)x2 + abcx3
(o caso sem reposição possui a mesma codificação como f.g.o e f.g.e)
Substituindo a, b e c por 1:
(1 + x)3 = 1 + (1 + 1 + 1)x + (1 + 1 + 1)x2 + 1x3
= (1 + 3x + 3x2 + x3)
Leitura: [x2
2!
](1 + 3x + 3x2 + x3) = 6
Significado: número de arranjos (tuplas construídas sem reposição) detamanho 2 sobre o alfabeto {a, b, c}.
135/168
Funções geradoras exponenciais: exemplo 2
Expressão original:
(1x0
0!+ a
x1
1!+ a2 x2
2!+ a3 x3
3!+ · · · ) ×
(1x0
0!+ b
x1
1!+ b2 x2
2!+ b3 x3
3!+ · · · )
136/168
Funções geradoras exponenciais: exemplo 2
Expressão original:
(1x0
0!+ a
x1
1!+ a2 x2
2!+ a3 x3
3!+ · · · ) ×
(1x0
0!+ b
x1
1!+ b2 x2
2!+ b3 x3
3!+ · · · )
Expandindo . . .
1+( 1b0!1!
+a1
1!0!
)x1+(
1b2
0!2!+
ab1!1!
+a212!0!
)x2+(
1b3
0!3!+
ab2
1!2!+
a2b2!1!
+a313!0!
)x3 + · · ·
136/168
Funções geradoras exponenciais: exemplo 2
Expressão original:
(1x0
0!+ a
x1
1!+ a2 x2
2!+ a3 x3
3!+ · · · ) ×
(1x0
0!+ b
x1
1!+ b2 x2
2!+ b3 x3
3!+ · · · )
. . . multiplicando cada linha i > 0 por 1 (na forma i!i! ) . . .
1+
1!( 1b
0!1!+
a11!0!
) x1
1!+
2!(
1b2
0!2!+
ab1!1!
+a212!0!
)x2
2!+
3!(
1b3
0!3!+
ab2
1!2!+
a2b2!1!
+a313!0!
)x3
3!+ · · ·
136/168
Funções geradoras exponenciais: exemplo 2
Expressão original:
(1x0
0!+ a
x1
1!+ a2 x2
2!+ a3 x3
3!+ · · · ) ×
(1x0
0!+ b
x1
1!+ b2 x2
2!+ b3 x3
3!+ · · · )
. . . e reescrevendo:
1+( 1!0!1!
b +1!
1!0!a) x1
1!+( 2!
0!2!b2 +
2!1!1!
ab +2!
2!0!a2) x2
2!+( 3!
0!3!b3 +
3!1!2!
ab2 +3!
2!1!a2b +
3!3!0!
a3) x3
3!+ · · ·
Intuição: o coeficiente de xk
k! consiste de todos os k-multiconjuntos sobre o alfabeto {a, b},cada um multiplicado pela respectiva quantidade de permutações. Substituindo a e b por 1,contamos todas as k-tuplas.
136/168
Funções geradoras exponenciais e contagem
Contagem de arranjos de tamanho k sobre alfabeto de tamanho n:[xk
k!
](1 + x)n = k!
(nk
)= n!
(n – k)!
Contagem de tuplas (arranjos com reposição) de tamanho k sobre alfabeto detamanho n: [
xk
k!
](ex)n = nk
Contagem de tuplas de tamanho k sobre o alfabeto {a, b, c} onde 0 ≤ a ≤ 3,1 ≤ b ≤ 2 e c pode ocorrer indefinidamente:[
xk
k!
]((1 + x + x2
2! +x3
3!
)(x + x2
2!
)ex)
137/168
Funções geradoras exponenciais: exemplo 3
Exemplo: Quantas tuplas de tamanho k existem sobre o alfabeto {a, b, c} possuindoum número par de a’s?
Codificação do problema usando f.g.e:[xk
k!
]((1 + x2
2! +x4
4! + · · ·)e2x)
Usando o fato que (1 + x2
2! +x4
4! + · · ·)
= ex + e–x
2Temos [
xk
k!
](ex + e–x
2 e2x)
=[xk
k!
]12(e
3x + ex) = (3k + 1)2
138/168
Funções geradoras exponenciais: exemplo 4Exemplo: Derivação da fórmula de contagem de funções sobrejetoras de A para B utilizandof.g.e, onde |A| = a e |B| = b.
Equivale a contar as tuplas de tamanho a onde cada símbolo de B ocorre ao menos uma vez:[ xa
a!
](ex – 1)b
Simplificação:
((–1) + ex)b
=b∑
i=0
(bi
)(–1)ie(b–i)x [teor. binom.]
=b∑
i=0
(bi
)(–1)i
∞∑j=0
(b – i)j xj
j![expansão e(b–i)x]
=b∑
i=0
∞∑j=0
(–1)i(b
i
)(b – i)j xj
j![internaliza (–1)i
(bi
)]
=∞∑j=0
b∑i=0
(–1)i(b
i
)(b – i)j xj
j![troca ordem das somas]
Leitura:[xa
a!
](ex – 1)b
=b∑
i=0
(–1)i(b
i
)(b – i)a
139/168
Funções geradoras: resumo do método
Resolução de problemas de contagem de multiconjuntos de tamanho k:
1. Modele o problema e suas restrições através de uma f.g.o f(x) (funçãogeradora ordinária)
2. Simplifique a f.g.o para facilitar a leitura de coeficientes (expansão emsérie, transformá-la em uma soma de f.g.o’s conhecidas, etc...)
3. Leia o coeficiente de xk (na nossa notação,[xk]
f(x))
140/168
Funções geradoras: resumo do método (2)
Resolução de problemas de contagem de tuplas de tamanho k:
1. Modele o problema e suas restrições através de uma f.g.e f(x) (funçãogeradora exponencial)
2. Simplifique f(x) para facilitar a leitura de coeficientes (expansão em série,transformá-la em uma soma de f.g.e’s conhecidas, etc...)
3. Leia o coeficiente de xk
k! (na nossa notação,[
xk
k!
]f(x))
141/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
142/168
Relações de recorrência
Em matemática, o mais comum é definirmos novas funções através dacomposição de funções pré-existentes. Ex:
f(x) =√
x + x3
Contudo, certas funções podem ter uma definição simples reutilizandoresultados de sua própria aplicação sobre outros valores. Ex:
0! = 1 Fib(0) = 0n! = n × (n – 1)! Fib(1) = 1
Fib(n) = Fib(n – 1) + Fib(n – 2)
neste caso, dizemos que as definições são recorrentes, i.e. estabelecem umarelação de recorrência entre as saídas da função.
143/168
Relações de recorrência (cont.)
Apesar de Fib(n) possuir uma definição simples, precisamos calcular todos os999 valores anteriores para descobrir o valor de Fib(1000).
Nesse caso (valores grandes) seria interessante obter uma definiçãonão-recorrente para Fib(n).
Encontrar uma definição não-recorrente para uma função definida de formarecorrente é resolver a recorrência.
Nesta disciplina, veremos como• obter relações de recorrência a partir da descrição de um problema• resolver recorrências
Nota: lembre que sequências numéricas contendo elementos do conjunto Xpodem ser vistas como funções do tipo N → X.
144/168
Relações de recorrência: exemplo 1
A Torre de HanoiNeste jogo, inventado pelo matemático francês Édouard Lucas em 1883, há três eixos(esquerda, centro, direita) e um número n de discos de tamanhos distintos. Oobjetivo é passar os n discos (colocados em ordem ascendente de tamanho, de cimapara baixo) do eixo à esquerda para o eixo à direita na mesma ordem, efetuando omenor número de movimentos. Somente um disco pode ser mudado de eixo a cadamovimento, e ele não pode ser colocado em cima de um disco menor. Qual o númeromínimo de passos para a resolução de uma instância do jogo contendo n discos?
Applet Java para simulação do jogo:http://www.mazeworks.com/hanoi/index.htm
Recorrência: (contagem do número mínimo de passos)
H(0) = 0H(n) = 2H(n – 1) + 1
145/168
Relações de recorrência: exemplo 2
Cálculo do tamanho de uma população de saposA população de sapos de um lago quadruplica a cada ano. No primeiro dia decada ano, 100 sapos são removidos do lago e transferidos para outro local.Assumindo que inicialmente havia 50 sapos no lago, quantos sapos o lago teráem n anos? Suponha que os sapos não morrem e que não haja migração.
Recorrência:
S(0) = 50S(n) = 4 ∗ S(n – 1) – 100 para n > 0
146/168
Relações de recorrência: exemplo 3
Cálculo do tamanho de uma população de coelhosSuponha que um casal de coelhos recém-nascidos é colocado numa ilha, e queeles não produzem descendentes até completarem dois meses de idade. Umavez atingida esta idade, cada casal de coelhos produz exatamente um outrocasal de coelhos por mês. Qual seria a população de coelhos na ilha após novemeses, supondo que nenhum dos coelhos tenha morrido e que não hajamigração neste período?
Recorrência:
F(0) =0F(1) =1 (casal)F(n) =F(n – 1) + F(n – 2) para n > 1
147/168
Resolução de recorrências
Vimos três problemas e suas respectivas recorrências:
A Torre de Hanoi
H(0) = 0H(n) = 2H(n – 1) + 1 para n > 0
Cálculo do tamanho de uma população de sapos
S(0) = 50S(n) = 4 ∗ S(n – 1) – 100 para n > 0
Cálculo do tamanho de uma população de coelhos (Fibonacci)
Fib(0) =0Fib(1) =1Fib(n) =Fib(n – 1) + Fib(n – 2) para n > 1
148/168
Resolução de recorrências (2)
Veremos agora como solucionar recorrências.
Nesta disciplina, dois métodos:• hipótese e confirmação• resolução através de funções geradoras ordinárias
Nota: o livro menciona outros métodos além dos vistos acima, mas não vamosfocar neles.
149/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
150/168
Método da hipótese e confirmação
Considere a sequência de valores H(n), contada apartir de n = 0
H(0) = 0H(n) = 2H(n – 1) + 1
Para chegarmos a uma hipótese, precisamosidentificar algum padrão de formação na sequênciade números.
Observando os valores à direita, podemos detectarum padrão: aparentemente H(n) é sempre o númeroanterior a 2n.
Hipótese: H(n) = 2n – 1
n H(n)0 01 12 33 74 155 316 637 1278 255...
...
151/168
Método da hipótese e confirmação (2)
Podemos verificar manualmente se a hipótese funcionapara os primeiros valores da tabela:
20 – 1 = 0
21 – 1 = 1
22 – 1 = 3 . . .
Contudo, para termos certeza da validade da hipótese, énecessário provar que ela é válida.
Para recorrências, o método de prova mais recomendadoé indução matemática, visto que as bases e os passos deindução estão explicitamente descritos.
H(0) = 0H(n) = 2H(n – 1) + 1
n H(n)0 01 12 33 74 155 316 637 1278 255...
...
152/168
Método da hipótese e confirmação (3)
Teorema: H(n) = 2n – 1
Demonstração:
• Base: H(0) = 20 – 1
1. 20 – 1 = 0
• Passo indutivo:Se H(n) = 2n – 1 então H(n + 1) = 2n+1 – 1.
1. H(n + 1) = 2H(n) + 1 (Def.)2. H(n + 1) = 2(2n – 1) + 1 (H.I.)3. H(n + 1) = (2n+1 – 2) + 14. H(n + 1) = 2n+1 – 1
H(0) = 0H(n) = 2H(n – 1) + 1
n H(n)0 01 12 33 74 155 316 637 1278 255...
...
153/168
Método da hipótese e confirmação (4)
Também é útil na identificação de padrões a expansão de H(n) para certos valorespequenos de n. O padrão pode emergir da simplificação da expressão final.
Exemplo: para n = 4
H(4) = 2H(3) + 1 (Def. Recorrente)= 2(2H(2) + 1) + 1 (Def. Recorrente)= 2(2(2H(1) + 1) + 1) + 1 (Def. Recorrente)= 2(2(2(2H(0) + 1) + 1) + 1) + 1 (Def. Recorrente)= 2(2(2(2 · 0 + 1) + 1) + 1) + 1 (Base)= 4(2(2 · 0 + 1) + 1) + 2 + 1 (Distribui 2)= 8(2 · 0 + 1) + 4 + 2 + 1 (Distribui 4)= 16 · 0 + 8 + 4 + 2 + 1 (Distribui 8)= 8 + 4 + 2 + 1 (Remove 0)
=3∑
i=0
2i = 24 – 1 = 15
154/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
155/168
Resolução de recorrências com f.g.o
O método anterior de resolução exige que tenhamosuma hipótese correta de trabalho, o que nem semprepode ser formulada considerando o padrão dasequência de números:
Exemplo:
Fib(0) =0Fib(1) =1Fib(n) =Fib(n – 1) + Fib(n – 2) para n > 1
Nesses casos, veremos como resolver recorrênciascalculando a função geradora ordinária da sequênciade números (an) = F(n)
n Fib(n)0 01 12 13 24 35 56 87 138 21...
...
156/168
Resolução de recorrências com f.g.o
Para ilustrar o método, vamos utilizar a recorrência já resolvida H(n).
H0 = 0Hn = 2Hn–1 + 1 para n > 0
Vamos chamar de H a f.g.o da sequência (H0, H1, H2, . . .). Estamos interessadosinicialmente em uma definição para H.
Considere as seguintes f.g.o’s:
H = H0 + H1x + H2x2 + H3x3 + · · ·2xH = 0 + 2H0x + 2H1x2 + 2H2x3 + · · ·
x( 1
1–x)
= 0 + 1x + 1x2 + 1x3 + · · ·
Por construção, a equação abaixo representa exatamente as restrições da recorrênciasobre H:
H = 2xH + x1 – x
157/168
Resolução de recorrências com f.g.o (2)
Resolvendo:
H = 2xH +x
1 – xH – 2xH =
x1 – x
(1 – 2x)H =x
1 – xH =
x(1 – x)(1 – 2x)
Note que obtivemos uma expressão fechada para a f.g.o da sequência de números(H0, H1, H2, . . .)
H =x
(1 – x)(1 – 2x)
Portanto, descobrir uma fórmula explícita para Hn equivale a descobrir o coeficiente de xn
na expansão de H:Hn = [xn]
x(1 – x)(1 – 2x)
158/168
Resolução de recorrências com f.g.o (3)
Habitualmente, a parte mais complexa da resolução de recorrências utilizando f.g.o éo cálculo de coeficientes.
Se pudermos transformar a f.g.o em uma soma de f.g.o’s cujos coeficientes sãoconhecidos, a resolução se torna fácil.
No nosso exemplo, através de manipulação algébrica (frações parciais) podemos fazera seguinte transformação
x(1 – x)(1 – 2x) = 1
1 – 2x – 11 – x
e, portanto,
Hn = [xn]( 11 – 2x – 1
1 – x
)= 2n – 1
Nota: a discussão sobre os detalhes da transformação algébrica utilizada acima serávista quando apresentarmos a resolução de Fibonacci.
159/168
Resolução de recorrências com f.g.o: exercício
Exercício: resolva a seguinte recorrência utilizando o método das funçõesgeradoras ordinárias:
Cálculo do tamanho de uma população de sapos
S(0) = 50S(n) = 4 ∗ S(n – 1) – 100 para n > 0
160/168
Conteúdo
Princípios aditivo e multiplicativoPermutaçõesArranjosCombinaçõesTeorema binomialTriângulo de PascalRegra da subtraçãoRegra do quocienteDistribuição de elementos idênticosCombinações com repetiçãoArranjos com repetiçãoPermutações circularesPermutações com repetição
Teorema multinomialPrincípio da inclusão e exclusãoPermutações caóticasPrincípio dos escaninhosRevisão dos princípios de contagemFunções geradoras ordináriasF.g.o.’s e contagem de multiconjuntosFunções geradoras exponenciaisF.g.e.’s e contagem de tuplasRelações de recorrênciaRecorrências: hipótese e confirmaçãoRecorrências: funções geradorasRecorrências: fórmula para Fibonacci
161/168
Resolução de recorrências com f.g.o: Fibonacci
A seguir vamos considerar a descoberta da f.g.o para Fibonacci, e falaremos sobre astécnicas de manipulação algébrica para simplificar a f.g.o obtida.
F0 = 0F1 = 1Fn = Fn–1 + Fn–2 para n > 1
Modelando a recorrência com f.g.o’s:
F = F0 + F1x + F2x2 + F3x3 + · · ·xF = 0 + F0x + F1x2 + F2x3 + · · ·x2F = 0 + 0x + F0x2 + F1x3 + · · ·
x = 0 + 1x + 0x2 + 0x3 + · · ·
Logo:F = xF + x2F + x =⇒ F = x
1 – x – x2
162/168
Fibonacci: constantes φ e φ
As constantes φ e φ aparecem ao longo da resolução da recorrência deFibonacci.• φ = 1+
√5
2 (proporção áurea), ≈ 1.6180 . . .
• φ = 1–√
52 , ≈ –0.6180 . . .
As seguintes identidades são válidas para φ e φ:
1 – φ = φ
1 – φ = φ
φ(–1) = –φ
φ(–1) = –φ
φ2 = 1 + φ
φ2 = 1 + φ
163/168
Resolução da recorrência de Fibonacci
Visão geral sobre as simplificações necessárias:
1. Fatoração do polinômio no denominadorx
–x2 – x + 1=⇒ x
(–1)(x + φ)(x + φ)
2. Separação por frações parciais:
–x(x + φ)(x + φ) =⇒
–φ√5
(x + φ) +φ√5
(x + φ)
3. Formatação como 11–ax :
–φ√5
(x + φ) +φ√5
(x + φ) =⇒ –1√5
1(1 – φx) +
1√5
1(1 – φx)
164/168
Resolução da recorrência de Fibonacci
1. Fatoração do polinômio no denominador
Inicialmente precisamos fatorar o polinômio no denominador. Isso pode ser feitoutilizando o seguinte resultado matemático.
Teorema fundamental da álgebra:
Seja p(x) = c0 + c1x + c2x2 + c3x3 + · · · + cnxn um polinômio de grau n sobre avariável x, com coeficientes complexos c0, c1, . . . , cn.
Há exatamente n raízes complexas r1, r2, . . . , rn para p(x), sendo que p(x) podeser fatorado como
p(x) = cn(x – r1)(x – r2)(x – r3) · · · (x – rn)
Nota: as raízes r1, r2, . . . , rn não são necessariamente distintas, podendo haverrepetição.
165/168
Resolução da recorrência de Fibonacci
2. Separação em frações parciais
Objetivo: obter D e E tal quea
b × c=
Db
+Ec
onde a, b, c são polinômios lineares em x, e b 6= c.
Método:
a = cD + bE assuma igualdade e multipliqueambos os lados por b × c
a|x=rc = bE|x=rc zere c substituindo x pela raiz de ce calcule E
a|x=rb = cD|x=rb zere b substituindo x pela raiz de be calcule D
Nota: se b = c, utilizamos o teorema binomial generalizado.
166/168
Resolução da recorrência de Fibonacci
3. Formatação para leitura de coeficientes
Objetivo: transformar 1x–r numa instância de c 1
1–ax .
Método: multiplique a parte de cima e de baixo da fração por 1–r
1x – r ×
1–r1–r
=1–r
1–r x + 1
= 1–r × 1
1 – 1r x
167/168
Resolução da recorrência de Fibonacci
4. Expansão em séries
F =–1√
51
(1 – φx)+
1√
51
(1 – φx)
F =–1√
5
(∞∑i=0
φixi
)+
1√
5
(∞∑i=0
φixi
)
F =∞∑i=0
1√
5(φi – φi)xi
5. Leitura do coeficiente:[xi]F =
1√
5(φi – φi)
168/168