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

Abel's binomial theoremasymptotic expansionparking functionspanning forestTutte polynomial

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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 birth of the giant component
• The inversion enumerator for labeled trees
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
• 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

(26)

• Counting defective parking functions
• Parking functions, valet functions and priority queues
• Exact formulas for moments of sums of classical parking functions
• Parking function varieties for combinatorial tree models
• Cycle structure of random parking functions
• Generalizing parking functions with randomness
• Enumerating parking completions using join and split
• A combinatorial approach for discrete car parking on random labelled trees
• Probabilizing parking functions
• The number of parking functions with center of a given length
• A three shuffle case of the compositional parking function conjecture
• Asymptotic normality in a discrete analog of the parking problem
• Parking functions for mappings
• Subset parking functions
• Parking functions: interdisciplinary connections
• Parking functions, multi-shuffle, and asymptotic phenomena
• Lucky Cars: Expected Values and Generating Functions
• Probabilistic parking functions
• On Parking Functions and The Tower of Hanoi
• Asymptotic behaviour of the first positions of uniform parking functions
• Some enumerative properties of parking functions
• Statistics of parking functions and labeled forests
• Distribution of new statistics of parking functions and their generalizations
• Probabilistic (m, n)-parking functions
• Metered parking functions
• Out of the parking lot and into the forest: parking functions, bond lattices, and unimodal forests

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)