Document Open Access Logo

Parking Functions, Multi-Shuffle, and Asymptotic Phenomena

Author Mei Yin

PDF

File

Thumbnail PDF
PDF
LIPIcs.AofA.2022.18.pdf
  • Filesize: 0.9 MB
  • 12 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probability and statistics
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Parking function
  • Multi-shuffle
  • Asymptotic expansion
  • Abel’s multinomial theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.AofA.2022.18

Author Details

Mei Yin
  • Department of Mathematics, University of Denver, Denver, CO, USA

Funding

Research partially supported by the University of Denver’s Faculty Research Fund 84688-145601.

References

  1. Ayomikun Adeniran, Steve Butler, Galen Dorpalen-Barry, Pamela E. Harris, Cyrus Hettle, Qingzhong Liang, Jeremy L. Martin, and Hayan Nam. Enumerating parking completions using join and split. Electron. J. Comb., 27(2), 2020. URL: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i2p44.
  2. Peter J. Cameron, Daniel Johannsen, Thomas Prellberg, and Pascal Schweitzer. Counting defective parking functions. Electron. J. Comb., 15(1), 2008. URL: http://www.combinatorics.org/Volume_15/Abstracts/v15i1r92.html.
  3. Philippe Chassaing and Jean-François Marckert. Parking functions, empirical processes, and the width of rooted labeled trees. Electron. J. Comb., 8(1), 2001. URL: http://www.combinatorics.org/Volume_8/Abstracts/v8i1r14.html.
  4. Robert Cori and Dominique Rossin. On the sandpile group of dual graphs. Eur. J. Comb., 21(4):447-459, 2000. URL: https://doi.org/10.1006/eujc.1999.0366.
  5. Persi Diaconis and Angela Hicks. Probabilizing parking functions. Adv. Appl. Math., 89:125-155, 2017. URL: https://doi.org/10.1016/j.aam.2017.05.004.
  6. D. Foata and J. Riordan. Mappings of acyclic and parking functions. Aequationes Math., 10:10-22, 1974. Google Scholar
  7. J. Haglund, M. Haiman, N. Loehr, J. B. Remmel, and A. Ulyanov. A combinatorial formula for the characters of the diagonal coinvariants. Duke Math. J., 126:195-232, 2005. Google Scholar
  8. R. Kenyon and M. Yin. Parking functions: From combinatorics to probability. arXiv preprint, 2021. URL: http://arxiv.org/abs/2103.17180.
  9. Donald Ervin Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison-Wesley, 1998. URL: https://www.worldcat.org/oclc/312994415.
  10. A. G. Konheim and B. Weiss. An occupancy discipline and applications. SIAM J. Appl. Math., 14(6):1266-1274, 1966. URL: http://www.jstor.org/stable/2946240.
  11. Joseph P. S. Kung and Catherine H. Yan. Expected sums of general parking functions. Ann. Comb., 7:481-493, 2003. URL: https://doi.org/10.1007/s00026-003-0198-7.
  12. Joseph P. S. Kung and Catherine H. Yan. Gončarov polynomials and parking functions. J. Comb. Theory, Ser. A, 102(1):16-37, 2003. URL: https://doi.org/10.1016/S0097-3165(03)00009-8.
  13. J. E. Paguyo. Cycle structure of random parking functions. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.08829.
  14. Jim Pitman. Forest volume decompositions and abel-cayley-hurwitz multinomial expansions. J. Comb. Theory, Ser. A, 98(1):175-191, 2002. URL: https://doi.org/10.1006/jcta.2001.3238.
  15. J. Riordan. Combinatorial Identities. Wiley Series in Probability and Mathematical Statistics. Wiley, 1968. URL: https://books.google.com/books?id=X6ccBWwECP8C.
  16. Richard P. Stanley. Parking functions and noncrossing partitions. Electron. J. Comb., 4(2), 1997. URL: http://www.combinatorics.org/Volume_4/Abstracts/v4i2r20ab.html.
  17. Richard P. Stanley. Hyperplane arrangements, parking functions and tree inversions. In Mathematical essays in honor of Gian-Carlo Rota, volume 161 of Progr. Math., pages 359-375. Birkhäuser Boston, Boston, MA, 1998. Google Scholar
  18. Richard P. Stanley. Enumerative Combinatorics, volume 2. Cambridge University Press, 1999. URL: http://math.mit.edu/~rstan/ec/.
  19. Catherine H. Yan. Generalized parking functions, tree inversions, and multicolored graphs. Adv. Appl. Math., 27(2-3):641-670, 2001. URL: https://doi.org/10.1006/aama.2001.0754.
  20. Catherine H. Yan. Parking functions. In Handbook of Enumerative Combinatorics, Discrete Math. Appl., pages 835-893. CRC Press, Boca Raton, FL, 2015. Google Scholar
  21. M. Yin. Parking functions: Interdisciplinary connections. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.01767.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact