|
|
A335920
|
|
Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.
|
|
6
|
|
|
1, 1, 2, 1, 4, 6, 6, 4, 1, 8, 20, 40, 68, 94, 114, 116, 94, 60, 28, 8, 1, 16, 56, 152, 376, 844, 1744, 3340, 5976, 10040, 15856, 23460, 32398, 41658, 49700, 54746, 55308, 50788, 41944, 30782, 19788, 10948, 5096, 1932, 568, 120, 16, 1, 32, 144, 480, 1440, 4056
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
Sum_{k=0..n} k * T(n,k) = A335921(n).
Sum_{n=k..2^k-1} n * T(n,k) = A335922(k).
|
|
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
|
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), n=k..2^k-1), k=0..6);
|
|
MATHEMATICA
|
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];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|