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.

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, 0, 0, 80, 2240, 2048, 608, 64, 0, 0, 0, 0, 11360, 18816, 8352, 1664, 128, 0, 0, 0, 0, 55040, 168768, 104448, 30016, 4352, 256, 0, 0, 0, 0, 253440, 1508032, 1277568, 479040, 99200, 11008, 512

Offset: 0

Author

Alois P. Heinz, Sep 20 2011

Keywords

• nonn
• tabl

Comments

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

Examples

			T(3,3) = 4, because 4 permutations of {1,2,3} result in a binary search tree of height 3:
  (1,2,3):   1       (1,3,2):   1     (3,1,2):   3   (3,2,1):   3
            / \                / \              / \            / \
           o   2              o   3            1   o          2   o
              / \                / \          / \            / \
             o   3              2   o        o   2          1   o
                / \            / \              / \        / \
               o   o          o   o            o   o      o   o
Triangle T(n,k) begins:
  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, 0, 0, 80,   2240,    2048,     608,     64;
  0, 0, 0,  0,  11360,   18816,    8352,   1664,   128;
  0, 0, 0,  0,  55040,  168768,  104448,  30016,  4352,   256;
  0, 0, 0,  0, 253440, 1508032, 1277568, 479040, 99200, 11008, 512;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• Wikipedia, Binary search tree
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Row sums give A000142. Column sums give A227822.

Main diagonal gives A011782, lower diagonal gives A076616.

T(n,A000523(n)+1) = A076615(n).

T(2^n-1,n) = A056972(n).

T(2n,n) = A265846(n).

Cf. A195582, A195583, A244108 (the same read by columns), A316944, A317012.

Programs

Maple

b:= proc(n, k) option remember; `if`(n<2, `if`(k b(n, k)-b(n, k-1):
seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

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 *)

Formula

Sum_{k=0..n} k * T(n,k) = A316944(n).

Sum_{k=n..2^n-1} k * T(k,n) = A317012(n).