fatoracao e funções geradoras

["Luis Lopes" <llopes@xxxxxxxxxxxxx>]

Sauda,c~oes,

Escrevi para o prof. Rousseau a respeito deste email.
Vejam sua resposta:

===
Dear Luis:

   These sorts of problems are naturally dealt with using
generating functions. The series
\sum_{k_1,k_3 \geq 0} x^{2k_1 + k_3}
sums to \frac{1}{(1-x^2)(1-x)} = (1+x^2 + x^4 + x^6 + \cdots)/(1-x)
= 1 + x + 2x^2 + 2x^3 + 3x^3 + 3x^4 +  \codts  .  Thus the
number of solutions of  n = 2k_1 + k_3 is the coefficient of x^n
in this series, which can be written as 1 + \floor n/2 \floor.
For solutions of  n =  3k_1 + 2k_2 + k_3 the generating
function approach is similar. One gets
1/(1-x)(1-x^2)(1-x^3)) = 1/((1-x)^3(1+x)(1+x+x^2)).
Now the recovery of the coefficient
of  x^n  gets more complicated.  By partial fractions one can
get an exact (though slightly complicated) formula.  Specifically,

(n+3)^2/12 - 7/72 + (-1)^n/8 + 2 cos(2 \pi n/3)/9.

The details are given in various places. Right now, I am looking
at chapter 15 of A Course in Combinatorics by van Lint and
Wilson.  I hope this helps.  Sorry, I haven't had a good look
at the Smarandache problem that you sent.  I have been
very busy trying to catch up on various responsibilities.

Cecil
===

Confesso que é a primeira vez que pensei sobre tais problemas
e naturalmente não conhecia as técnicas para resolvê-los.

Tendo em vista o recurso às funções geradoras em diversas
aplicações, sugiro que um artigo tratando delas e suas
aplicações - em particular na resolução dessas equações e no cálculo
de somas (para os que sabem, o método do "snake oil method" no livro
do Wilf)  - seja apresentado em algum número da Eureka.

[ ]'s
Luís


-----Mensagem Original-----
De: Luis Lopes <llopes@ensrbr.com.br>
Para: <obm-l@mat.puc-rio.br>
Enviada em: Segunda-feira, 12 de Março de 2001 19:37
Assunto: Re: fatoracao


Sauda,c~oes,

Para resolver o problema da decomposição de N em três
fatores, a solução que o Nicolau apresentou numa hora
tratou de resolver a seguinte equação:

===
O número de soluções naturais da equação a = 2 a1 + a3 é claramente
floor(1 + (a/2)) (aqui floor(x) é o maior inteiro menor ou igual a x).
Assim ...
===

Como resolver tais equações? E se fosse
a = 3 a1 + 2a2 +  a3   ???

E considere também a  equação

===
a = a1 + a2 + a3, where a1 >= a2 >= a3.

By generating functions  or otherwise, one can show that
the number of such solutions  is {(k+3)^2/12}.  where {x} denotes
 the integer nearest x. (pedaço do mail do Rousseau).
===
Qual a técnica para resolver tais equações?

[ ]s,
Luís