کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655076 | 1632930 | 2016 | 28 صفحه PDF | دانلود رایگان |
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 Mn,mMn,m of mapping parking functions, i.e., the number of pairs (f,s)(f,s) with f:[n]→[n]f:[n]→[n] an n -mapping and s∈[n]ms∈[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/2m=n/2 for Mn,mMn,m and relate it to previously studied combinatorial contexts.
Journal: Journal of Combinatorial Theory, Series A - Volume 142, August 2016, Pages 1–28