login
A127151
Triangle read by rows: T(n,k) is the number of full binary trees with n internal vertices and Strahler number k.
1
1, 2, 4, 1, 8, 6, 16, 26, 32, 100, 64, 364, 1, 128, 1288, 14, 256, 4488, 118, 512, 15504, 780, 1024, 53296, 4466, 2048, 182688, 23276, 4096, 625184, 113620, 8192, 2137408, 528840, 16384, 7303360, 2375100, 1, 32768, 24946816, 10378056, 30, 65536
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.
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
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
Sequence in context: A345881 A372868 A091894 * A193034 A254179 A328641
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jan 06 2007
STATUS
approved