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,6

Comments

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

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

Formula

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

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

Example

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

Maple

b:= proc(n, k) option remember; `if`(n<2, `if`(k<n, 0, 1),
      add(binomial(n-1, r)*b(r, k-1)*b(n-1-r, k-1), r=0..n-1))
    end:
T:= (n, 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 *)

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.

Sequence in context: A134312 A329790 A343649 * A020474 A135589 A244312

Adjacent sequences: A195578 A195579 A195580 * A195582 A195583 A195584

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 20 2011

Status

approved