login
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
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
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.
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).
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jan 06 2007
STATUS
approved