Probabilizing parking functions

Abstract: We explore the link between combinatorics and probability generated by the question "What does a random parking function look like?" This gives rise to novel probabilistic interpretations of some elegant, known generating functions. It leads to new combinatorics: how many parking functions begin with

i

? We classify features (e.g., the full descent pattern) of parking functions that have exactly the same distribution among parking functions as among all functions. Finally, we develop the link between parking functions and Brownian excursion theory to give examples where the two ensembles differ.

Review text

Let us imagine that there are \(n\) cars and each has a preferred spot, the car \(i\) wants \(\pi_i\), \(1\leq i\leq n\), with \(1\leq\pi_i\leq n\). We have the following definition: A parking function is a sequence \(\pi=(\pi_1, \pi_2,\dots,\pi_n)\) with \(1\leq\pi_i\leq n\) so that all cars can park. Following a classical tradition, the author asks the following questions: {\parindent=0.6cm \begin{itemize}\item[(1)] What is the chance that \(\pi_i=j\)? \item[(2)] What is the distribution of the sum \(\sum_j \pi_j\)? \end{itemize}} Finally, the last section discusses open problems.

Recommendations

Cites work

Cited in

(40)

This page was built for publication: Probabilizing parking functions

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