

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 nonnegative integers. 

Title: Re: Reciprocal Product Summation Post by Eigenray on Jul 13^{th}, 2009, 12:06pm [hideb] This is the coefficient of x^{n+3} in (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif x^{a+1}/(a+1))^3 = [log(1x)]^{3}, ...which is listed in sloane as 6s(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 nelement set with k cycles. Inductively, suppose http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n,k)k! x^{n}/n! = [log(1x)]^{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}/n!) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif x^{i}/i = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif x^{n} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(ni,k)k!/((ni)! * i), so we must show that c(n,k+1)(k+1)! = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif [n(n1)...(ni1)/i]*c(ni,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(n1)...(ni1)/i ways the first cycle can have length i, and then c(ni,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}/n! = [log(1+x)]^{k} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S(n,k)k! x^{n}/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 (1x) 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^{n} = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (z)_{n}/n! x^{n} = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif x^{n}/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}/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 oneliners: c(n,k) counts the number of ways to break an nset into k (nonempty) cycles, so http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c(n,k) x^{n}/n! = C(x)^{k}/k!, where C(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (n1)! x^{n}/n! = log(1x), since there are (n1)! ways make an nset into a single cycle. S(n,k) counts the number of ways to break an nset into k nonempty sets, so http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S(n,k) x^{n}/n! = F(x)^{k}/k!, where F(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{n>0} x^{n}/n! = e^{x}1, since there is 1 way to make an nset into a nonempty set, for n > 0. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 