# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a124453
Showing 1-1 of 1

%I A124453 #7 Jan 17 2024 09:07:52
%S A124453 1,0,-1,2,-8,48,-378,3672,-42368,565760,-8579000,145590000,
%T A124453 -2733455808,56248698240,-1258816278272,30438340438016,
%U A124453 -790789409079296,21967629557170176,-649763240318538624,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 and Patricio V. Poblete. The Analysis of Linear Probing Hashing with Buckets. Algorithmica 21(1): 37-71 (1998)
%H A124453 Alfredo Viola, <a href="https://doi.org/10.46298/dmtcs.3386">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 2005, 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:
%o A124453 (Python)
%o A124453 from functools import cache
%o A124453 from sympy import binomial
%o A124453 @cache
%o A124453 def T(k,d,b):
%o A124453   if d >= b or d < 0 or k < 0: return 0
%o A124453   elif k == 0: return 1
%o A124453   else: return -(sum(binomial(k,j)*((k+d)//b)**(k-j)*T(j,d,b) for j in range(0,k)))
%o A124453 print([T(n,0,2) for n in range(0,22)]) # _Darío Clavijo_, Dec 12 2023
%K A124453 sign
%O A124453 0,4
%A A124453 Alfredo Viola (viola(AT)fing.edu.uy), Dec 16 2006

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE