Parking in Trees and Mappings - Enumerative Results and a Phase Change Behaviour

Parking functions were originally introduced in the context of a hashing procedure and have since then been studied intensively in combinatorics. We apply the concept of parking functions to rooted labelled trees and functional digraphs of mappings (i.e., functions $f : [n] \to [n]$). The nodes are considered as parking spaces and the directed edges as one-way streets: Each driver has a preferred parking space and starting with this node he follows the edges in the graph until he either finds a free parking space or all reachable parking spaces are occupied. If all drivers are successful we speak about a parking function for the tree or mapping. Via analytic combinatorics techniques we study the total number $F_{n,m}$ and $M_{n,m}$ of tree and mapping parking functions, respectively, i.e. the number of pairs $(T,s)$ (or $(f,s)$), with $T$ a size-$n$ tree (or $f : [n] \to [n]$ an $n$-mapping) and $s \in [n]^{m}$ a parking function for $T$ (or for $f$) with $m$ drivers, yielding exact and asymptotic results. We describe the phase change behaviour appearing at $m=\frac{n}{2}$ for $F_{n,m}$ and $M_{n,m}$, respectively, and relate it to previously studied combinatorial contexts. Moreover, we present a bijective proof of the occurring relation $n F_{n,m} = M_{n,m}$.