A244108 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.

1, 1, 2, 2, 4, 16, 40, 80, 80, 8, 64, 400, 2240, 11360, 55040, 253440, 1056000, 3801600, 10982400, 21964800, 21964800, 16, 208, 2048, 18816, 168768, 1508032, 13501312, 121362560, 1099169280, 10049994240, 92644597760, 857213660160, 7907423180800, 72155129446400

Offset

0,3

Comments

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

Links

Alois P. Heinz, Columns k = 0..9, 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

Triangle T(n,k) begins:
: 1;
:    1;
:       2;
:       2,  4;
:          16,      8;
:          40,     64,      16;
:          80,    400,     208,      32;
:          80,   2240,    2048,     608,     64;
:               11360,   18816,    8352,   1664,   128;
:               55040,  168768,  104448,  30016,  4352,   256;
:              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), n=k..2^k-1), k=0..5);

Mathematica

b[n_, k_] := b[n, k] = If[n<2, If[k<n, 0, 1], Sum[Binomial[n-1, r]*b[r, k-1]*b[n-1-r, k-1], {r, 0, n-1}]]; T[n_, k_] := b[n, k] - b[n, k-1]; Table[T[n, k], {k, 0, 5}, {n, k, 2^k-1}] // Flatten (* Jean-François Alcover, Feb 19 2017, 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. A195581 (the same read by rows), A195582, A195583, A316944, A317012.

Sequence in context: A291338 A326481 A009542 * A032318 A090753 A091788

Adjacent sequences: A244105 A244106 A244107 * A244109 A244110 A244111

Keyword

nonn,tabf

Author

Alois P. Heinz, Dec 21 2015

Status

approved