A374811 Numerator of the expected height of a random binary search tree (BST) with n elements.

-1, 0, 1, 5, 7, 14, 49, 1156, 2531, 2461, 5263, 23231, 48857, 142327, 161366, 677983151, 701098187, 49162215523, 56895744916, 97659246406291, 28593399072431, 21502630803250973, 26851741349945933, 246602936364321931, 1508124176077531039, 10968493811640186469

Offset

0,4

Comments

Here we're using the conventional definition of BST height, which is path length from the root to the node (the height of an empty tree is -1), as compared to A195582 which has the height one greater.

Links

Table of n, a(n) for n=0..25.

Formula

a(n) = numerator(A195582(n)/A195583(n) - 1).

a(n) = A195582(n) - A195583(n). - Alois P. Heinz, Jul 20 2024

Maple

b:= proc(n, k) option remember;
      if n=0 then 1
    elif n=1 then `if`(k>0, 1, 0)
    else add(binomial(n-1, r-1) *b(r-1, k-1) *b(n-r, k-1), r=1..n)
      fi
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
a:= n-> add(T(n, k)*k, k=0..n)/n!:
seq(numer(a(n)-1), n=0..30);

Mathematica

[n_, k_] := b[n, k] = If[n==0, 1, If[n==1, If[k>0, 1, 0], Sum[Binomial[n - 1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}]]]; T[n_, k_] := b[n, k] - If[ k>0, b[n, k-1], 0]; a[n_] := Sum[T[n, k]*k, {k, 0, n}]/n!; Table[ Numerator[a[n]-1], {n, 0, 30}]

Crossrefs

Denominators: A195583.

Cf. A195582.

Sequence in context: A314353 A043099 A030755 * A373113 A170827 A314354

Adjacent sequences: A374807 A374808 A374809 * A374812 A374813 A374814

Keyword

sign,frac,new

Author

Melissa O'Neill, Jul 20 2024

Status

approved