cp's OEIS Frontend

A335921 Total height of all binary search trees with n internal nodes.

%I A335921 #24 Apr 26 2022 02:59:14
%S A335921 0,1,4,14,50,178,644,2347,8624,31908,118768,444308,1669560,6298280,
%T A335921 23842032,90531032,344702646,1315726218,5033357852,19294463682,
%U A335921 74099098212,285056401796,1098314920968,4237879802726,16373796107092,63341371265892,245315823125496
%N A335921 Total height of all binary search trees with n internal nodes.
%C A335921 Empty external nodes are counted in determining the height of a search tree.
%H A335921 Alois P. Heinz, <a href="/A335921/b335921.txt">Table of n, a(n) for n = 0..1000</a>
%H A335921 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>
%H A335921 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A335921 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A335921 a(n) = Sum_{k=0..n} k * A335919(n,k) = Sum_{k=0..n} k * A335920(n,k).
%F A335921 a(n) is odd <=> n in { A083420 }.
%e A335921 a(3) = 14 = 3 + 3 + 2 + 3 + 3:
%e A335921 .
%e A335921           3         3        2        1         1
%e A335921          / \       / \      / \      / \       / \
%e A335921         2   o     1   o    1   3    o   3     o   2
%e A335921        / \       / \      ( ) ( )      / \       / \
%e A335921       1   o     o   2     o o o o     2   o     o   3
%e A335921      / \           / \               / \           / \
%e A335921     o   o         o   o             o   o         o   o
%e A335921 .
%p A335921 g:= n-> `if`(n=0, 0, ilog2(n)+1):
%p A335921 b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
%p A335921       add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
%p A335921     end:
%p A335921 T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
%p A335921 a:= n-> add(T(n, k)*k, k=g(n)..n):
%p A335921 seq(a(n), n=0..35);
%t A335921 g[n_] := If[n == 0, 0, Floor@Log2[n] + 1];
%t A335921 b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
%t A335921      Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
%t A335921 T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
%t A335921 a[n_] := Sum[T[n, k]*k, {k, g[n], n}];
%t A335921 Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Apr 26 2022, after _Alois P. Heinz_ *)
%Y A335921 Cf. A083420, A316944, A335919, A335920, A335922.
%K A335921 nonn
%O A335921 0,3
%A A335921 _Alois P. Heinz_, Jun 29 2020