%I #67 Jul 07 2020 20:20:38
%S 1,1,2,2,4,16,40,80,80,8,64,400,2240,11360,55040,253440,1056000,
%T 3801600,10982400,21964800,21964800,16,208,2048,18816,168768,1508032,
%U 13501312,121362560,1099169280,10049994240,92644597760,857213660160,7907423180800,72155129446400
%N Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; 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.
%H Alois P. Heinz, <a href="/A244108/b244108.txt">Columns k = 0..9, 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) = A316944(n).
%F Sum_{k=n..2^n-1} k * T(k,n) = A317012(n).
%e Triangle T(n,k) begins:
%e : 1;
%e : 1;
%e : 2;
%e : 2, 4;
%e : 16, 8;
%e : 40, 64, 16;
%e : 80, 400, 208, 32;
%e : 80, 2240, 2048, 608, 64;
%e : 11360, 18816, 8352, 1664, 128;
%e : 55040, 168768, 104448, 30016, 4352, 256;
%e : 253440, 1508032, 1277568, 479040, 99200, 11008, 512;
%p b:= proc(n, k) option remember; `if`(n<2, `if`(k<n, 0, 1),
%p add(binomial(n-1, r)*b(r, k-1)*b(n-1-r, k-1), r=0..n-1))
%p end:
%p T:= (n, k)-> b(n, k)-b(n, k-1):
%p seq(seq(T(n, k), n=k..2^k-1), k=0..5);
%t b[n_, k_] := b[n, k] = If[n<2, If[k<n, 0, 1], Sum[Binomial[n-1, r]*b[r, k-1]*b[n-1-r, k-1], {r, 0, n-1}]]; T[n_, k_] := b[n, k] - b[n, k-1]; Table[T[n, k], {k, 0, 5}, {n, k, 2^k-1}] // Flatten (* _Jean-François Alcover_, Feb 19 2017, translated from Maple *)
%Y Row sums give A000142.
%Y Column sums give A227822.
%Y Main diagonal gives A011782, lower diagonal gives A076616.
%Y T(n,A000523(n)+1) = A076615(n).
%Y T(2^n-1,n) = A056972(n).
%Y T(2n,n) = A265846(n).
%Y Cf. A195581 (the same read by rows), A195582, A195583, A316944, A317012.
%K nonn,tabf
%O 0,3
%A _Alois P. Heinz_, Dec 21 2015