login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 11
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 11 03:22 EDT 2020. Contains 336421 sequences. (Running on oeis4.)