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.

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.

Links

Alois P. Heinz, Rows n = 0..200, flattened

Wikipedia, Binary search tree

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

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

Adjacent sequences: A335916 A335917 A335918 * A335920 A335921 A335922

Keyword

nonn,tabf

Author

Alois P. Heinz, Jun 29 2020

Status

approved