A335922 Total number of internal nodes in all binary search trees of height n.

0, 1, 7, 97, 6031, 8760337, 8245932762607, 3508518207942911995940881, 311594265746788494170059418351454897488270152687

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

Mathematica

b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
     Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
a[k_] := Sum[T[n, k]*n, {n, k, 2^k - 1}];
Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Apr 26 2022, after Alois P. Heinz *)

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