License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2022.18
URN: urn:nbn:de:0030-drops-161041
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16104/
Go to the corresponding LIPIcs Volume Portal

Yin, Mei

Parking Functions, Multi-Shuffle, and Asymptotic Phenomena

pdf-format:
LIPIcs-AofA-2022-18.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{yin:LIPIcs.AofA.2022.18,
  author =	{Yin, Mei},
  title =	{{Parking Functions, Multi-Shuffle, and Asymptotic Phenomena}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{18:1--18:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16104},
  URN =		{urn:nbn:de:0030-drops-161041},
  doi =		{10.4230/LIPIcs.AofA.2022.18},
  annote =	{Keywords: Parking function, Multi-shuffle, Asymptotic expansion, Abel’s multinomial theorem}
}

Keywords: Parking function, Multi-shuffle, Asymptotic expansion, Abel’s multinomial theorem
Collection: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Issue Date: 2022
Date of publication: 08.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI