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

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

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.

License Agreements, Terms of Use, Privacy Policy. .

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