OFFSET
0,3
COMMENTS
Empty external nodes are counted in determining the height of a search tree.
T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms. Terms not shown are zero.
LINKS
EXAMPLE
Triangle T(n,k) begins:
1;
1;
2;
1, 4;
6, 8;
6, 20, 16;
4, 40, 56, 32;
1, 68, 152, 144, 64;
94, 376, 480, 352, 128;
114, 844, 1440, 1376, 832, 256;
116, 1744, 4056, 4736, 3712, 1920, 512;
...
MAPLE
g:= n-> `if`(n=0, 0, ilog2(n)+1):
b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
seq(seq(T(n, k), k=g(n)..n), n=0..12);
MATHEMATICA
g[n_] := If[n == 0, 0, Floor@Log[2, n]+1];
b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
Table[Table[T[n, k], {k, g[n], n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 08 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Jun 29 2020
STATUS
approved