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

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

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.

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