Parking Functions: From Combinatorics to Probability

Richard Kenyon () and Mei Yin ()
Additional contact information
Richard Kenyon: Yale University
Mei Yin: University of Denver

Methodology and Computing in Applied Probability, 2023, vol. 25, issue 1, 1-30

Abstract: 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$$ m = n ; we study here combinatorial and probabilistic aspects of this generalized case. We construct a family of bijections between parking functions $$\text {PF}(m, n)$$ PF ( m , n ) with m cars and n spots and spanning forests $$\mathscr {F}(n+1, n+1-m)$$ F ( n + 1 , n + 1 - m ) with $$n+1$$ n + 1 vertices and $$n+1-m$$ n + 1 - m distinct trees having specified roots. This leads to a bijective correspondence between $$\text {PF}(m, n)$$ PF ( m , n ) and monomial terms in the associated Tutte polynomial of a disjoint union of $$n-m+1$$ n - m + 1 complete graphs. We present an identity between the “inversion enumerator” of spanning forests with fixed roots and the “displacement enumerator” of parking functions. The displacement is then related to the number of graphs on $$n+1$$ n + 1 labeled vertices with a fixed number of edges, where the graph has $$n+1-m$$ n + 1 - m disjoint rooted components with specified roots. We investigate various probabilistic properties of a uniform parking function, giving a formula for the law of a single coordinate. As a side result we obtain a recurrence relation for the displacement enumerator. Adapting known results on random linear probes, we further deduce the covariance between two coordinates when $$m=n$$ m = n .

Keywords: Parking function; Spanning forest; Tutte polynomial; Abel’s binomial theorem; Asymptotic expansion; 60C05; 05A16; 05A19; 60F10 (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-023-10022-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:25:y:2023:i:1:d:10.1007_s11009-023-10022-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-023-10022-5

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().