Counting defective parking functions

MaRDI QIDQ1010819zbMATH OpenFDO

Authors Daniel Johannsen, Thomas Prellberg, P. Schweitzer, Peter J. Cameron

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.0302, https://eudml.org/doc/129971, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r92.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

defective parking functionlinear car parkparking space

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Discrete location and assignment (90B80)

Abstract: Suppose that $n$ drivers each choose a preferred parking space in a linear car park with $m$ spaces. Each driver goes to the chosen space and parks there if it is free, and otherwise takes the first available space with 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 case $m=omega(n)$, the probability that all spaces are occupied tends asymptotically to one.

Recommendations

• Probabilizing parking functions
• Parking functions: from combinatorics to probability
• Cycle structure of random parking functions
• Parking function varieties for combinatorial tree models
• Subset parking functions

Cited in

(9)

• Cycle structure of random parking functions
• Parking functions for mappings
• Partial parking functions
• Parking functions on directed graphs and some directed trees
• Parking functions: interdisciplinary connections
• Connecting k-Naples parking functions and obstructed parking functions via involutions
• Parking functions, multi-shuffle, and asymptotic phenomena
• Parking function varieties for combinatorial tree models
• On friendship and cyclic parking functions

This page was built for publication: Counting defective parking functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010819)