[Zurück]

A. Panholzer, M. Lackner:
"Parking functions for mappings";
Journal of Combinatorial Theory Series A, 142 (2016), S. 1 - 28.

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.

http://dx.doi.org/10.1016/j.disc.2015.08.010