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!)
A124453 Define Tuba numbers T(k,d,b) (0 <= d < b) by Sum_{j=0..k} binomial(k,j)*floor((k+d)/b)^(k-j)*T(j,d,b) = delta(k,0). Sequence gives T(n,0,2). 1
1, 0, -1, 2, -8, 48, -378, 3672, -42368, 565760, -8579000, 145590000, -2733455808, 56248698240, -1258816278272, 30438340438016, -790789409079296, 21967629557170176, -649763240318538624, 20387405315291592960, -676348013837480576000, 23653682853089611520000 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

This family of sequences appeared when I was solving an open problem presented in volume 3 of the Art of Computer Programming by D. E. Knuth. This problem asked for the expected value of the search cost of a random element in a linear probing hashing table with buckets of size b. In our paper in Algorithmica 21(1): 37-71 (1998) we solve this open problem.

Later we found the exact distribution when the Robin Hood heuristic is used to solve collisions. One of the main results was the introduction of the exact distribution of the bucket occupancy in the Poisson Model. By depoissonization methods we may find this value for exact n and m, but calculations are complicated. This result was presented in the 2005 International Conference on Analysis of Algorithms. The key component of the analysis was the introduction of this sequence of numbers.

REFERENCES

Alfredo Viola (2005), Distributional analysis of Robin Hood linear probing hashing with buckets, in 2005 International Conference on Analysis of Algorithms, Conrado Martinez (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AD, pp. 297-306

Alfredo Viola and Patricio V. Poblete. The Analysis of Linear Probing Hashing with Buckets. Algorithmica 21(1): 37-71 (1998)

LINKS

Table of n, a(n) for n=0..21.

Alfredo Viola, Distributional analysis of Robin Hood linear probing hashing with buckets, 2005 International Conference on Analysis of Algorithms, Conrado Martinez (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AD, pp. 297-306

FORMULA

The exponential generating function T_{b*alpha) is the probability that a given bucket has more than d empty slots when we insert n elements in a linear probing hashing table with m buckets of size b when n,m -> infinity and n = b*alpha.

MAPLE

T := proc(k, d, b) local j: options remember: if (d >= b or d < 0 or k <0) then 0 elif k = 0 then 1 else eval(-sum('binomial(k, j)*floor((k+d)/b)^(k-j)*T(j, d, b)', j=0..k-1)) fi end:

CROSSREFS

Sequence in context: A211196 A334856 A219613 * A211827 A322339 A000165

Adjacent sequences:  A124450 A124451 A124452 * A124454 A124455 A124456

KEYWORD

sign

AUTHOR

Alfredo Viola (viola(AT)fing.edu.uy), Dec 16 2006

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 June 21 06:55 EDT 2021. Contains 345358 sequences. (Running on oeis4.)