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.

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

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, Columns k = 0..10, 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

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];
Table[Table[T[n, k], {n, k, 2^k - 1}], {k, 0, 6}] // 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, A076615, A195581, A244108, A335919 (the same read by rows), A335921, A335922.

Sequence in context: A006265 A131452 A359898 * A111104 A026190 A262599

Adjacent sequences: A335917 A335918 A335919 * A335921 A335922 A335923

Keyword

nonn,tabf

Author

Alois P. Heinz, Jun 29 2020

Status

approved