OFFSET
0,3
COMMENTS
Empty external nodes are counted in determining the height of a search tree.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..478
B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.
Wikipedia, Binary search tree
FORMULA
EXAMPLE
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
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.
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)), n=0..30);
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn,frac
AUTHOR
Alois P. Heinz, Sep 20 2011
STATUS
approved