Author 
Topic: Reciprocal Product Summation (Read 3647 times) 

Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Reciprocal Product Summation
« on: Jul 13^{th}, 2009, 1:53am » 
Quote Modify

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.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Reciprocal Product Summation
« Reply #1 on: Jul 13^{th}, 2009, 12:06pm » 
Quote Modify

hidden:  This is the coefficient of x^{n+3} in ( 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 c(n,k)k! x^{n}/n! = [log(1x)]^{k}, which is cleary true for k=0. Then c(n,k)k! x^{n}/n!) x^{i}/i = x^{n} c(ni,k)k!/((ni)! * i), so we must show that c(n,k+1)(k+1)! = [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.  Note the inverse results: hidden:  s(n,k)k! x^{n}/n! = [log(1+x)]^{k} S(n,k)k! x^{n}/n! = [exp(x)1]^{k} 

« Last Edit: Jul 13^{th}, 2009, 12:07pm by Eigenray » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Reciprocal Product Summation
« Reply #2 on: Jul 13^{th}, 2009, 12:41pm » 
Quote Modify

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


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Reciprocal Product Summation
« Reply #3 on: Sep 13^{th}, 2009, 5:30pm » 
Quote Modify

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} = C(z,n) x^{n} = (z)_{n}/n! x^{n} = x^{n}/n! s(n,k)z^{k} = z^{k} s(n,k) x^{n}/n!


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Reciprocal Product Summation
« Reply #4 on: Sep 14^{th}, 2009, 5:30pm » 
Quote Modify

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 c(n,k) x^{n}/n! = C(x)^{k}/k!, where C(x) = (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 S(n,k) x^{n}/n! = F(x)^{k}/k!, where F(x) = _{n>0} x^{n}/n! = e^{x}1, since there is 1 way to make an nset into a nonempty set, for n > 0.


IP Logged 



