cp's OEIS Frontend

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.

%I A335919 #26 Feb 08 2021 17:41:08
%S A335919 1,1,2,1,4,6,8,6,20,16,4,40,56,32,1,68,152,144,64,94,376,480,352,128,
%T A335919 114,844,1440,1376,832,256,116,1744,4056,4736,3712,1920,512,94,3340,
%U A335919 10856,15248,14272,9600,4352,1024,60,5976,27672,47104,50784,40576,24064
%N 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.
%C A335919 Empty external nodes are counted in determining the height of a search tree.
%C A335919 T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms. Terms not shown are zero.
%H A335919 Alois P. Heinz, <a href="/A335919/b335919.txt">Rows n = 0..200, flattened</a>
%H A335919 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>
%H A335919 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A335919 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A335919 Sum_{k=0..n} k * T(n,k) = A335921(n).
%F A335919 Sum_{n=k..2^k-1} n * T(n,k) = A335922(k).
%e A335919 Triangle T(n,k) begins:
%e A335919   1;
%e A335919      1;
%e A335919         2;
%e A335919         1, 4;
%e A335919            6,   8;
%e A335919            6,  20,   16;
%e A335919            4,  40,   56,   32;
%e A335919            1,  68,  152,  144,   64;
%e A335919                94,  376,  480,  352,  128;
%e A335919               114,  844, 1440, 1376,  832,  256;
%e A335919               116, 1744, 4056, 4736, 3712, 1920, 512;
%e A335919   ...
%p A335919 g:= n-> `if`(n=0, 0, ilog2(n)+1):
%p A335919 b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
%p A335919       add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
%p A335919     end:
%p A335919 T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
%p A335919 seq(seq(T(n, k), k=g(n)..n), n=0..12);
%t A335919 g[n_] := If[n == 0, 0, Floor@Log[2, n]+1];
%t A335919 b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
%t A335919      Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
%t A335919 T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
%t A335919 Table[Table[T[n, k], {k, g[n], n}], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Feb 08 2021, after _Alois P. Heinz_ *)
%Y A335919 Row sums give A000108.
%Y A335919 Column sums give A001699.
%Y A335919 Main diagonal gives A011782.
%Y A335919 T(n+3,n+2) gives A014480.
%Y A335919 T(n,max(0,A000523(n)+1)) = A328349(n).
%Y A335919 Cf. A073345, A073429 (another version with 0's), A076615, A195581, A244108, A335920 (the same read by columns), A335921, A335922.
%K A335919 nonn,tabf
%O A335919 0,3
%A A335919 _Alois P. Heinz_, Jun 29 2020