[go: up one dir, main page]

login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #22 Apr 26 2022 02:58:40

%S 0,1,7,97,6031,8760337,8245932762607,3508518207942911995940881,

%T 311594265746788494170059418351454897488270152687

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

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

%H Alois P. Heinz, <a href="/A335922/b335922.txt">Table of n, a(n) for n = 0..12</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

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

%e a(2) = 7 = 2 + 3 + 2:

%e .

%e 2 2 1

%e / \ / \ / \

%e 1 o 1 3 o 2

%e / \ ( ) ( ) / \

%e o o o o o o o o

%e .

%p b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,

%p add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))

%p end:

%p T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):

%p a:= k-> add(T(n, k)*n, n=k..2^k-1):

%p seq(a(n), n=0..10);

%t b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,

%t Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];

%t T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];

%t a[k_] := Sum[T[n, k]*n, {n, k, 2^k - 1}];

%t Table[a[n], {n, 0, 10}] (* _Jean-François Alcover_, Apr 26 2022, after _Alois P. Heinz_ *)

%Y Cf. A317012, A335919, A335920, A335921.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Jun 29 2020