A. Panholzer, M. Lackner:
"Parking functions for mappings";
Journal of Combinatorial Theory Series A,
We apply the concept of parking functions to functional digraphs of mappings by considering the nodes 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 of a parking function for the mapping. We transfer well-known characterizations of parking functions to mappings. Via analytic combinatorics techniques we study the total number M n , m of mapping parking functions, i.e., the number of pairs ( f , s ) with f : n ¿ n an n-mapping and s ¿ n m a parking function for f with m drivers, yielding exact and asymptotic results. Moreover, we describe the phase change behaviour appearing at m = n / 2 for M n , m and relate it to previously studied combinatorial contexts.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.