|
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
|