%I A124453
%S A124453 1,0,1,2,8,48,378,3672,42368,565760,8579000,145590000,2733455808,56248698240,
%T A124453 1258816278272,30438340438016,790789409079296,21967629557170176,649763240318538624,
%U A124453 20387405315291592960,676348013837480576000,23653682853089611520000
%V A124453 1,0,-1,2,-8,48,-378,3672,-42368,565760,-8579000,145590000,-2733455808,
               56248698240,
%W A124453 -1258816278272,30438340438016,-790789409079296,21967629557170176,-649763240318538624,
%X A124453 20387405315291592960,-676348013837480576000,23653682853089611520000
%N 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).
%C A124453 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.
%C A124453 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.
%D A124453 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
%D A124453 Alfredo Viola and Patricio V. Poblete. The Analysis of Linear Probing 
               Hashing with Buckets. Algorithmica 21(1): 37-71 (1998)
%H A124453 Alfredo Viola, <a href="http://www.dmtcs.org/pdfpapers/dmAD0127.pdf">
               Distributional analysis of Robin Hood linear probing hashing with 
               buckets</a>, 2005 International Conference on Analysis of Algorithms, 
               Conrado Martinez (ed.), Discrete Mathematics and Theoretical Computer 
               Science Proceedings AD, pp. 297-306
%F A124453 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.
%p A124453 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:
%Y A124453 Sequence in context: A054726 A003576 A095989 this_sequence A000165 A109664 
               A009812
%Y A124453 Adjacent sequences: A124450 A124451 A124452 this_sequence A124454 A124455 
               A124456
%K A124453 sign
%O A124453 0,4
%A A124453 Alfredo Viola (viola(AT)fing.edu.uy), Dec 16 2006