%I #25 Feb 08 2021 17:41:14
%S 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,
%T 844,1744,3340,5976,10040,15856,23460,32398,41658,49700,54746,55308,
%U 50788,41944,30782,19788,10948,5096,1932,568,120,16,1,32,144,480,1440,4056
%N 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.
%C Empty external nodes are counted in determining the height of a search tree.
%C T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms. Terms not shown are zero.
%H Alois P. Heinz, <a href="/A335920/b335920.txt">Columns k = 0..10, flattened</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F Sum_{k=0..n} k * T(n,k) = A335921(n).
%F Sum_{n=k..2^k-1} n * T(n,k) = A335922(k).
%e Triangle T(n,k) begins:
%e 1;
%e 1;
%e 2;
%e 1, 4;
%e 6, 8;
%e 6, 20, 16;
%e 4, 40, 56, 32;
%e 1, 68, 152, 144, 64;
%e 94, 376, 480, 352, 128;
%e 114, 844, 1440, 1376, 832, 256;
%e 116, 1744, 4056, 4736, 3712, 1920, 512;
%e ...
%p b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
%p add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
%p end:
%p T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
%p seq(seq(T(n, k), n=k..2^k-1), k=0..6);
%t b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
%t Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
%t T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
%t 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_ *)
%Y Row sums give A000108.
%Y Column sums give A001699.
%Y Main diagonal gives A011782.
%Y T(n+3,n+2) gives A014480.
%Y T(n,max(0,A000523(n)+1)) = A328349(n).
%Y Cf. A073345, A076615, A195581, A244108, A335919 (the same read by rows), A335921, A335922.
%K nonn,tabf
%O 0,3
%A _Alois P. Heinz_, Jun 29 2020