Re: [obm-l] Contagem

[Domingos Jr.]

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 �: http://www.research.att.com/~njas/sequences/ 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 ----- From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] 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