tailieunhanh - Báo cáo toán học: "Counting Defective Parking Functions"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Counting Defective Parking Functions. | Counting Defective Parking Functions Peter J Cameron Daniel Johannsen Thomas Prellberg Pascal Schweitzer School of Mathematical Sciences Queen Mary University of London Mile End Road London E1 4NS . tp@ Max-Planck-Institut fur Informatik CAMPUS E1 4 66123 Saarbrcken johannse@ pascal@ Submitted Mar 3 2008 Accepted Jul 8 2008 Published Jul 14 2008 Mathematics Subject ClassiEcations 05A15 05A16 Abstract Suppose that m drivers each choose a preferred parking space in a linear car park with n spaces. Each driver goes to the chosen space and parks there if it is free and otherwise takes the Erst available space with a larger number if any . If all drivers park successfully the sequence of choices is called a parking function. In general if k drivers fail to park we have a defective parking function of defect k. Let cp n m k be the number of such functions. In this paper we establish a recurrence relation for the numbers cp n m k and express this as an equation for a three-variable generating function. We solve this equation using the kernel method and extract the coefficients explicitly it turns out that the cumulative totals are partial sums in Abel s binomial identity. Finally we compute the asymptotics of cp n m k . In particular for the case m n if choices are made independently at random the limiting distribution of the defect the number of drivers who fail to park scaled by the square root of n is the Rayleigh distribution. On the other hand in the case m n the probability that all spaces are occupied tends asymptotically to one. 1 Introduction A car park consists of n numbered spaces in a line. The drivers of m cars have independently chosen their favorite parking spaces. Each driver arrives at the car park and proceeds to his chosen space parking there if it is free. If the chosen space is occupied THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R92 1 the driver continues on towards the .