Saturday, November 22, 2008

Prod Sums

The Diophantine r1e1+r2e2+rmem =n can be analyzed as a product of ordinary generating functions as Prod(1/(1-z^(ri),i = 1..m). So there are m generating functions that are multiplied and we are looking at the coefficient of z^n in that product. The solution for this is #{(e1,e2,..,em): r1e1+r2e2+...+rmem = n}. Using this idea several problems can be solved for ex 3x1+3x2+3x3+3x4 = n. Here r1=r2=r3=r4 = 3 and x1=e1, x2=e2, x3=e3, x4=e4. This can be easily solved using composition formula by noting that n = 3k and then binomial(k+3,k).
So what's the correct way to think about this equation r1e1+r2e2+...rmem = n ? These are m generating functions multiplied together and we are looking at the coefficient [z^n] as in the following expression
[z^n] (...+ (z^(r1))e1+...)(...+(z^(r2))e2+...) ... (...+(z^(rm))em+...)
Once understood one can prove a beautiful result that every number has a unique binary representation and that can be generalized for r ary numbers.

0 Comments:

Post a Comment

<< Home

Site Meter