Alfredo Viola (GREYC, Caen et Montevideo, Republica oriental del Uruguay)

In this talk we present the first distributional analysis of both, a parkingproblem and a linear probing hashing scheme with buckets of size b. The exact distribution of the cost of successful searches for a b α-full table is obtained, and moments and asymptotic results are derived. With the use of the Poisson transform distributional results are also obtained for tables of size m and with n elements. We also present results related with the distribution of bucket occupancy. A key element in the analysis is the use of a new family of numbers, that satisfies a recurrence resembling that of the Bernoulli numbers. These numbers may prove helpful in studying recurrences involving truncated generating functions, as well as in other problems related with buckets.