Electronic Journal Article @Article Zeitschriftenartikel in einem e-Journal

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Cameron, Peter Johannsen, Daniel Prellberg, Thomas Schweitzer, Pascal dblp dblp dblp dblp Not MPG Author(s): Cameron, Peter Prellberg, Thomas
 BibTeX cite key*: CameronJohannsenPrellbergSchweitzer2008

 Title
 Title*: Counting Defective Parking Functions CameronJohannsenPrellbergSchweitzer_2008_CountingDefectiveParkingFunctions.pdf (250.68 KB)

 Journal
 Journal Title*: Electronic Journal of Combinatorics Journal's URL: http://www.combinatorics.org Download URL for the article: http://www.combinatorics.org/Volume_15/PDF/v15i1r92.pdf Language: English

 Publisher
 Publisher's Name: Publisher's URL: Publisher's Address: ISSN:

 Vol, No, Year, pp.
 Volume: 15 Number: 1 Month: July Year*: 2008 Pages: R92 Number of VG Pages: Sequence Number: DOI:

 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

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@MISC{CameronJohannsenPrellbergSchweitzer2008,
AUTHOR = {Cameron, Peter and Johannsen, Daniel and Prellberg, Thomas and Schweitzer, Pascal},
TITLE = {Counting Defective Parking Functions},
JOURNAL = {Electronic Journal of Combinatorics},
YEAR = {2008},
NUMBER = {1},
VOLUME = {15},
PAGES = {R92},
MONTH = {July},
}