Parking functions for mappings

作者：Lackner Marie Louise^*; Panholzer Alois^*

来源：Journal of Combinatorial Theory - Series A, 2016, 142: 1-28.

DOI：10.1016/j.jcta.2016.03.001

• Parking functions
• Mappings
• Enumeration
• Phase transition

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-m of mapping parking functions, i.e., the number of pairs (f, s) with f : [n] -> [n] an n-mapping and s is an element of [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-m and relate it to previously studied combinatorial contexts.

• 出版日期2016-8