Note: 

(LaTeX) 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 first 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 \emph{defective parking function} of \emph{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 threevariable 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=\omega(n)$, the probability that all spaces are occupied tends asymptotically to one. 
URL for the Abstract: 

Categories / Keywords: 
Combinatorial Enumeration, Generating Functions, Parking Functions 
HyperLinks / References / URLs: 

Copyright Message: 

Personal Comments: 

Download
Access Level: 
Public 
