cp's OEIS Frontend

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

%I A335922 #22 Apr 26 2022 02:58:40
%S A335922 0,1,7,97,6031,8760337,8245932762607,3508518207942911995940881,
%T A335922 311594265746788494170059418351454897488270152687
%N A335922 Total number of internal nodes in all binary search trees of height n.
%C A335922 Empty external nodes are counted in determining the height of a search tree.
%H A335922 Alois P. Heinz, <a href="/A335922/b335922.txt">Table of n, a(n) for n = 0..12</a>
%H A335922 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>
%H A335922 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A335922 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A335922 a(n) = Sum_{k=n..2^n-1} k * A335919(k,n) = Sum_{k=n..2^n-1} k * A335920(k,n).
%e A335922 a(2) = 7 = 2 + 3 + 2:
%e A335922 .
%e A335922          2        2        1
%e A335922         / \      / \      / \
%e A335922        1   o    1   3    o   2
%e A335922       / \      ( ) ( )      / \
%e A335922      o   o     o o o o     o   o
%e A335922 .
%p A335922 b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
%p A335922       add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
%p A335922     end:
%p A335922 T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
%p A335922 a:= k-> add(T(n, k)*n, n=k..2^k-1):
%p A335922 seq(a(n), n=0..10);
%t A335922 b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
%t A335922      Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
%t A335922 T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
%t A335922 a[k_] := Sum[T[n, k]*n, {n, k, 2^k - 1}];
%t A335922 Table[a[n], {n, 0, 10}] (* _Jean-François Alcover_, Apr 26 2022, after _Alois P. Heinz_ *)
%Y A335922 Cf. A317012, A335919, A335920, A335921.
%K A335922 nonn
%O A335922 0,3
%A A335922 _Alois P. Heinz_, Jun 29 2020