Parking functions: interdisciplinary connections

DOI10.1017/APR.2022.49MaRDI QIDQ6068842zbMATH OpenOpenAlexFDO

Authors Mei Yin

Publication date 15 December 2023

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.01767

zbMATH Keywords

Abel's multinomial theoremasymptotic expansionedge-labeled spanning treemulti-shuffleparking function

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Combinatorial identities, bijective combinatorics (05A19) Combinatorial probability (60C05)

Abstract: Suppose that $m$ drivers each choose a preferred parking space in a linear car park with $n$ spots. In order, each driver goes to their chosen spot and parks there if possible, and otherwise takes the next available spot if it exists. If all drivers park successfully, the sequence of choices is called a parking function. Classical parking functions correspond to the case $m=n$. We investigate various probabilistic properties of a uniform parking function. Through a combinatorial construction termed a parking function multi-shuffle, we give a formula for the law of multiple coordinates in the generic situation $mlesssimn$. We further deduce all possible covariances, between two coordinates, between a coordinate and an unattempted spot, and between two unattempted spots. This asymptotic scenario in the generic situation $mlesssimn$ is in sharp contrast with that of the special situation $m=n$. A generalization of parking functions called interval parking functions is also studied, in which each driver is willing to park only in a fixed interval of spots. We construct a family of bijections between interval parking functions with $n$ cars and $n$ spots and edge-labeled spanning trees with $n+1$ vertices and a specified root.

Recommendations

• Parking functions: from combinatorics to probability
• Probabilizing parking functions
• Parking functions, multi-shuffle, and asymptotic phenomena
• Parking functions
• Subset parking functions

Cites work

• A polytope related to empirical distributions, plane trees, parking functions, and the associahedron
• A refinement of Cayley's formula for trees
• A transducer approach to Coxeter groups
• Combinatorics of Coxeter Groups
• Conjectures on the quotient ring by diagonal invariants
• Counting defective parking functions
• Enumerating parking completions using join and split
• Expected sums of general parking functions
• Forest volume decompositions and Abel-Cayley-Hurwitz multinomial expansions
• Generalized parking functions, tree inversions, and multicolored graphs
• scientific article; zbMATH DE number 1182849 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• Interval parking functions
• Mappings of acyclic and parking functions
• On the sandpile group of dual graphs
• Parking cars after a trailer
• Parking functions
• Parking functions and noncrossing partitions
• Parking functions, empirical processes, and the width of rooted labeled trees
• Parking functions: from combinatorics to probability
• Probabilizing parking functions

Cited in

(6)

• Subsidized Parking and Neighborhood Nuisances: A Supplement
• scientific article; zbMATH DE number 7058727 (Why is no real title available?)
• Parking functions, multi-shuffle, and asymptotic phenomena
• Asymptotic behaviour of the first positions of uniform parking functions
• Permutation invariant parking assortments
• Probabilistic (m, n)-parking functions

This page was built for publication: Parking functions: interdisciplinary connections

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