A244108 - OEIS

%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