Parking functions: from combinatorics to probability

DOI10.1007/S11009-023-10022-5MaRDI QIDQ6164864zbMATH OpenOpenAlexFDO

Authors Richard Kenyon, Mei Yin

Publication date 4 July 2023

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic expansionTutte polynomialparking functionspanning forestAbel's binomial theorem

Mathematics Subject Classification ID

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

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 study here combinatorial and probabilistic aspects of this generalized case. We construct a family of bijections between parking functions $extPF(m,n)$ with $m$ cars and $n$ spots and spanning forests $mathscrF(n+1,n+1-m)$ with $n+1$ vertices and $n+1-m$ distinct trees having specified roots. This leads to a bijective correspondence between $extPF(m,n)$ and monomial terms in the associated Tutte polynomial of a disjoint union of $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$ labeled vertices with a fixed number of edges, where the graph has $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$.

Recommendations

• Probabilizing parking functions
• Parking functions on directed graphs and some directed trees
• Parking functions
• Parking function varieties for combinatorial tree models
• Parking functions and labeled trees

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• scientific article; zbMATH DE number 1182849 (Why is no real title available?)
• A family of bijections between \(G\)-parking functions and spanning trees
• A polytope related to empirical distributions, plane trees, parking functions, and the associahedron
• A refinement of Cayley's formula for trees
• An Occupancy Discipline and Applications
• Asymptotic distribution for the cost of linear probing hashing
• Asymptotische Eigenschaften der unvollständigen Gammafunktionen
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Depth-first search as a combinatorial correspondence
• Enumerating graphs and Brownian motion
• Enumeration of \((p,q)\)-parking functions
• Exact formulas for moments of sums of classical parking functions
• Generalized parking functions, tree inversions, and multicolored graphs
• Handbook of Enumerative Combinatorics
• Handbook of the Tutte polynomial and related topics
• Linear probing and graphs
• Mappings of acyclic and parking functions
• Multiparking functions, graph searching, and the Tutte polynomial
• On the analysis of linear probing hashing
• On the sandpile group of dual graphs
• Parking functions and noncrossing partitions
• Parking functions, empirical processes, and the width of rooted labeled trees
• Parking functions, valet functions and priority queues
• Probabilizing parking functions
• Self-organized critical state of sandpile automaton models
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
• The birth of the giant component
• The inversion enumerator for labeled trees
• Trees, parking functions, syzygies, and deformations of monomial ideals
• Tutte polynomials and \(G\)-parking functions
• Une famille de polynômes ayant plusieurs propriétés enumeratives

Cited in

(19)

• Lucky Cars: Expected Values and Generating Functions
• Probabilistic parking functions
• A three shuffle case of the compositional parking function conjecture
• Cycle structure of random parking functions
• Enumerating parking completions using join and split
• Parking functions for mappings
• Asymptotic normality in a discrete analog of the parking problem
• Counting defective parking functions
• A combinatorial approach for discrete car parking on random labelled trees
• Probabilizing parking functions
• Exact formulas for moments of sums of classical parking functions
• Parking functions: interdisciplinary connections
• Asymptotic behaviour of the first positions of uniform parking functions
• Generalizing parking functions with randomness
• Subset parking functions
• Parking functions, multi-shuffle, and asymptotic phenomena
• Parking function varieties for combinatorial tree models
• The number of parking functions with center of a given length
• On Parking Functions and The Tower of Hanoi

This page was built for publication: Parking functions: from combinatorics to probability

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