Re: [obm-l] Combinatória.

["Domingos Jr." <dopikas@xxxxxxxxxx>]

> f(n, p) = (p-2) f(n-1, p) + (p-1) f(n-2, p) para n >= 4.


Ok, agora só faltava matar o problema definitivamente com uma fórmula 
fechada. Estava relendo sobre o maquinário de funções geradoras e vi que 
dá pra atacar este problema com funções geradoras exponenciais. A minha 
referência é o livro do Herbert Wilf, generatingfunctionology (pode 
baixá-lo gratuitamente na internet).

Não vou introduzir os conceitos teóricos, mas a idéia é fixar o 
parâmetro p e olhar para a função geradora exp.
    F = soma_{n >= 0} f(n+4, p) x^n / n!

Uma simples regra mostra a partir da recorrência determinada, ie, f(n+2, 
p) = (p-2) f(n+1, p) + (p-1) f(n, p), temos
    F'' = (p-2) F' + (p-1) F.

Resolvendo a eq. diferencial acima, obtemos F = c_1 exp{-x} + c_2 
exp{(p-1)x}, onde c_1 e c_2 são constantes que não dependem de n (mas 
podem depender de p).
Tomando a série que representa o lado direito, vemos que
    F = soma_{n >= 0} [c_1 (-1)^n + c_2 (p-1)^n] x^n / n!
donde segue que
    f(n+4, p) = c_1 (-1)^n + c_2 (p-1)^n.

Verifiquei empiricamente que
    f(n, p) = (p-1)(-1)^n + (p-1)^n. (para n >= 2)

Para completar uma demonstração formal, basta verificar que para n = 2, 
temos
    f(2, p) = p(p-1) = (p-1)(-1)^2 + (p-1)^2 e que para n = 3
    f(3, p) = p(p-1)(p-2) = (p-1)(-1)^3 + (p-1)^3
e o resultado segue por indução pois o lado direito satisfaz a eq. de 
recorrência para n > 3.

Simplesmente lindo, não é?

Abraços.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================