The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 20
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
0,6
COMMENTS
Empty external nodes are counted in determining the height of a search tree.
LINKS
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
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Sep 20 2011
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 06:41 EDT 2024. Contains 373432 sequences. (Running on oeis4.)