[go: up one dir, main page]

login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A335919
Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), n>=0, max(0,floor(log_2(n))+1)<=k<=n, read by rows.
6
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, 94, 3340, 10856, 15248, 14272, 9600, 4352, 1024, 60, 5976, 27672, 47104, 50784, 40576, 24064
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.
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
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
Row sums give A000108.
Column sums give A001699.
Main diagonal gives A011782.
T(n+3,n+2) gives A014480.
T(n,max(0,A000523(n)+1)) = A328349(n).
Cf. A073345, A073429 (another version with 0's), A076615, A195581, A244108, A335920 (the same read by columns), A335921, A335922.
Sequence in context: A262599 A160016 A245089 * A296340 A048213 A338746
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Jun 29 2020
STATUS
approved