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 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=\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 |
|
Edit History (please click the blue arrow to see the details)
