|
%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
|
