OFFSET
0,3
COMMENTS
Empty external nodes are counted in determining the height of a search tree.
LINKS
EXAMPLE
a(2) = 10 = 2 + 3 + 3 + 2:
.
2 2 1
/ \ / \ / \
1 o 1 3 o 2
/ \ ( ) ( ) / \
o o o o o o o o
(2,1) (2,1,3) (2,3,1) (1,2)
.
MAPLE
b:= proc(n, k) option remember; `if`(n<2, `if`(k<n, 0, 1),
add(binomial(n-1, r)*b(r, k-1)*b(n-1-r, k-1), r=0..n-1))
end:
T:= (n, k)-> b(n, k)-b(n, k-1):
a:= k-> add(T(n, k)*n, n=k..2^k-1):
seq(a(n), n=0..6);
MATHEMATICA
b[n_, k_] := b[n, k] = If[n < 2, If[k < n, 0, 1],
Sum[Binomial[n-1, r] b[r, k-1] b[n-1-r, k-1], {r, 0, n-1}]];
T[n_, k_] := b[n, k] - b[n, k-1];
a[k_] := Sum[T[n, k] n, {n, k, 2^k - 1}];
a /@ Range[0, 6] (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 18 2018
STATUS
approved