wu :: forums
« wu :: forums - Reciprocal Product Summation »

Welcome, Guest. Please Login or Register.
Sep 30th, 2022, 4:33pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: SMQ, Icarus, william wu, Grimbal, Eigenray, towr)
   Reciprocal Product Summation
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Reciprocal Product Summation  (Read 3647 times)
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Reciprocal Product Summation  
« on: Jul 13th, 2009, 1:53am »
Quote Quote Modify 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 non-negative integers.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Reciprocal Product Summation  
« Reply #1 on: Jul 13th, 2009, 12:06pm »
Quote Quote Modify Modify

hidden:

This is the coefficient of xn+3 in
( xa+1/(a+1))^3 = [-log(1-x)]3,
...which is listed in sloane as 6|s(n+3,3)|/(n+3)!. Embarassed
 
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
c(n,k)k! xn/n! = [-log(1-x)]k,
which is cleary true for k=0.  Then
c(n,k)k! xn/n!)   xi/i
 = xn   c(n-i,k)k!/((n-i)! * i),
 
so we must show that
 
c(n,k+1)(k+1)! = [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.

Note the inverse results:
hidden:

s(n,k)k! xn/n! = [log(1+x)]k
S(n,k)k! xn/n! = [exp(x)-1]k
« Last Edit: Jul 13th, 2009, 12:07pm by Eigenray » IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Reciprocal Product Summation  
« Reply #2 on: Jul 13th, 2009, 12:41pm »
Quote Quote Modify Modify

That is correct. I found it interesting that the generating functions for powes of ln (1-x) give us stirling numbers!
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Reciprocal Product Summation  
« Reply #3 on: Sep 13th, 2009, 5:30pm »
Quote Quote Modify Modify

Just came across a nicer proof in van Lint & Wilson:
 
1/k! [ log(1+x) ]k is the coefficient of zk in
 
exp( z log(1+x) ) = (1+x)z
 = C(z,n) xn  
 = (z)n/n! xn
 = xn/n! s(n,k)zk
 = zk   s(n,k) xn/n!
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Reciprocal Product Summation  
« Reply #4 on: Sep 14th, 2009, 5:30pm »
Quote Quote Modify Modify

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
c(n,k) xn/n!  =  C(x)k/k!,
where C(x) = (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, so
S(n,k) xn/n! = F(x)k/k!,
where F(x) = n>0  xn/n! = ex-1, since there is 1 way to make an n-set into a non-empty set, for n > 0.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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