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