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!)
 A335922 Total number of internal nodes in all binary search trees of height n. 5
 0, 1, 7, 97, 6031, 8760337, 8245932762607, 3508518207942911995940881, 311594265746788494170059418351454897488270152687 (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, Table of n, a(n) for n = 0..12 Wikipedia, Binary search tree FORMULA a(n) = Sum_{k=n..2^n-1} k * A335919(k,n) = Sum_{k=n..2^n-1} k * A335920(k,n). EXAMPLE a(2) = 7 = 2 + 3 + 2: .          2        2        1         / \      / \      / \        1   o    1   3    o   2       / \      ( ) ( )      / \      o   o     o o o o     o   o . MAPLE b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,       add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))     end: T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0): a:= k-> add(T(n, k)*n, n=k..2^k-1): seq(a(n), n=0..10); CROSSREFS Cf. A317012, A335919, A335920, A335921. Sequence in context: A005014 A201063 A333246 * A157035 A022008 A200504 Adjacent sequences:  A335919 A335920 A335921 * A335923 A335924 A335925 KEYWORD nonn AUTHOR Alois P. Heinz, Jun 29 2020 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.

Last modified April 15 03:00 EDT 2021. Contains 342974 sequences. (Running on oeis4.)