login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A195582 Numerator of the average height of a binary search tree on n elements. 12
0, 1, 2, 8, 10, 19, 64, 1471, 3161, 3028, 6397, 27956, 58307, 168652, 190031, 794076401, 817191437, 57056556523, 65776878541, 112508501827291, 32836043478431, 24620974441660973, 30663050241335933, 280904716386831931, 1713934856212591039, 12438570098319186469 (list; graph; refs; listen; history; text; internal format)
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.

FORMULA

A195582(n)/A195583(n) = 1/n! * Sum_{k=1..n} k * A195581(n,k).

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

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

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

Denominators: A195583.

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

Sequence in context: A297293 A294157 A082396 * A071388 A209202 A032356

Adjacent sequences:  A195579 A195580 A195581 * A195583 A195584 A195585

KEYWORD

nonn,frac

AUTHOR

Alois P. Heinz, Sep 20 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 13:37 EST 2020. Contains 332159 sequences. (Running on oeis4.)