A195582 - OEIS

%I #29 Jun 29 2020 18:09:02

%S 0,1,2,8,10,19,64,1471,3161,3028,6397,27956,58307,168652,190031,

%T 794076401,817191437,57056556523,65776878541,112508501827291,

%U 32836043478431,24620974441660973,30663050241335933,280904716386831931,1713934856212591039,12438570098319186469

%N Numerator of the average height of a binary search tree on n elements.

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

%H Alois P. Heinz, <a href="/A195582/b195582.txt">Table of n, a(n) for n = 0..478</a>

%H B. Reed, <a href="http://doi.acm.org/10.1145/765568.765571">The height of a random binary search tree</a>, J. ACM, 50 (2003), 306-332.

%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 A195582(n)/A195583(n) = 1/n! * Sum_{k=1..n} k * A195581(n,k).

%F A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1), with alpha = 4.311... (A195596) and beta = 1.953... (A195599).

%F A195582(n)/A195583(n) = A316944(n) / A000142(n).

%e 0/1, 1/1, 2/1, 8/3, 10/3, 19/5, 64/15, 1471/315, 3161/630, 3028/567, 6397/1134, 27956/4725, 58307/9450, 168652/26325, 190031/28665 ... = A195582/A195583

%e For n = 3 there are 2 permutations of {1,2,3} resulting in a binary search tree of height 2 and 4 permutations resulting in a tree of height 3.  The average height is (2*2+4*3)/3! = (4+12)/6 = 16/6 = 8/3.

%p b:= proc(n,k) option remember;

%p       if n=0 then 1

%p     elif n=1 then `if`(k>0, 1, 0)

%p     else add(binomial(n-1,r-1) *b(r-1,k-1) *b(n-r,k-1), r=1..n)

%p       fi

%p     end:

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

%p a:= n-> add(T(n,k)*k, k=0..n)/n!:

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

%t b[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]], {n, 0, 30}] (* _Jean-François Alcover_, Mar 01 2016, after _Alois P. Heinz_ *)

%Y Denominators: A195583.

%Y Cf. A000142, A195581, A195596, A195597, A195598, A195599, A195600, A195601, A244108, A316944.

%K nonn,frac

%O 0,3

%A _Alois P. Heinz_, Sep 20 2011