cp's OEIS Frontend

A244108 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.

%I A244108 #67 Jul 07 2020 20:20:38
%S A244108 1,1,2,2,4,16,40,80,80,8,64,400,2240,11360,55040,253440,1056000,
%T A244108 3801600,10982400,21964800,21964800,16,208,2048,18816,168768,1508032,
%U A244108 13501312,121362560,1099169280,10049994240,92644597760,857213660160,7907423180800,72155129446400
%N A244108 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 A244108 Empty external nodes are counted in determining the height of a search tree.
%H A244108 Alois P. Heinz, <a href="/A244108/b244108.txt">Columns k = 0..9, flattened</a>
%H A244108 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>
%H A244108 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A244108 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A244108 Sum_{k=0..n} k * T(n,k) = A316944(n).
%F A244108 Sum_{k=n..2^n-1} k * T(k,n) = A317012(n).
%e A244108 Triangle T(n,k) begins:
%e A244108 : 1;
%e A244108 :    1;
%e A244108 :       2;
%e A244108 :       2,  4;
%e A244108 :          16,      8;
%e A244108 :          40,     64,      16;
%e A244108 :          80,    400,     208,      32;
%e A244108 :          80,   2240,    2048,     608,     64;
%e A244108 :               11360,   18816,    8352,   1664,   128;
%e A244108 :               55040,  168768,  104448,  30016,  4352,   256;
%e A244108 :              253440, 1508032, 1277568, 479040, 99200, 11008, 512;
%p A244108 b:= proc(n, k) option remember; `if`(n<2, `if`(k<n, 0, 1),
%p A244108       add(binomial(n-1, r)*b(r, k-1)*b(n-1-r, k-1), r=0..n-1))
%p A244108     end:
%p A244108 T:= (n, k)-> b(n, k)-b(n, k-1):
%p A244108 seq(seq(T(n, k), n=k..2^k-1), k=0..5);
%t A244108 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 A244108 Row sums give A000142.
%Y A244108 Column sums give A227822.
%Y A244108 Main diagonal gives A011782, lower diagonal gives A076616.
%Y A244108 T(n,A000523(n)+1) = A076615(n).
%Y A244108 T(2^n-1,n) = A056972(n).
%Y A244108 T(2n,n) = A265846(n).
%Y A244108 Cf. A195581 (the same read by rows), A195582, A195583, A316944, A317012.
%K A244108 nonn,tabf
%O A244108 0,3
%A A244108 _Alois P. Heinz_, Dec 21 2015