This site is supported by donations to The OEIS Foundation.

 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. 17
 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 Alois P. Heinz, Rows n = 0..140, flattened FORMULA 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 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), A317012. Sequence in context: A115509 A279360 A134312 * A020474 A135589 A244312 Adjacent sequences:  A195578 A195579 A195580 * A195582 A195583 A195584 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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 15 08:45 EDT 2018. Contains 316210 sequences. (Running on oeis4.)