server down [was: Re: G.f. for a(n) = ...]

[Joerg Arndt]

David Wilson wrote:

> For A006906, could a(n+1)/a(n) be approaching a limit?

> Like maybe 3^(1/3)?

The limit does not exist.  The generating function for a(n) is

                        n                 1
    A(z)  =  SUM  a(n) z   =  PRODUCT --------                          (0)
                                             n
             n>=0              n>=1   1 - n z

for small z.

The product on the right is defined for all z with |z|<1 except for
singularities at  r n^(-1/n),  where n>1 is an integer and r is an
n-th root of 1.  These are all poles of order 1, except for poles of
order 2 at 2^(-1/2) = 4^(-1/4) and its negative.  The singularities with
the smallest absolute value occur for n=3; hence equation (0) is true
for  |z| < 3^(-1/3).

So

              1              A(z)
    a(n) = ------  INTEGRAL  ---- dz                                    (1)
           2 pi i     C       n+1
                             z

where the integral is around a circle centered at 0, with radius less
than 3^(-1/3).  To estimate this, we can expand the circle, in order
to avoid the singularity at z=0.  Increasing the radius of the circle
beyond 3^(-1/3) changes the value of the integral by the sum of the
residues of the integrand at the 3 singularities of absolute value
3^(-1/3):

              1              A(z)
    a(n) = ------  INTEGRAL  ---- dz -                                  (2)
           2 pi i     D       n+1
                             z

                 (R(3^(-1/3)) + R(w 3^(-1/3)) + R(w^2 3^(-1/3))

where D is a circle of radius r, with  3^(-1/3) < r < 2^(-1/2),
w = (-1 + sqrt(3) i)/2  and R(z0) is the residue of  A(z)/z^(n+1)  at z0.

On D, the integrand is  o(3^(n/3)).  Since the length of D is independent
of n, the integral is also  o(3^(n/3)).  This will turn out to be smaller
than the sum of the residues, so we can ignore it if we just want an
asymptotic value for a(n).  (For a more accurate estimate, we could
expand the circle further, taking into account the residues at the
other singularities.)

For each of the 3 relevant singularities z0 (i.e. the cube roots of 1/3),
we have

           3        3
    1 - 3 z  = -3 (z  - 1/3) = -3 (z-z0) (z-w z0) (z-w^2 z0)

so
                               1              1
    R(z0) =   lim   (z - z0) ---- PRODUCT --------
            z -> z0           n+1  n>=1          n
                             z            1 - n z
                                 
              1                  1                           1
          = -----  ----------------------------  PRODUCT ---------  
              n+1  -3 (z0 - w z0) (z0 - w^2 z0)   n>=1           n
            z0                                    n!=3   1 - n z0
                                 
               -1                 1
          = --------  PRODUCT ---------  
                n+3    n>=1           n
            9 z0       n!=3   1 - n z0

I don't know if the products on the right can be evaluated in closed
form, but they can be computed numerically:

For  z0 = 3^(-1/3),  the product is

    p0 ~ 293769.1124891011564831268878467064420586

For  z0 = w 3^(-1/3)  it's

    p1 ~ 0.3452412325801026189128598712870317087930 +

         0.0293627889575200300383689071994562320564 i

For  z0 = w^2 3^(-1/3)  it's

    p2 ~ 0.3452412325801026189128598712870317087930 -

         0.0293627889575200300383689071994562320564 i

So

       -1/3      n/3 - 1
    R(3    ) = -3        p0

         -1/3      n/3 - 1  2n
    R(w 3    ) = -3        w   p1

       2  -1/3      n/3 - 1  n
    R(w  3    ) = -3        w  p2

Substituting these values in (2) gives an asymptotic formula for a(n):

            n/3 - 1        2n       n
    a(n) ~ 3        (p0 + w   p1 + w  p2)
                                                                        (3)
            n/3
         = 3    c(n mod 3)

where

    c(0) = (p0 + p1 + p2)/3       ~ 97923.26765718877222945490452214967204067

    c(1) = (p0 + w^2 p1 + w p2)/3 ~ 97922.93936857030090919621139317470903737

    c(2) = (p0 + w p1 + w^2 p2)/3 ~ 97922.90546334208334447577193138206098055

Because these 3 values are different, the sequence of ratios a(n+1)/a(n) has
3 different limit points, which differ slightly from 3^(1/3).

For anyone who wants to check this computationally, here's some Mathematica
code to compute a(n); a[n,k] is the sum of the products of all partitions
of n into parts <= k.

a[0,0]=1;
a[n_,0]:=0;
a[n_,k_]:=If[k>n, a[n,n], a[n,k] = a[n,k-1] + k a[n-k,k] ];
a[n_]:=a[n,n];

Dean Hickerson
dean at math.ucdavis.edu