wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Reciprocal Product Summation
        
(Message started by: Aryabhatta on Jul 13^th, 2009, 1:53am)

Title: Reciprocal Product Summation
Post by Aryabhatta on Jul 13^th, 2009, 1:53am

Let N be given positive integer. Find the sum:

Sigma ((a+1) (b+1) (c+1))^-1

where the sum ranges over the set of solutions of

a + b + c = N, a, b, c being non-negative integers.

Title: Re: Reciprocal Product Summation
Post by Eigenray on Jul 13^th, 2009, 12:06pm

[hideb]
This is the coefficient of xⁿ⁺³ in
(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif x^a+1/(a+1))^3 = [-log(1-x)]³,
...which is listed in sloane as 6|s(n+3,3)|/(n+3)!. :-[

Discovering this result may be one thing, but proving it isn't so hard.
Let c(n,k) be the number of permutations of an n-element set with k cycles.
Inductively, suppose
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n,k)k! xⁿ/n! = [-log(1-x)]^k,
which is cleary true for k=0. Then
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n,k)k! xⁿ/n!) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif xⁱ/i
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif xⁿ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n-i,k)k!/((n-i)! * i),

so we must show that

c(n,k+1)(k+1)! = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif [n(n-1)...(n-i-1)/i]*c(n-i,k)k!

The left side counts the number of ways to permute n elements with (k+1) cycles, and then order the cycles. But there are n(n-1)...(n-i-1)/i ways the first cycle can have length i, and then c(n-i,k)k! ways to pick the remaining k cycles.
[/hideb]
Note the inverse results:
[hideb]
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif s(n,k)k! xⁿ/n! = [log(1+x)]^k
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S(n,k)k! xⁿ/n! = [exp(x)-1]^k
[/hideb]

Title: Re: Reciprocal Product Summation
Post by Aryabhatta on Jul 13^th, 2009, 12:41pm

That is correct. I found it interesting that the generating functions for powes of ln (1-x) give us stirling numbers!

Title: Re: Reciprocal Product Summation
Post by Eigenray on Sep 13^th, 2009, 5:30pm

Just came across a nicer proof in van Lint & Wilson:

1/k! [ log(1+x) ]^k is the coefficient of z^k in

exp( z log(1+x) ) = (1+x)^z
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif C(z,n) xⁿ
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (z)_n/n! xⁿ
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif xⁿ/n! http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif s(n,k)z^k
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif z^k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif s(n,k) xⁿ/n!

Title: Re: Reciprocal Product Summation
Post by Eigenray on Sep 14^th, 2009, 5:30pm

Just realized that in the context of Joyal species these are both one-liners:

c(n,k) counts the number of ways to break an n-set into k (non-empty) cycles, so
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n,k) xⁿ/n! = C(x)^k/k!,
where C(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (n-1)! xⁿ/n! = -log(1-x), since there are (n-1)! ways make an n-set into a single cycle.

S(n,k) counts the number of ways to break an n-set into k non-empty sets, so
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S(n,k) xⁿ/n! = F(x)^k/k!,
where F(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 xⁿ/n! = e^x-1, since there is 1 way to make an n-set into a non-empty set, for n > 0.