|
Search: id:A127152
|
|
|
| A127152 |
|
Sum of the Strahler numbers of all full binary trees with n internal vertices. 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. |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
a(n)=Sum(k*A127151(n,k),k>=1).
|
|
REFERENCES
|
P. Flajolet, J.C. Raoult, and J. Vuillemin, The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci. 9, 1979, 99-125.
J. Francon, Sur le nombre de registres necessaires a l'evaluation d'une expression arithmetique, RAIRO Inform. Theor, 18, 1984, 355-364.
X.G. Viennot, A Strahler bijection between Dyck paths and planar trees, Discrete Math., 246, 2002, 317-329. 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
|
G.f.=Sum(k*F[k],k=1..infinity), 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);
|
|
CROSSREFS
|
Cf. A127151.
Sequence in context: A027063 A027065 A006012 this_sequence A082679 A094854 A026029
Adjacent sequences: A127149 A127150 A127151 this_sequence A127153 A127154 A127155
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 06 2007
|
|
|
Search completed in 0.002 seconds
|
