cp's OEIS Frontend

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

%I A195581 #56 Feb 22 2022 16:15:13
%S A195581 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 A195581 0,0,80,2240,2048,608,64,0,0,0,0,11360,18816,8352,1664,128,0,0,0,0,
%U A195581 55040,168768,104448,30016,4352,256,0,0,0,0,253440,1508032,1277568,479040,99200,11008,512
%N A195581 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 A195581 Empty external nodes are counted in determining the height of a search tree.
%H A195581 Alois P. Heinz, <a href="/A195581/b195581.txt">Rows n = 0..140, flattened</a>
%H A195581 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>
%H A195581 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A195581 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A195581 Sum_{k=0..n} k * T(n,k) = A316944(n).
%F A195581 Sum_{k=n..2^n-1} k * T(k,n) = A317012(n).
%e A195581 T(3,3) = 4, because 4 permutations of {1,2,3} result in a binary search tree of height 3:
%e A195581   (1,2,3):   1       (1,3,2):   1     (3,1,2):   3   (3,2,1):   3
%e A195581             / \                / \              / \            / \
%e A195581            o   2              o   3            1   o          2   o
%e A195581               / \                / \          / \            / \
%e A195581              o   3              2   o        o   2          1   o
%e A195581                 / \            / \              / \        / \
%e A195581                o   o          o   o            o   o      o   o
%e A195581 Triangle T(n,k) begins:
%e A195581   1;
%e A195581   0, 1;
%e A195581   0, 0, 2;
%e A195581   0, 0, 2,  4;
%e A195581   0, 0, 0, 16,      8;
%e A195581   0, 0, 0, 40,     64,      16;
%e A195581   0, 0, 0, 80,    400,     208,      32;
%e A195581   0, 0, 0, 80,   2240,    2048,     608,     64;
%e A195581   0, 0, 0,  0,  11360,   18816,    8352,   1664,   128;
%e A195581   0, 0, 0,  0,  55040,  168768,  104448,  30016,  4352,   256;
%e A195581   0, 0, 0,  0, 253440, 1508032, 1277568, 479040, 99200, 11008, 512;
%e A195581   ...
%p A195581 b:= proc(n, k) option remember; `if`(n<2, `if`(k<n, 0, 1),
%p A195581       add(binomial(n-1, r)*b(r, k-1)*b(n-1-r, k-1), r=0..n-1))
%p A195581     end:
%p A195581 T:= (n, k)-> b(n, k)-b(n, k-1):
%p A195581 seq(seq(T(n, k), k=0..n), n=0..10);
%t A195581 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 A195581 Row sums give A000142. Column sums give A227822.
%Y A195581 Main diagonal gives A011782, lower diagonal gives A076616.
%Y A195581 T(n,A000523(n)+1) = A076615(n).
%Y A195581 T(2^n-1,n) = A056972(n).
%Y A195581 T(2n,n) = A265846(n).
%Y A195581 Cf. A195582, A195583, A244108 (the same read by columns), A316944, A317012.
%K A195581 nonn,tabl
%O A195581 0,6
%A A195581 _Alois P. Heinz_, Sep 20 2011