A158466 Numerators of EH(n), the expected value of the height of a probabilistic skip list with n elements and p=1/2.
0, 2, 8, 22, 368, 2470, 7880, 150266, 13315424, 2350261538, 1777792792, 340013628538, 203832594062416, 131294440969788022, 822860039794822168, 177175812995012739374, 231553634961214157747264, 1813465925343969651214825522, 14983458468103810854318443432
Offset: 0
Examples
0, 2, 8/3, 22/7, 368/105, 2470/651, 7880/1953, 150266/35433, 13315424/3011805, 2350261538/513010785, 1777792792/376207909 ... = A158466/A158467
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..100
- P. V. Poblete, J. I. Munro and T. Papadakis, The binomial transform and the analysis of skip lists, Theor. Comput. Sci. 352, 1 (Mar. 2006), 136-158.
- William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, 668-676, June 1990
- Wikipedia, Skip list
Programs
-
Maple
EH:= n-> -add((-1)^k *binomial(n,k) /(1-(1/2)^k), k=1..n): seq(numer(EH(n)), n=0..20);
-
Mathematica
Table[Sum[x*((1-2^(-x))^n-(1-2^-(x-1))^n), {x, 1, Infinity}], {n, 0, 20}] (* Geoffrey Critzer, Dec 13 2009 *)
Formula
EH(n) = Sum_{k>0} k * ((1-(1/2)^k)^n - (1-(1/2)^(k-1))^n).
EH(n) = -Sum_{k=1..n} (-1)^k * C(n,k) / (1-(1/2)^k).
Comments