0,3
Empty external nodes are counted in determining the height of a search tree.
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
a(n) = Sum_{k=n..2^n-1} k * A335919(k,n) = Sum_{k=n..2^n-1} k * A335920(k,n).
a(2) = 7 = 2 + 3 + 2:
.
2 2 1
/ \ / \ / \
1 o 1 3 o 2
/ \ ( ) ( ) / \
o o o o o o o o
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);
Cf. A317012, A335919, A335920, A335921.
Sequence in context: A005014 A201063 A333246 * A157035 A022008 A200504
Adjacent sequences: A335919 A335920 A335921 * A335923 A335924 A335925
nonn
Alois P. Heinz, Jun 29 2020
approved
