The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #17 Jul 22 2017 13:43:43
%S 1,2,6,20,68,232,795,2746,9586,33860,121014,437252,1595324,5869528,
%T 21748408,81060688,303606864,1141733024,4307943856,16300004128,
%U 61819681632,234929133504,894335405016,3409775718096,13017932402704
%N Sum of the Strahler numbers of all full binary trees with n internal vertices.
%C 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.
%H P. Flajolet, J.-C. Raoult, and J. Vuillemin, <a href="http://dx.doi.org/10.1016/0304-3975(79)90009-4">The number of registers required for evaluating arithmetic expressions</a>, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.
%H J. Francon, <a href="https://doi.org/10.1051/ita/1984180403551">Sur le nombre de registres nécessaires à l'évaluation d'une expression arithmétique</a>, RAIRO Inform. Theor, 18, 1984, 355-364.
%H Xavier Gérard Viennot, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00265-5">A Strahler bijection between Dyck paths and planar trees</a>, FPSAC (Barcelona, 1999), Discrete Math. 246 (2002), no. 1-3, 317-329. MR1887493 (2003b:05013).
%H D. Zeilberger, <a href="https://doi.org/10.1016/0012-365X(90)90047-L">A bijection from ordered trees to binary trees that sends the pruning order to the Strahler number</a>, Discrete Math., 82, 1990, 89-92.
%F a(n) = Sum_{k>=1} k*A127151(n,k).
%F 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.
%p 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);
%t 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 *)
%Y Cf. A127151.
%K nonn
%O 1,2
%A _Emeric Deutsch_, Jan 06 2007