[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Contagem



Seguem alguns comentarios rapidos sobre esse problema.. Eh provavel que eu tenha errado as contas (nao conferi e fiz meio rapido), mas desse jeito foi bom que a resposta ficou simpatica..
Chame de x(n) as palavras de n letras sem dois A's adjacentes.
Quantas palavras x(n+2) existem?
    Se a primeira letra for A, há duas opções para a segunda letra (B ou C) e a partir daí temos x(n) opções.
    Caso contrário, há duas opções para a primeira letra (B ou C) e a partir daí temos x(n+1) opções.
Logo, x(n+2) = 2x(n+1) + 2x(n) (*)
    Usar funções geratrizes em geral não é uma boa técnica para resolver equações lineares de coeficientes constantes pq nesse caso tem uma teoria mais prática, muito parecida com a que voce usa para resolver EDOs..
    Sem maiores explicacoes sobre a teoria (qq coisa, de uma lida na Eureka ou mande um email que eu dou mais detalhes):
        Solucoes da forma t^n: t^2 - 2t - 2 = 0 => t = 1 +- sqrt(3), logo x(n) = a(1+sqrt(3))^n + b(1-sqrt(3))^n eh solucao de (*) qq que sejam a,b.
    No nosso caso porém, x(1)=3, x(2)=8 (donde a recorrencia da x(0) = 1) e portanto a+b=1, (a+b) + (a-b)sqrt(3) = 3 e então
a = (2+sqrt(3))/2sqrt(3) = (1+sqrt(3))^2/8sqrt(3), b = (-2+sqrt(3))/2sqrt(3) = -(1-sqrt(3))^2/8sqrt(3)
    Logo, x(n) = [(1+sqrt(3))^(n+2) - (1-sqrt(3))^(n+2)]/8sqrt(3)
    Mais legal ainda é que, como (1-sqrt(3))^(n+2) / 8sqrt(3) eh quase sempre muito pequeno, e x(n) eh inteiro, voce pode concluir que:
n par: x(n) = Piso {(1+sqrt(3))^(n+2)/8sqrt(3)}
n impar: x(n) = Teto {(1+sqrt(3))^(n+2)/8sqrt(3)}
----- Original Message -----
Sent: Thursday, September 11, 2003 8:47 PM
Subject: Re: [obm-l] Contagem

seja f(n) := número de palavras de n letras do alfabeto {A, B, C} sem dois ou mais A's consecutivos
e g(n) := conta todas as palavras contadas por f(n) que terminam em A.
f(1) = 3, g(1) = 1
f(n + 1) = 3f(n) - g(n)
    [a idéia: uma palavra de n+1 letras deve ser formada por uma palavra de n letras mais uma letra, essa letra pode ser A, B, C e a palavra anterior a ela não pode ter A's consecutivos, no entanto se a palavra de tamanho n termina em A, não podemos colocar A como última letra, logo descontamos g(n)]
g(n + 1) = f(n) - g(n)
    [pegamos uma palavra de n letras sem A's consecutivos e que NÃO termina em A e concatenamos um A]
 
 
agora vamos tentar resolver essas recorrências!
f(n) = g(n+1) + g(n) =>
f(n + 1) = g(n + 2) + g(n + 1)
mas
f(n + 1) = 3f(n) - g(n) = 3g(n + 1) + 2g(n)
logo
 
3g(n + 1) + 2g(n) = g(n + 2) + g(n + 1)
g(n + 2) = 2[g(n + 1) + g(n)] = 2f(n)
f(n + 2) = g(n + 3) + g(n + 2) = 2f(n + 1) + 2f(n) = 2[f(n+1) + f(n)]
 
 
a recorrência passa a ser:
f(1) = 3, f(2) = 8
f(n + 2) = 2[f(n+1) + f(n)], n >= 1
 
os primeiros valores são 3, 8, 22, 60, 164, ...
 
vamos obter a função geradora dessa nossa f.
seja A(x) = soma{i=1..oo} f(i)*x^i
f(n + 2) = 2[f(n+1) + f(n)] =>
soma{i=1..oo} f(n + 2) = soma{i=1..oo} 2[f(n+1) + f(n)]
 
temos:
soma{i=1..oo} f(n + 2) = f(3)x + f(4)x² + ... = [A(x) - f(1)x - f(2)x²]/x² = [A(x) -3x - 8x²]/x²
soma{i=1..oo} f(n + 1) = f(2)x + f(3)x² + ... = [A(x) - f(1)x]/x = [A(x) - 3x]/x
 
logo:
[A(x) -3x - 8x²]/x² = 2{[A(x) - 3x]/x + A(x)}
A(x) -3x - 8x² = 2{xA(x) - 3x² + x²A(x)}
A(x) (2x² + 2x - 1) = (-2x² - 3x)
A(x) = (-2x² - 3x)/(2x² + 2x - 1) = -1 - (x+1)(2x² + 2x - 1)
 
 
precisamos agora calcular o coeficiente de x^n na série que define A(x), fazer isso é um pouco trabalhoso e é bem técnico... o livro do Herbert Wilf, generatingfunctionology calcula o falor de fib(n), a sequência de Fibonacci...
 
devemos expandir (x+1)/(1 - 2x - 2x²) em "partial fractions" (não sei uma boa tradução).
 
infelizmente estou apanhando pra fazer essa expansão, fico te devendo!
 
um lugar legal pra ver que vc acertou o problema é:
que tem um banco de dados grande de seqüências inteiras, procure a sequência 3, 8, 22, 60, 164 pra vc ver que legal!
 
[ ]'s
 
----- Original Message -----
Sent: Thursday, September 11, 2003 6:05 PM
Subject: [obm-l] Contagem

Usando as letras A, B e C podemos formar 3^n "palavras" de n letras. Quantas dessas palavras não possuem dois ou mais A´s adjacentes??
Esse exercício foi extraído do livro Problem-solving strategies, de Arthur Engel. Gostaria de ver outra solução, pois, a expressão final da minha solução está muito estranha...risos...eu diria ...desengonçada. Se alguém fizer eu agradeço.
         Korshinoi