cp's OEIS Frontend

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

%I A374811 #10 Jul 22 2024 20:28:56
%S A374811 -1,0,1,5,7,14,49,1156,2531,2461,5263,23231,48857,142327,161366,
%T A374811 677983151,701098187,49162215523,56895744916,97659246406291,
%U A374811 28593399072431,21502630803250973,26851741349945933,246602936364321931,1508124176077531039,10968493811640186469
%N A374811 Numerator of the expected height of a random binary search tree (BST) with n elements.
%C A374811 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.
%F A374811 a(n) = numerator(A195582(n)/A195583(n) - 1).
%F A374811 a(n) = A195582(n) - A195583(n). - _Alois P. Heinz_, Jul 20 2024
%p A374811 b:= proc(n, k) option remember;
%p A374811       if n=0 then 1
%p A374811     elif n=1 then `if`(k>0, 1, 0)
%p A374811     else add(binomial(n-1, r-1) *b(r-1, k-1) *b(n-r, k-1), r=1..n)
%p A374811       fi
%p A374811     end:
%p A374811 T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
%p A374811 a:= n-> add(T(n, k)*k, k=0..n)/n!:
%p A374811 seq(numer(a(n)-1), n=0..30);
%t A374811 [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}]
%Y A374811 Denominators: A195583.
%Y A374811 Cf. A195582.
%K A374811 sign,frac
%O A374811 0,4
%A A374811 _Melissa O'Neill_, Jul 20 2024