A127151 Triangle read by rows: T(n,k) is the number of full binary trees with n internal vertices and Strahler number k.

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

Table of n, a(n) for n=1..43.

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

Cf. A000108, A127152.

Sequence in context: A257794 A345881 A091894 * A193034 A254179 A328641

Adjacent sequences: A127148 A127149 A127150 * A127152 A127153 A127154

Keyword

nonn,tabf

Author

Emeric Deutsch, Jan 06 2007

Status

approved