Date: Sun, 19 Aug 2007 11:38:09 -0700 From: Dean Hickerson (dean(AT)math.ucdavis.edu) Comments on A006906 David Wilson wrote: > For A006906, could a(n+1)/a(n) be approaching a limit? 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 ------------------------------------------------------- From: Paul D. Hanna (pauldhanna(AT)juno.com) Is it not correct to state: (*) the limit of a(n+3)/a(n) exists and is equal to 3. This can still be true and the limit of (*) unique even though a(n+1)/a(n) takes on 3 different values - as long as the product of these 3 limit points equals 3. ------------------------------------------------------- Date: Sun, 19 Aug 2007 17:36:16 -0700 From: Dean Hickerson Yes, that follows from my equation (3), since n mod 3 = (n+3) mod 3. Dean Hickerson -------------------------------------------------------