A195581 - OEIS

%I #56 Feb 22 2022 16:15:13

%S 1,0,1,0,0,2,0,0,2,4,0,0,0,16,8,0,0,0,40,64,16,0,0,0,80,400,208,32,0,

%T 0,0,80,2240,2048,608,64,0,0,0,0,11360,18816,8352,1664,128,0,0,0,0,

%U 55040,168768,104448,30016,4352,256,0,0,0,0,253440,1508032,1277568,479040,99200,11008,512

%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), n>=0, 0<=k<=n, read by rows.

%C Empty external nodes are counted in determining the height of a search tree.

%H Alois P. Heinz, <a href="/A195581/b195581.txt">Rows n = 0..140, 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 T(3,3) = 4, because 4 permutations of {1,2,3} result in a binary search tree of height 3:

%e   (1,2,3):   1       (1,3,2):   1     (3,1,2):   3   (3,2,1):   3

%e             / \                / \              / \            / \

%e            o   2              o   3            1   o          2   o

%e               / \                / \          / \            / \

%e              o   3              2   o        o   2          1   o

%e                 / \            / \              / \        / \

%e                o   o          o   o            o   o      o   o

%e Triangle T(n,k) begins:

%e   1;

%e   0, 1;

%e   0, 0, 2;

%e   0, 0, 2,  4;

%e   0, 0, 0, 16,      8;

%e   0, 0, 0, 40,     64,      16;

%e   0, 0, 0, 80,    400,     208,      32;

%e   0, 0, 0, 80,   2240,    2048,     608,     64;

%e   0, 0, 0,  0,  11360,   18816,    8352,   1664,   128;

%e   0, 0, 0,  0,  55040,  168768,  104448,  30016,  4352,   256;

%e   0, 0, 0,  0, 253440, 1508032, 1277568, 479040, 99200, 11008, 512;

%e   ...

%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), k=0..n), n=0..10);

%t b[n_, k_] := b[n, k] = If[n == 0, 1, If[n == 1, If[k > 0, 1, 0], Sum[Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}] ] ]; t [n_, k_] := b[n, k] - If[k > 0, b[n, k-1], 0]; Table[Table[t[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Dec 17 2013, translated from Maple *)

%Y Row sums give A000142. 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. A195582, A195583, A244108 (the same read by columns), A316944, A317012.

%K nonn,tabl

%O 0,6

%A _Alois P. Heinz_, Sep 20 2011