\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Peter J Cameron, Daniel Johannsen, Thomas Prellberg and Pascal Schweitzer}
%
%
\medskip
\noindent
%
%
{\bf Counting Defective Parking Functions}
%
%
\vskip 5mm
\noindent
%
%
%
%
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 {\em defective parking function}
of {\em defect} $k$. Let ${\rm cp}(n,m,k)$ be the number of such
functions.

In this paper, we establish a recurrence relation for the numbers
${\rm 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 ${\rm 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.



\bye