2026-08-06T04:24:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16104 2024-03-06T10:56:58Z ddc:004 open_access

Parking Functions, Multi-Shuffle, and Asymptotic Phenomena Yin, Mei Parking function Multi-shuffle Asymptotic expansion Abel’s multinomial theorem Given a positive integer-valued vector u = (u_1, … , u_m) with u_1 < ⋯ < u_m, a u-parking function of length m is a sequence π = (π_1, … , π_m) of positive integers whose non-decreasing rearrangement (λ_1, … , λ_m) satisfies λ_i ≤ u_i for all 1 ≤ i ≤ m. We introduce a combinatorial construction termed a parking function multi-shuffle to generic u-parking functions and obtain an explicit characterization of multiple parking coordinates. As an application, we derive various asymptotic probabilistic properties of a uniform u-parking function of length m when u_i = cm+ib. The asymptotic scenario in the generic situation c > 0 is in sharp contrast with that of the special situation c = 0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mei Yin 2022 Is Part Of LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2022.18 urn:nbn:de:0030-drops-161041 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.18 eng https://creativecommons.org/licenses/by/4.0/legalcode