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

Author

Alois P. Heinz, Jun 29 2020

Keywords

• nonn

Comments

Empty external nodes are counted in determining the height of a search tree.

Examples

			a(2) = 7 = 2 + 3 + 2:
.
         2        2        1
        / \      / \      / \
       1   o    1   3    o   2
      / \      ( ) ( )      / \
     o   o     o o o o     o   o
.
		

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

Crossrefs

Cf. A317012, A335919, A335920, A335921.

Programs

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

Formula

a(n) = Sum_{k=n..2^n-1} k * A335919(k,n) = Sum_{k=n..2^n-1} k * A335920(k,n).