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:








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:


Abstract, Links, (C)

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},
}


Entry last modified by Anja Becker, 02/11/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Daniel Johannsen
Created
02/15/2009 08:28:37 PM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Daniel Johannsen
Daniel Johannsen

Edit Dates
11.02.2011 13:56:44
02/15/2009 10:58:45 PM
02/15/2009 08:28:37 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
CameronJohannsenPrellbergSchweitzer_2008_CountingDefectiveParkingFunctions.pdf