Let a(n) be the number of rooted trees with n nodes, as in EIS A000081.

The number of rooted trees with n nodes grows like
b*n^(-3/2)*c^n*(1+O(1/n))
where b and c where given to 100 digits,
by Dirk Kreimer and me, in Section 4.1 of the paper indexed by

       http://xxx.lanl.gov/abs/hep-th/9810087

Christian Bower told me that b and c are called Otter constants.
Steve Finch mentions them in

       http://pauillac.inria.fr/algo/bsolve/otter/otter.html

I now have them to (I hope) 1800 digits:

c=
2.9557652856519949747148175241231945883754923046635965953504724789059647331395
749510866682836765813525306643713553062216140804716398086805528130252344795910
656450830094857724237733381960025839469497653106826655718270860682985427979012
044927318264877923165543441886049809053386951478126324251699809842476454117022
914498182207731305326691488822870879884674225079006972041559262826724346603865
511395549974595716724047293015669814373335868696232253972389009814080091539603
396562978537734246881433388503598376598762533529229147960470508680388449072017
852231661330812159293100901747448705408544599945314487758953479948204037497159
912479440501273250666044628064269870751284766131175952434919430350883603512578
989841518484797085223412953014018440496271680305050463592540513181033634182650
672066046380962799286758918257087669461349069339268320138893997266074178959247
586625205304377695494726802194622430816490355172525009444586418370221450429689
312742148243751820531421791396400211513114551580559206012994389002996432708915
094736117842404681882631543798228701299640222254254171936454319388908744845163
971249113539277459762993560177200108997444778629789111107961642283445260740253
854188508679691395461632459569732978287298742382144611656482195846528648947556
777368528640152334661600050980078324740613894003120675551874335356255280134247
326076167392305893027999116890124478263211972769332046786910115199877285353282
485397365366918738443264829773210413827145948737380235150426049008766459808935
445371969044928033412737087505186653313369634847150425719535240970539214056462
298983378711892653117304583435970188646592828031256172924819550419573417519525
259109945997412651726668095720265040399971791357211649473217196215499807167208
556195963320654326682124480373471898209405271292572318272871372593299040607263
2203163

b=
0.4399240125710253040409033914345447647980854079401198576534935450226354004204
764605379862197779782334994096008928808607036130355278681239749015268137132783
467102127261751692624250709808021922587739120314486821277158285717016795641177
677796963467835863723521783476332803083736800135718589958044083591844847211499
996000615221798590441691054151409780137383964731714853212457499289452244928156
301005028549157077215977884172726005835139347180738571273667131314612858187105
334513170110629127806829109892427377844327293945018896994701919257086356528212
554994000401774480092423190965687535495927594980046045278792234517577644204756
654168870757450444063848820314986484950509103588119722448685719863403777710132
443325486489193017398380583860118430919190921399032405063260997988226150198932
373622403048147635203926348372806704519566431462304864840807607315220059945574
945297542308458286204529069652562161706299969371641042175509405555507691791665
244362110492020819889911151842244689414438609829231944305663742579673934575380
325258199790411237627941682770758144141536820339526977682044033362876974649402
156107763245577107479989155552572491825972659453719966971034676095695103675051
379477004148946537388270112634948984729989625313547946847772355434646483026307
325512425150212801880973366030209299124240396402160323228944995865551591598011
823671793302398650263547656258397638336283300436861723404377243985517354410589
634435357495048623479461976371092548054128066955687636077606748976499761004208
913674741054947171926000591745909960214469222070978300538930490791285831553674
226320874200951043551154125229159062874524651774513877546312433313772121021865
696087995229492427619388878358743521451313327399021090479125009989521989574370
531780125492046427344836473474571867583751900266990801942402494933824022758149
44815778

It is suspected that they do relate to other constants,
beyond tree enumeration.


This constant was computed by David Broadhurst in November 1999.


ID Number: A000081 (Formerly M1180 and N0454)
Sequence:  1,1,1,2,4,9,20,48,115,286,719,1842,4766,12486,32973,87811,
           235381,634847,1721159,4688676,12826228,35221832,97055181,
           268282855,743724984,2067174645,5759636510,16083734329,
           45007066269,126186554308,354426847597
Name:      Rooted trees with n nodes (or connected functions with a fixed point).
References J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958,
           p. 138.
           F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
           N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 42, 49.
           D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, pp. 386-88.
           F. Bergeron et al., Combinatorial Species and Tree-Like Structures,
           Camb. 1998, p. 279.
           R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
Links:     Index entries for sequences related to rooted trees
           Index entries for sequences related to trees
           Index entries for "core" sequences
Formula:   G.f. A(x) = x exp(A(x)+A(x^2)/2+A(x^3)/3+A(x^4)/4+...)
           Also A(x) = Sum_{n>=1} a(n)*x^n = x / Product_{n>=1}
           (1-x^n)^a(n).
           Recurrence: a(n+1) = (1/n) * sum_{k=1..n} ( sum_{d|k} d*a(d) ) *
           a(n-k+1).
Example:   There are 4 rooted trees with 4 nodes (X is the root):
           .x..................
           .x..x.x..x..........
           .x...x...x.x..x.x.x.
           .X...X....X.....X...
Maple:     a:=[ 1,1 ]; for n from 3 to 30 do x*mul( (1-x^i)^(-a[ i ]), i=1..n-1);
           series(%,x,n+1); b:=coeff(%,x,n); a:=[ op(a),b ]; od: a;
           T:=series(add(a[ i ]*x^i,i=1..30),x,50);
Mma:       s[ n_,k_ ]:=s[ n,k ]=a[ n+1-k ]+If[ n<2k,0,s[ n-k,k ] ]; a[ 1 ]=1;a[ n_
           ]:=a[ n ]=Sum[ a[ i ]s[ n-1,i ]i,{i,1,n-1} ]/(n-1); Table[ a[ i
           ],{i,1,30} ] (from Robert A. Russell (russell@post.harvard.edu)
See also:  Cf. A000041, A000055, A000169, A005200.
Keywords:  nonn,easy,core,nice
Offset:    0
Author(s): njas


































# This is the electronic signature for Plouffe's Inverter        #
# Ceci est la signature électronique pour l'Inverseur de Plouffe #
# Copyright : Simon Plouffe/Plouffe's Inverter (c) 1986.         #
# http://www.lacim.uqam.ca/pi                                    #