Parking functions: from combinatorics to probability

DOI10.1007/S11009-023-10022-5zbMATH Open1515.60043arXiv2103.17180OpenAlexW4321351843MaRDI QIDQ6164864FDOQ6164864

Authors: Richard Kenyon, Mei Yin 

Publication date: 4 July 2023

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

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$.

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

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

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)

Cites Work

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

Cited In (19)

• 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
• Parking functions: interdisciplinary connections
• Probabilizing parking functions
• Exact formulas for moments of sums of classical parking functions
• 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
• Lucky Cars: Expected Values and Generating Functions
• Probabilistic parking functions

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)