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.
Row n has floor(log_2(n+1)) terms.
Row sums yield the Catalan numbers (A000108).
Sum_{k>=1} k*T(n,k) = A127152(n).
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.
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
The column g.f. 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]), where F[0]=1. For example, F[1][z]=z/(1-2z); F[2](z) = z^3/[(1-2z)(1-4z+2z^2)].
EXAMPLE
Triangle starts:
1;
2;
4, 1;
8, 6;
16, 26;
32, 100;
64, 364, 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: for k from 1 to 4 do Fser[k]:=series(F[k], z=0, 30) od: T:=(n, k)->coeff(Fser[k], z, n): for n from 1 to 18 do seq(T(n, k), k=1..floor(simplify(log[2](n+1)))) od; # yields sequence in triangular form
MATHEMATICA
max = 17; f[0] = 1; f[k_] := f[k] = Simplify[z*(f[k-1]^2/(1 - 2*z*Sum[f[j], {j, 0, k-1}]))]; col[k_] := CoefficientList[ Series[f[k], {z, 0, max}], z]; Flatten[ Drop[ Transpose[ DeleteCases[ Table[ col[k], {k, 1, Floor[Log[2, max]]}], {}]] //. {n__, 0} -> {n}, 1]] (* Jean-François Alcover, Oct 05 2011 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jan 06 2007
STATUS
approved