DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2024.29

Statistics of Parking Functions and Labeled Forests

Authors: Stephan Wagner and Mei Yin

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract

In this paper we obtain some new results on the enumeration of parking functions and labeled forests. We introduce new statistics both for parking functions and for labeled forests that are connected to each other by means of a bijection. We determine the joint distribution of two statistics on parking functions and their counterparts on labeled forests. Our results on labeled forests also serve to explain the mysterious equidistribution between two seemingly unrelated statistics in parking functions recently identified by Stanley and Yin and give an explicit bijection between the two statistics.

Cite as

Stephan Wagner and Mei Yin. Statistics of Parking Functions and Labeled Forests. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wagner_et_al:LIPIcs.AofA.2024.29,
  author =	{Wagner, Stephan and Yin, Mei},
  title =	{{Statistics of Parking Functions and Labeled Forests}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.29},
  URN =		{urn:nbn:de:0030-drops-204648},
  doi =		{10.4230/LIPIcs.AofA.2024.29},
  annote =	{Keywords: parking function, labeled forest, generating function, Pollak’s circle argument, bijection}
}

Document

DOI: 10.4230/LIPIcs.AofA.2022.18

Parking Functions, Multi-Shuffle, and Asymptotic Phenomena

Authors: Mei Yin

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

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.

Cite as

Mei Yin. Parking Functions, Multi-Shuffle, and Asymptotic Phenomena. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.AofA.2022.18},
  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}
}

Search Results

Documents authored by Yin, Mei

Statistics of Parking Functions and Labeled Forests

Abstract

Cite as

Parking Functions, Multi-Shuffle, and Asymptotic Phenomena

Abstract

Cite as

Thanks for your feedback!

Could not send message