The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A127152 Sum of the Strahler numbers of all full binary trees with n internal vertices. 1
 1, 2, 6, 20, 68, 232, 795, 2746, 9586, 33860, 121014, 437252, 1595324, 5869528, 21748408, 81060688, 303606864, 1141733024, 4307943856, 16300004128, 61819681632, 234929133504, 894335405016, 3409775718096, 13017932402704 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS The Strahler number of a full binary tree is obtained by the following process: label the external vertices (i.e., leaves) by 1 and label an internal vertex recursively as a function of the labels of its sons: if they are distinct, take the largest of the two and if they are equal, increase them by 1. The Strahler number is the label of the root. LINKS Table of n, a(n) for n=1..25. P. Flajolet, J.-C. Raoult, and J. Vuillemin, The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125. J. Francon, Sur le nombre de registres nécessaires à l'évaluation d'une expression arithmétique, RAIRO Inform. Theor, 18, 1984, 355-364. Xavier Gérard Viennot, A Strahler bijection between Dyck paths and planar trees, FPSAC (Barcelona, 1999), Discrete Math. 246 (2002), no. 1-3, 317-329. MR1887493 (2003b:05013). D. Zeilberger, A bijection from ordered trees to binary trees that sends the pruning order to the Strahler number, Discrete Math., 82, 1990, 89-92. FORMULA a(n) = Sum_{k>=1} k*A127151(n,k). G.f.: Sum_{k>=1} k*F[k], where F[k] = F[k](z) (k=1,2,...) are defined recursively by F[k] = zF[k-1]^2 + 2zF[k](F[0] + F[1] + ... + F[k-1]), with F[0]=1. MAPLE F[0]:=1: for k from 1 to 4 do F[k]:=simplify(z*F[k-1]^2/(1-2*z*sum(F[j], j=0..k-1))) od: g:=add(j*F[j], j=1..4): gser:=series(g, z=0, 32): seq(coeff(gser, z, n), n=1..28); MATHEMATICA f[0]=1; For[k=1, k <= 4, k++, f[k] = Simplify[z*f[k-1]^2/(1-2*z*Sum[f[j], {j, 0, k-1}])]]; g=Sum[j*f[j], {j, 1, 4}]; gser=Series[g, {z, 0, 25}]; CoefficientList[gser, z] // Rest (* Jean-François Alcover, Nov 22 2012, translated from Maple *) CROSSREFS Cf. A127151. Sequence in context: A231057 A295873 A006012 * A279557 A363182 A150120 Adjacent sequences: A127149 A127150 A127151 * A127153 A127154 A127155 KEYWORD nonn AUTHOR Emeric Deutsch, Jan 06 2007 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 15 14:37 EDT 2024. Contains 371689 sequences. (Running on oeis4.)