A001858: Asymptotics in Product of Binomial Functionals

Paul D. Hanna pauldhanna at juno.com
Tue May 4 07:11:09 CEST 2004


Perhaps someone would be interested in verifying the following
observation. 
The conjecture involves A001858 (number of forests of labeled trees with
n nodes).
 
Consider the solutions to the binomial functional equation:
 
  f(x,t) = 1 + x*f(x,t)^t
 
These solutions are given by: 
 
  f(x,t)^m = Sum_{n>=0} binomial(n*t+m,n)/(n*t+m)*x^n

  log( f(x,t)) = Sum_{n>=1} binomial(n*t,n)/(n*t)*x^n.
 
Among such solutions are 
  f(x,1)=1/(1-x); f(x,2)=Catalan series; f(x,3)=g.f. for A001764; and
many more. 
 
PRODUCT OF BINOMIAL FUNCTIONALS.  
I was curious as to the behavior of the product of the first n such
functions: 
   
  g(x,n) = Prod_{t=1..n} f(x,t)
 
  log( g(x,n)) = Sum_{t=1,n} Sum_{k>=1} binomial(k*t,k)/(k*t)*x^k 
 
and found the following (apparent) asymptotic behavior:
 
  [x^k] g(x,n) ~ binomial(n,k)*A001858(k) + O(?)
 
where [x^k] g(x,n) denotes the coefficient of x^k in g(x,n), and k<<n.
 
CONJECTURE.
The conjecture is that the following limit exists, 
and that the convergent sequence equals A001858: 
 
  limit_{n-->oo} {[x^k] g(x,n)}/binomial(n,k) = A001858(k)
 
Below I give some empirical results of my PARI program (the convergence
is very slow). 
 
Could someone provide an argument for the convergent sequence to be
A001858? 

HINT... 
One big hint may be that the more general product: 
   
  g(x,n,q) = Prod_{t=1..n} f(x,t)^q
 
seems to have the following asymptotic behavior:
 
  limit_{n-->oo} {[x^k] g(x,n,q)}/binomial(n,k) = k! * [x^k] (e.g.f. of
A001858)^q
 
For example, q=2, the limit is [1,2,6,26,156,1242,...], and we see that: 
  {e.g.f. of [1,2,6,26,156,1242,...]} = {e.g.f. of
[1,1,2,7,38,291,...]}^2.
 
 
Finally, perhaps these results could be generalized to other functions
besides the binomial (1+x)? 
 
Thanks,
Paul
 
-------------------PARI CODE-----------------------
N=10000;
{PRODB(n,k)=prod(m=1,n,sum(i=0,k+1,binomial(m*i+1,i)/(m*i+1)*x^i)+x*O(x^k
))}
for(k=0,10,print(1.0*polcoeff(PRODB(N,k),k)/binomial(N,k),","))
  
---------------RESULTS AT N=10000-----------------
1.000000000000000000000000000,
1.000000000000000000000000000,
2.000200020002000200020002000,
7.002100480102021004260858172,
38.02280936333710915459077011,
291.2911872999482559401985124,
2936.402077034396215325716446,
37038.71595422840427639613680,
563524.0423274664459079824548,
10062675.46629876542321458190,
206536146.7770722924393550118,
 
---------------RESULTS AT N=100000----------------
1.000000000000000000000000000,
1.000000000000000000000000000,
2.000020000200002000020000200,
7.000210004800102002100042601,
38.00228009360333611088354491,
291.0291018720999048236193156,
2932.439840743032599512146934,
36968.76278767183374138484273,
562105.3712897922747938615125,
10030115.29121810216792740365,
205701083.5238411270346478014,
 
---------------RESULTS AT N=500000----------------
1.000000000000000000000000000,
1.000000000000000000000000000,
2.000004000008000016000032000,
7.000042000192000816003360014,
38.00045600374402668817740913,
291.0058200748807992077175102,
2932.087961629624259519203887,
36962.55240110378101687818537,
561979.4701218869759309027114,
10027226.93833294277097036312,
205627041.7154000628322640112, 
 
------------PROPOSED CONVERGENT SEQUENCE------------
ID Number: A001858 
URL:       http://www.research.att.com/projects/OEIS?Anum=A001858

Sequence:  1,1,2,7,38,291,2932,36961,561948,10026505,205608536,
           4767440679,123373203208,3525630110107,110284283006640,
           3748357699560961,137557910094840848,5421179050350334929,
           228359487335194570528

Name:      Number of forests of labeled trees with n nodes.

Formula:   E.g.f.: exp(T - (1/2)T^2), where T=T(x) is Euler's tree
function
(see A000169). - Len Smiley (smiley(AT)math.uaa.alaska.edu), Dec 12 2001

Program:   (PARI)
a(n)=if(n<0,0,sum(m=0,n,sum(j=0,m,binomial(m,j)*binomial(n-1,n-m-j)*n^(n-
m-j)*(m+j)!/(-2)^j)/m!))
-------------------------------------------------------------------------
END





More information about the SeqFan mailing list