A127152 Sum of the Strahler numbers of all full binary trees with n internal vertices.

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

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