``` 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 13th, 2009, 1:53am) ``` Title: Reciprocal Product Summation Post by Aryabhatta on Jul 13th, 2009, 1:53am Let N be given positive integer. Find the sum:Sigma  ((a+1) (b+1) (c+1))-1where the sum ranges over the set of solutions ofa + b + c = N, a, b, c being non-negative integers. Title: Re: Reciprocal Product Summation Post by Eigenray on Jul 13th, 2009, 12:06pm [hideb]This is the coefficient of xn+3 in(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif xa+1/(a+1))^3 = [-log(1-x)]3,...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, supposehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n,k)k! xn/n! = [-log(1-x)]k,which is cleary true for k=0.  Thenhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n,k)k! xn/n!)  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif xi/i = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif xn  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n-i,k)k!/((n-i)! * i),so we must show thatc(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! xn/n! = [log(1+x)]khttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S(n,k)k! xn/n! = [exp(x)-1]k[/hideb] Title: Re: Reciprocal Product Summation Post by Aryabhatta on Jul 13th, 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 13th, 2009, 5:30pm Just came across a nicer proof in van Lint & Wilson:1/k! [ log(1+x) ]k is the coefficient of zk inexp( z log(1+x) ) = (1+x)z = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif C(z,n) xn = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (z)n/n! xn = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif xn/n! http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif s(n,k)zk = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif zk  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif s(n,k) xn/n! Title: Re: Reciprocal Product Summation Post by Eigenray on Sep 14th, 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, sohttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n,k) xn/n!  =  C(x)k/k!,where C(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (n-1)! xn/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, sohttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S(n,k) xn/n! = F(x)k/k!,where F(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifn>0  xn/n! = ex-1, since there is 1 way to make an n-set into a non-empty set, for n > 0. Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board