[seqfan] Re: GF for A083710 Number of partitions [...]

Richard Mathar mathar at strw.leidenuniv.nl
Thu Jun 11 21:19:46 CEST 2009

In http://list.seqfan.eu/pipermail/seqfan/2009-June/001612.html we read

njas> N. J. A. Sloane njas at research.att.com
njas> Mon Jun 8 12:14:14 CEST 2009
njas> Gary Adamson's comment:
njas> %C A083710 Equals left border of triangle A137587 starting (1, 2, 3, 5, 6, 11,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 27 2008 
njas> is equivalent to the formula
njas>    A083710(n) = Sum_{d|n} p(d-1)
njas> where p(i) = no. of partitions of i. 
njas> Hence A083710 has g.f. Sum_{d>=1} p(d-1)*x^d/(1-x^d)
    or actually 1+sum_{d>=1} p(d-1)*x^d/(1-x^d) .............(1)
    to include a(0)=1 .
njas> (which is not what Joerg conjectured, however).
njas> Neil

The two forms of the generating function turn out to be equivalent. Details
to round this up:

Joerg's format is
gf(JA) = 1+sum_{n>=1}  x^n/eta(x^n)   ................(2)
where eta(x^n) = sum_{i=0..infinity} A010815(i)*x^(i*n)
 = (1-x)*(1-x^(2n))*(1-x^(3n))*(1-x^(4n))*(1-x^(5n))*....

 From the convolution property (first comment in A010815) we have
gf(A000041)*gf(A010815) = 1..................(3)
where the two generating functions are defined by
gf(A000041) = sum_{i=0..infinity} A000041(i)*x^i ;
gf(A010815) = sum_{j=0..infinity} A010815(j)*x^j ;
so the long write-up of (3) is
sum_{i=0..infinity} A000041(i)*x^i * sum_{j=0..infinity} A010815(j)*x^j = 1
therefore by division
1/ sum_{j=0..infinity} A010815(j)*x^j = sum_{i=0..infinity} A000041(i)*x^i
and by the substitution x->x^n
1/ sum_{j=0..infinity} A010815(j)*x^(j*n) = sum_{i=0..infinity} A000041(i)*x^(i*n)

Insertion into equation (2) is
gf(JA) = 1+sum_{n>=1}  x^n * sum_{i=0..infinity} A000041(i)*x^(i*n)
       = 1+sum_{n>=1}  sum_{i=0..infinity} A000041(i)*x^((i+1)*n)
       = 1+sum_{n>=1}  sum_{l=1..infinity} A000041(l-1)*x^(l*n)
Interchange of the two summations and insertion of the geometric series standard
       sum_{n>=1} x^(l*n) = x^l/(1-x^l)
gf(JA) = 1+ sum_{l=1..infinity} A000041(l-1)*x^l/(1-x^l)
which is (1), the result from Gary's reference.

More information about the SeqFan mailing list