非表示:
キーワード:
-
要旨:
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.
